V tomto kurzu se dozvíte, jak funguje binární vyhledávací strom. Také najdete pracovní příklady binárního vyhledávacího stromu v jazycích C, C ++, Java a Python.
Binární vyhledávací strom je datová struktura, která nám rychle umožňuje udržovat seřazený seznam čísel.
- Říká se tomu binární strom, protože každý uzel stromu má maximálně dvě děti.
- Nazývá se vyhledávací strom, protože jej lze použít k vyhledání přítomnosti čísla v
O(log(n))čase.
Vlastnosti, které oddělují binární vyhledávací strom od běžného binárního stromu, jsou
- Všechny uzly levého podstromu jsou menší než kořenový uzel
- Všechny uzly pravého podstromu jsou více než kořenový uzel
- Oba podstromy každého uzlu jsou také BST, tj. Mají výše uvedené dvě vlastnosti
Strom, který má pravý podstrom s jednou hodnotou menší než kořen, ukazuje, že nejde o platný binární vyhledávací strom
Binární strom vpravo není binární vyhledávací strom, protože pravý podstrom uzlu „3“ obsahuje menší hodnotu.
Ve stromu binárního vyhledávání můžete provádět dvě základní operace:
Vyhledávací operace
Algoritmus závisí na vlastnosti BST, že pokud má každý levý podstrom hodnoty pod kořenem a každý pravý podstrom má hodnoty nad kořenem.
Pokud je hodnota pod kořenem, můžeme s jistotou říci, že hodnota není ve správném podstromu; musíme hledat pouze v levém podstromu a pokud je hodnota nad kořenem, můžeme s jistotou říci, že hodnota není v levém podstromu; musíme hledat pouze ve správném podstromu.
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)
Pokusme se to vizualizovat pomocí diagramu.
4 není nalezen tak, traverz levým podstromem 8 
4 není nalezen tak, traverz pravým podstromem 3 
4 není nalezen tak, traverz levým podstromem 6 4 je nalezen
Pokud je hodnota nalezena, vrátíme ji tak, aby se šířila v každém kroku rekurze, jak je znázorněno na obrázku níže.
Pokud jste si všimli, zavolali jsme čtyřikrát zpětné vyhledávání (strukturovaný uzel *). Když vrátíme nový uzel nebo NULL, hodnota se vrátí znovu a znovu, dokud search (root) nevrátí konečný výsledek.
Pokud je hodnota nalezena v některém z podstromů, šíří se nahoru, aby se nakonec vrátila, jinak se vrátí null
Pokud hodnota není nalezena, nakonec dosáhneme levého nebo pravého potomka uzlu listu, který má hodnotu NULL a bude šířen a vrácen.
Operace vložení
Vložení hodnoty do správné polohy je podobné vyhledávání, protože se snažíme zachovat pravidlo, že levý podstrom je menší než root a pravý podstrom je větší než root.
Stále pokračujeme do pravého podstromu nebo levého podstromu v závislosti na hodnotě a když dosáhneme bodu, levý nebo pravý podstrom je nulový, umístíme tam nový uzel.
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 není tak jednoduchý, jak vypadá. Zkusme si představit, jak přidáme číslo k existujícímu BST.
4 <8 tak, příčně přes levé dítě 8 
4> 3 tak, příčně přes pravé dítě 8 
4 <6 tak, příčně přes levé dítě 6 
Vložte 4 jako levé dítě 6
Připojili jsme uzel, ale stále musíme opustit funkci, aniž bychom způsobili poškození zbytku stromu. To je místo, kde se return node;nakonec hodí. V případě NULL, že je nově vytvořený uzel vrácen a připojen k nadřazenému uzlu, jinak bude stejný uzel vrácen bez jakékoli změny, když jdeme nahoru, dokud se nevrátíme do kořenového adresáře.
Tím zajistíme, že při přesunu zpět do stromu se ostatní připojení uzlů nezmění.
Obrázek ukazující důležitost vrácení kořenového prvku na konci, aby prvky neztratily svoji polohu během kroku rekurze nahoru.
Operace mazání
Existují tři případy odstranění uzlu z binárního vyhledávacího stromu.
Případ I
V prvním případě je uzlem, který má být odstraněn, listový uzel. V takovém případě jednoduše odstraňte uzel ze stromu.
4 má být odstraněn 
Vymazat uzel
Případ II
V druhém případě má uzel, který má být odstraněn, jediný podřízený uzel. V takovém případě postupujte podle následujících pokynů:
- Nahraďte tento uzel jeho podřízeným uzlem.
- Odeberte podřízený uzel z jeho původní polohy.
6 má být odstraněn, 
zkopírujte hodnotu svého podřízeného prvku do uzlu a odstraňte podřízený 
finální strom
Případ III
Ve třetím případě má uzel, který má být odstraněn, dvě podřízené položky. V takovém případě postupujte podle následujících pokynů:
- Získejte inorder nástupce tohoto uzlu.
- Nahraďte uzel inorderovým nástupcem.
- Odstraňte neuspořádaného nástupce z jeho původní polohy.
3 má být odstraněn Zkopírujte hodnotu následného pořadí (4) do uzlu 
Odstranit následného pořadí
Python, Java a C / C ++ příklady
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); )
Složitosti binárního stromu vyhledávání
Časová složitost
| Úkon | Nejlepší složitost případu | Průměrná složitost případu | Složitost nejhoršího případu |
| Vyhledávání | O (log n) | O (log n) | Na) |
| Vložení | O (log n) | O (log n) | Na) |
| Vymazání | O (log n) | O (log n) | Na) |
Zde n je počet uzlů ve stromu.
Složitost vesmíru
Složitost prostoru pro všechny operace je O (n).
Binární vyhledávací aplikace stromu
- Ve víceúrovňovém indexování v databázi
- Pro dynamické třídění
- Pro správu oblastí virtuální paměti v unixovém jádře
