W tym samouczku dowiesz się, jak działa drzewo wyszukiwania binarnego. Znajdziesz również działające przykłady Binary Search Tree w językach C, C ++, Java i Python.
Drzewo wyszukiwania binarnego to struktura danych, która pozwala nam szybko utrzymywać posortowaną listę liczb.
- Nazywa się to drzewem binarnym, ponieważ każdy węzeł drzewa ma maksymalnie dwoje dzieci.
- Nazywa się to drzewem wyszukiwania, ponieważ można go używać do wyszukiwania obecności liczby w
O(log(n))czasie.
Właściwości oddzielające drzewo wyszukiwania binarnego od zwykłego drzewa binarnego to
- Wszystkie węzły lewego poddrzewa są mniejsze niż węzeł główny
- Wszystkie węzły prawego poddrzewa są czymś więcej niż węzłem głównym
- Oba poddrzewa każdego węzła są również BST, tj. Mają powyższe dwie właściwości
Drzewo mające prawe poddrzewo z jedną wartością mniejszą niż korzeń jest pokazane, aby zademonstrować, że nie jest to poprawne drzewo wyszukiwania binarnego
Drzewo binarne po prawej stronie nie jest drzewem wyszukiwania binarnego, ponieważ prawe poddrzewo węzła „3” zawiera wartość mniejszą od niego.
Istnieją dwie podstawowe operacje, które można wykonać na drzewie wyszukiwania binarnego:
Operacja wyszukiwania
Algorytm zależy od właściwości BST, że jeśli każde lewe poddrzewo ma wartości poniżej pierwiastka, a każde prawe poddrzewo ma wartości powyżej pierwiastka.
Jeśli wartość jest poniżej korzenia, możemy z całą pewnością stwierdzić, że wartość nie znajduje się w prawym poddrzewie; musimy szukać tylko w lewym poddrzewie i jeśli wartość jest powyżej korzenia, możemy z całą pewnością stwierdzić, że wartość nie znajduje się w lewym poddrzewie; musimy szukać tylko w prawym poddrzewie.
Algorytm:
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)
Spróbujmy to zobrazować za pomocą diagramu.
4 nie jest znalezione, więc, nie znaleziono trawersu przez lewe poddrzewo 8 
4, więc nie znaleziono trawersu przez prawe poddrzewo 3 
4, więc znajduje się trawers przez lewe poddrzewo 6 4
Jeśli wartość zostanie znaleziona, zwracamy wartość, aby była propagowana w każdym kroku rekurencji, jak pokazano na poniższym obrazku.
Jeśli mogłeś zauważyć, czterokrotnie wywołaliśmy funkcję return search (struct node *). Kiedy zwracamy nowy węzeł lub NULL, wartość jest zwracana wielokrotnie, aż funkcja search (root) zwróci wynik końcowy.
Jeśli wartość zostanie znaleziona w którymkolwiek z poddrzew, jest propagowana w górę, aby na końcu została zwrócona, w przeciwnym razie zwracana jest wartość null
Jeśli wartość nie zostanie znaleziona, w końcu docieramy do lewego lub prawego dziecka węzła-liścia, który jest NULL, i jest on propagowany i zwracany.
Operacja wstawiania
Wstawianie wartości we właściwej pozycji jest podobne do wyszukiwania, ponieważ staramy się zachować regułę, że lewe poddrzewo jest mniejsze niż korzeń, a prawe poddrzewo większe niż korzeń.
W zależności od wartości kontynuujemy przechodzenie do prawego lub lewego poddrzewa, a kiedy osiągniemy punkt, w którym lewe lub prawe poddrzewo jest zerowe, umieszczamy tam nowy węzeł.
Algorytm:
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;
Algorytm nie jest tak prosty, jak się wydaje. Spróbujmy sobie wyobrazić, jak dodajemy liczbę do istniejącego BST.
4 <8 tak, poprzecznie przez lewe dziecko w wieku 8 
4> 3 tak, poprzecznie przez prawe dziecko w wieku 8 
4 <6 tak, poprzecznie przez lewe dziecko w wieku 6 lat 
Wstaw 4 jako lewe dziecko w wieku 6 lat
Dołączyliśmy węzeł, ale nadal musimy wyjść z funkcji, nie uszkadzając reszty drzewa. Tu return node;przydaje się koniec. W przypadku NULLnowo utworzonego węzła jest zwracany i dołączany do węzła nadrzędnego, w przeciwnym razie ten sam węzeł jest zwracany bez żadnych zmian, gdy idziemy w górę, aż wrócimy do katalogu głównego.
Daje to pewność, że w miarę przesuwania się w górę drzewa inne połączenia węzłów nie ulegną zmianie.
Obraz pokazujący, jak ważne jest zwrócenie elementu głównego na końcu, aby elementy nie utraciły swojej pozycji podczas kroku rekursji w górę.
Operacja usunięcia
Istnieją trzy przypadki usunięcia węzła z binarnego drzewa wyszukiwania.
Przypadek I
W pierwszym przypadku węzłem do usunięcia jest węzeł liścia. W takim przypadku po prostu usuń węzeł z drzewa.
4 ma zostać usunięty 
Usuń węzeł
Przypadek II
W drugim przypadku usuwany węzeł ma jeden węzeł podrzędny. W takim przypadku wykonaj poniższe czynności:
- Zastąp ten węzeł jego węzłem podrzędnym.
- Usuń węzeł potomny z jego pierwotnej pozycji.
6 ma zostać usunięty, 
skopiuj wartość jego potomka do węzła i usuń potomne 
drzewo końcowe
Przypadek III
W trzecim przypadku usuwany węzeł ma dwoje dzieci. W takim przypadku wykonaj poniższe czynności:
- Pobierz następcę w kolejności tego węzła.
- Zastąp węzeł następcą w kolejności.
- Usuń następcę wewnętrznego z jego pierwotnej pozycji.
3 ma zostać usunięty Skopiuj wartość następcy w kolejności (4) do węzła 
Usuń następcę w kolejności
Przykłady w Pythonie, Javie 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); )
Złożoność drzewa wyszukiwania binarnego
Złożoność czasowa
| Operacja | Najlepsza złożoność przypadku | Średnia złożoność przypadku | Najgorsza złożoność przypadku |
| Szukaj | O (log n) | O (log n) | Na) |
| Wprowadzenie | O (log n) | O (log n) | Na) |
| Usunięcie | O (log n) | O (log n) | Na) |
Tutaj n to liczba węzłów w drzewie.
Złożoność przestrzeni
Złożoność przestrzeni dla wszystkich operacji wynosi O (n).
Aplikacje w drzewie wyszukiwania binarnego
- W wielopoziomowym indeksowaniu w bazie danych
- Do dynamicznego sortowania
- Do zarządzania obszarami pamięci wirtualnej w jądrze Uniksa
