U ovom vodiču naučit ćete kako radi Binarno stablo pretraživanja. Također ćete pronaći radne primjere binarnog stabla pretraživanja na C, C ++, Java i Python.
Stablo binarnog pretraživanja struktura je podataka koja nam brzo omogućuje održavanje razvrstanog popisa brojeva.
- Zove se binarno stablo jer svaki čvor stabla ima najviše dvoje djece.
- Naziva se stablom pretraživanja jer se pomoću njega može tražiti prisutnost broja na
O(log(n))vrijeme.
Svojstva koja razdvajaju binarno stablo pretraživanja od redovitog binarnog stabla je
- Svi čvorovi lijevog podstabla manji su od korijenskog čvora
- Svi čvorovi desnog podstabla više su od korijenskog čvora
- Oba podstabla svakog čvora su ujedno i BST, tj. Imaju gore navedena dva svojstva
Prikazuje se stablo koje ima desno podstablo s jednom vrijednošću manjom od korijena da demonstrira da nije valjano binarno stablo pretraživanja
Binarno stablo s desne strane nije binarno stablo pretraživanja, jer desno podstablo čvora "3" sadrži vrijednost manju od njega.
Dvije su osnovne operacije koje možete izvesti na binarnom stablu pretraživanja:
Operacija pretraživanja
Algoritam ovisi o svojstvu BST-a da ako svako lijevo podstablo ima vrijednosti ispod korijena, a svako desno podstablo ima vrijednosti iznad korijena.
Ako je vrijednost ispod korijena, možemo sa sigurnošću reći da vrijednost nije u pravom podstablu; trebamo pretraživati samo u lijevom podstablu, a ako je vrijednost iznad korijena, možemo sa sigurnošću reći da vrijednost nije u lijevom podstablu; trebamo tražiti samo u pravom podstablu.
Algoritam:
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)
Pokušajmo to vizualizirati dijagramom.
4 nije pronađen, prelazak kroz lijevo podstablo 8 
4 nije pronađen, prelazak kroz desno poddrvo 3 
4 nije pronađen, pronađen je poprek kroz lijevo podstablo 6 4
Ako je vrijednost pronađena, vraćamo vrijednost tako da se širi u svakom koraku rekurzije kao što je prikazano na donjoj slici.
Ako ste mogli primijetiti, četiri smo puta pozvali return search (struct node *). Kada vratimo ili novi čvor ili NULL, vrijednost se vraća iznova i iznova dok pretraživanje (root) ne vrati konačni rezultat.
Ako se vrijednost pronađe u bilo kojem od podstabala, ona se širi tako da se na kraju vraća, u suprotnom se vraća null
Ako vrijednost nije pronađena, na kraju dolazimo do lijevog ili desnog podređenog čvora lista koji je NULL i on se širi i vraća.
Umetni rad
Umetanje vrijednosti u ispravan položaj slično je pretraživanju jer pokušavamo zadržati pravilo da je lijevo podstablo manje od korijena, a desno poddrvo veće od korijena.
Nastavljamo ići prema desnom ili lijevom podstablu, ovisno o vrijednosti, a kada dođemo do točke lijevo ili desno podstablo je null, tamo postavljamo novi čvor.
Algoritam:
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;
Algoritam nije tako jednostavan kako izgleda. Pokušajmo vizualizirati kako dodamo broj postojećem BST-u.
4 <8 dakle, poprečno kroz lijevo dijete od 8 
4> 3 dakle, poprečno kroz desno dijete od 8 
4 <6 tako, poprečno kroz lijevo dijete od 6 
Umetnite 4 kao lijevo dijete od 6 godina
Priključili smo čvor, ali još uvijek moramo izaći iz funkcije bez oštećenja ostatka stabla. Tu vam return node;na kraju dobro dođe kraj. U slučaju NULL, novostvoreni čvor se vraća i priključuje nadređenom čvoru, inače se isti čvor vraća bez ikakvih promjena dok se penjemo dok se ne vratimo u korijen.
To osigurava da se, dok se vraćamo prema stablu, veze ostalih čvorova ne promijene.
Slika koja prikazuje važnost vraćanja korijenskog elementa na kraj kako elementi ne bi izgubili svoj položaj tijekom koraka rekurzije prema gore.
Operacija brisanja
Tri su slučaja za brisanje čvora s binarnog stabla pretraživanja.
Slučaj I
U prvom slučaju, čvor koji se treba izbrisati je čvor lista. U takvom slučaju, jednostavno izbrišite čvor sa stabla.
4 se briše 
Izbrišite čvor
Slučaj II
U drugom slučaju, čvor koji treba izbrisati ima jedan podređeni čvor. U tom slučaju slijedite korake u nastavku:
- Zamijenite taj čvor njegovim podređenim čvorom.
- Uklonite podređeni čvor s izvornog položaja.
6 treba izbrisati, 
kopirati vrijednost njegovog podređenog u čvor i izbrisati podređeno 
završno stablo
Slučaj III
U trećem slučaju, čvor koji se briše ima dvoje djece. U tom slučaju slijedite korake u nastavku:
- Nabavite inorder nasljednika tog čvora.
- Zamijenite čvor s inorder nasljednikom.
- Uklonite nasljednika inorder s izvornog položaja.
3 treba izbrisati. Kopirajte vrijednost nasljednika inorder (4) u čvor 
Izbrišite nasljednika inorder-a
Primjeri Pythona, Java i 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); )
Složenost stabla binarnog pretraživanja
Složenost vremena
| Operacija | Složenost najboljeg slučaja | Prosječna složenost predmeta | Najgora složenost slučaja |
| traži | O (zapisnik n) | O (zapisnik n) | Na) |
| Umetanje | O (zapisnik n) | O (zapisnik n) | Na) |
| Brisanje | O (zapisnik n) | O (zapisnik n) | Na) |
Ovdje je n broj čvorova u stablu.
Složenost prostora
Složenost prostora za sve operacije je O (n).
Aplikacije binarnog stabla pretraživanja
- U višerazinskom indeksiranju u bazi podataka
- Za dinamičko sortiranje
- Za upravljanje područjima virtualne memorije u Unix kernelu
