V tomto výučbe sa dozviete, ako funguje binárny vyhľadávací strom. Nájdete tiež pracovné príklady binárneho vyhľadávacieho stromu v jazykoch C, C ++, Java a Python.
Binárny vyhľadávací strom je dátová štruktúra, ktorá nám rýchlo umožňuje udržiavať triedený zoznam čísel.
- Binárny strom sa nazýva, pretože každý uzol stromu má maximálne dve deti.
- Nazýva sa vyhľadávací strom, pretože ho možno použiť na včasné vyhľadanie prítomnosti čísla
O(log(n)).
Vlastnosti, ktoré oddeľujú binárny vyhľadávací strom od bežného binárneho stromu, sú
- Všetky uzly ľavého podstromu sú menšie ako koreňový uzol
- Všetky uzly pravého podstromu sú viac ako koreňový uzol
- Oba podstromy každého uzla sú tiež BST, tj majú vyššie uvedené dve vlastnosti
Strom, ktorý má pravý podstrom s jednou hodnotou menšou ako koreň, ukazuje, že nejde o platný binárny vyhľadávací strom.
Binárny strom vpravo nie je binárny vyhľadávací strom, pretože pravý podstrom uzla „3“ obsahuje nižšiu hodnotu.
S binárnym vyhľadávacím stromom môžete vykonať dve základné operácie:
Vyhľadávacia operácia
Algoritmus závisí od vlastnosti BST, že ak má každý ľavý podstrom hodnoty pod koreňom a každý pravý podstrom má hodnoty nad koreňom.
Ak je hodnota pod koreňom, môžeme s istotou povedať, že sa nenachádza v pravom podstrome; musíme hľadať iba v ľavom podstrome a ak je hodnota nad koreňom, môžeme s istotou povedať, že hodnota nie je v ľavom podstrome; musíme hľadať iba v pravom podstrome.
Algoritmus:
If root == NULL return NULL; If number == root->data return root->data; If number data return search(root->left) If number> root->data return search(root->right)
Pokúsme sa to vizualizovať pomocou diagramu.
4 sa nenájde, priechod ľavým podstromom 8 
4 sa nenájde, priechod pravým podstromom 3 
4 sa nenájde, priechod ľavým podstromom 6 4 sa nájde
Ak je hodnota nájdená, vrátime ju tak, aby sa propagovala v každom kroku rekurzie, ako je to znázornené na obrázku nižšie.
Ak ste si mohli všimnúť, štyrikrát sme zavolali spätné vyhľadávanie (štruktúrovaný uzol *). Keď vrátime buď nový uzol, alebo NULL, hodnota sa vráti znova a znova, až kým search (root) nevráti konečný výsledok.
Ak sa hodnota nachádza v ktoromkoľvek z podstromov, rozšíri sa nahor, aby sa nakoniec vrátila, inak sa vráti null.
Ak sa hodnota nenájde, nakoniec sa dostaneme k ľavému alebo pravému potomkovi listového uzla, ktorý má hodnotu NULL, a ten sa rozšíri a vráti.
Vložiť operáciu
Vloženie hodnoty na správnu pozíciu je podobné ako pri hľadaní, pretože sa snažíme zachovať pravidlo, že ľavý podstrom je menší ako root a pravý podstrom je väčší ako root.
Stále ideme do pravého podstromu alebo do ľavého podstromu v závislosti od hodnoty a keď dosiahneme bod, ľavý alebo pravý podstrom je nulový, umiestnime tam nový uzol.
Algoritmus:
If node == NULL return createNode(data) if (data data) node->left = insert(node->left, data); else if (data> node->data) node->right = insert(node->right, data); return node;
Algoritmus nie je taký jednoduchý, ako vyzerá. Skúsme si predstaviť, ako pridáme číslo k existujúcemu BST.
4 <8 tak, priečne cez ľavé dieťa od 8 
4> 3 tak, priečne cez pravé dieťa od 8 
4 <6 tak, priečne cez ľavé dieťa od 6 
Vložte 4 ako ľavé dieťa od 6
Pripojili sme uzol, ale stále musíme opustiť funkciu bez poškodenia zvyšku stromu. Tu sa return node;hodí koniec. V prípade NULL, že sa novovytvorený uzol vráti a pripojí sa k nadradenému uzlu, inak sa ten istý uzol vráti bez akejkoľvek zmeny, keď ideme hore, kým sa nevrátime ku koreňu.
Takto je zaistené, že pri návrate naspäť do stromu sa nezmenia ďalšie spojenia uzlov.
Obrázok ukazujúci na dôležitosť vrátenia koreňového prvku na konci, aby prvky nestratili svoju pozíciu počas kroku rekurzie nahor.
Operácia vymazania
Existujú tri prípady odstránenia uzla z binárneho vyhľadávacieho stromu.
Prípad I
V prvom prípade je uzlom, ktorý sa má vymazať, listový uzol. V takom prípade jednoducho odstráňte uzol zo stromu.
4 sa má vymazať 
Vymazať uzol
Prípad II
V druhom prípade má uzol, ktorý sa má vymazať, jeden podradený uzol. V takom prípade postupujte podľa nasledujúcich pokynov:
- Nahraďte tento uzol jeho podradeným uzlom.
- Odstráňte podradený uzol z pôvodnej polohy.
6 sa má vymazať, 
skopírovať hodnotu jeho podriadeného prvku do uzla a odstrániť podradený 
finálny strom
Prípad III
V treťom prípade má uzol, ktorý sa má vymazať, dve podradené položky. V takom prípade postupujte takto:
- Získajte následného poradia tohto uzla.
- Nahraďte uzol nasledovným radením.
- Odstráňte neusporiadaného nástupcu z pôvodnej polohy.
3 sa má vymazať Skopírujte hodnotu nasledujúceho poradia (4) do uzla 
Odstrániť nasledujúceho poradia
Príklady jazyka Python, Java a C / C ++
Python Java C C ++ # Binary Search Tree operations in Python # Create a node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Inorder traversal def inorder(root): if root is not None: # Traverse left inorder(root.left) # Traverse root print(str(root.key) + "->", end=' ') # Traverse right inorder(root.right) # Insert a node def insert(node, key): # Return a new node if the tree is empty if node is None: return Node(key) # Traverse to the right place and insert the node if key < node.key: node.left = insert(node.left, key) else: node.right = insert(node.right, key) return node # Find the inorder successor def minValueNode(node): current = node # Find the leftmost leaf while(current.left is not None): current = current.left return current # Deleting a node def deleteNode(root, key): # Return if the tree is empty if root is None: return root # Find the node to be deleted if key root.key): root.right = deleteNode(root.right, key) else: # If the node is with only one child or no child if root.left is None: temp = root.right root = None return temp elif root.right is None: temp = root.left root = None return temp # If the node has two children, # place the inorder successor in position of the node to be deleted temp = minValueNode(root.right) root.key = temp.key # Delete the inorder successor root.right = deleteNode(root.right, temp.key) return root root = None root = insert(root, 8) root = insert(root, 3) root = insert(root, 1) root = insert(root, 6) root = insert(root, 7) root = insert(root, 10) root = insert(root, 14) root = insert(root, 4) print("Inorder traversal: ", end=' ') inorder(root) print("Delete 10") root = deleteNode(root, 10) print("Inorder traversal: ", end=' ') inorder(root)
// Binary Search Tree operations in Java class BinarySearchTree ( class Node ( int key; Node left, right; public Node(int item) ( key = item; left = right = null; ) ) Node root; BinarySearchTree() ( root = null; ) void insert(int key) ( root = insertKey(root, key); ) // Insert key in the tree Node insertKey(Node root, int key) ( // Return a new node if the tree is empty if (root == null) ( root = new Node(key); return root; ) // Traverse to the right place and insert the node if (key root.key) root.right = insertKey(root.right, key); return root; ) void inorder() ( inorderRec(root); ) // Inorder Traversal void inorderRec(Node root) ( if (root != null) ( inorderRec(root.left); System.out.print(root.key + " -> "); inorderRec(root.right); ) ) void deleteKey(int key) ( root = deleteRec(root, key); ) Node deleteRec(Node root, int key) ( // Return if the tree is empty if (root == null) return root; // Find the node to be deleted if (key root.key) root.right = deleteRec(root.right, key); else ( // If the node is with only one child or no child if (root.left == null) return root.right; else if (root.right == null) return root.left; // If the node has two children // Place the inorder successor in position of the node to be deleted root.key = minValue(root.right); // Delete the inorder successor root.right = deleteRec(root.right, root.key); ) return root; ) // Find the inorder successor int minValue(Node root) ( int minv = root.key; while (root.left != null) ( minv = root.left.key; root = root.left; ) return minv; ) // Driver Program to test above functions public static void main(String() args) ( BinarySearchTree tree = new BinarySearchTree(); tree.insert(8); tree.insert(3); tree.insert(1); tree.insert(6); tree.insert(7); tree.insert(10); tree.insert(14); tree.insert(4); System.out.print("Inorder traversal: "); tree.inorder(); System.out.println("After deleting 10"); tree.deleteKey(10); System.out.print("Inorder traversal: "); tree.inorder(); ) )
// Binary Search Tree operations in C #include #include struct node ( int key; struct node *left, *right; ); // Create a node struct node *newNode(int item) ( struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; ) // Inorder Traversal void inorder(struct node *root) ( if (root != NULL) ( // Traverse left inorder(root->left); // Traverse root printf("%d -> ", root->key); // Traverse right inorder(root->right); ) ) // Insert a node struct node *insert(struct node *node, int key) ( // Return a new node if the tree is empty if (node == NULL) return newNode(key); // Traverse to the right place and insert the node if (key key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; ) // Find the inorder successor struct node *minValueNode(struct node *node) ( struct node *current = node; // Find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; ) // Deleting a node struct node *deleteNode(struct node *root, int key) ( // Return if the tree is empty if (root == NULL) return root; // Find the node to be deleted if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( // If the node is with only one child or no child if (root->left == NULL) ( struct node *temp = root->right; free(root); return temp; ) else if (root->right == NULL) ( struct node *temp = root->left; free(root); return temp; ) // If the node has two children struct node *temp = minValueNode(root->right); // Place the inorder successor in position of the node to be deleted root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); ) return root; ) // Driver code int main() ( struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4); printf("Inorder traversal: "); inorder(root); printf("After deleting 10"); root = deleteNode(root, 10); printf("Inorder traversal: "); inorder(root); )
// Binary Search Tree operations in C++ #include using namespace std; struct node ( int key; struct node *left, *right; ); // Create a node struct node *newNode(int item) ( struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; ) // Inorder Traversal void inorder(struct node *root) ( if (root != NULL) ( // Traverse left inorder(root->left); // Traverse root cout right); ) ) // Insert a node struct node *insert(struct node *node, int key) ( // Return a new node if the tree is empty if (node == NULL) return newNode(key); // Traverse to the right place and insert the node if (key key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; ) // Find the inorder successor struct node *minValueNode(struct node *node) ( struct node *current = node; // Find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; ) // Deleting a node struct node *deleteNode(struct node *root, int key) ( // Return if the tree is empty if (root == NULL) return root; // Find the node to be deleted if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( // If the node is with only one child or no child if (root->left == NULL) ( struct node *temp = root->right; free(root); return temp; ) else if (root->right == NULL) ( struct node *temp = root->left; free(root); return temp; ) // If the node has two children struct node *temp = minValueNode(root->right); // Place the inorder successor in position of the node to be deleted root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); ) return root; ) // Driver code int main() ( struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4); cout << "Inorder traversal: "; inorder(root); cout << "After deleting 10"; root = deleteNode(root, 10); cout << "Inorder traversal: "; inorder(root); )
Zložitosti binárneho vyhľadávacieho stromu
Časová zložitosť
| Prevádzka | Najlepšia zložitosť prípadu | Priemerná zložitosť prípadu | Najhoršia zložitosť prípadu |
| Vyhľadávanie | O (log n) | O (log n) | O (n) |
| Vloženie | O (log n) | O (log n) | O (n) |
| Vymazanie | O (log n) | O (log n) | O (n) |
Tu je n počet uzlov v strome.
Zložitosť vesmíru
Zložitosť priestoru pre všetky operácie je O (n).
Aplikácie binárneho vyhľadávacieho stromu
- Vo viacúrovňovom indexovaní v databáze
- Na dynamické triedenie
- Na správu oblastí virtuálnej pamäte v jadre Unixu
