В този урок ще научите как работи бинарното дърво за търсене. Също така ще намерите работещи примери за двоично дърво за търсене в C, C ++, Java и Python.
Двоично дърво за търсене е структура от данни, която бързо ни позволява да поддържаме сортиран списък с числа.
- Нарича се двоично дърво, тъй като всеки възел на дърво има максимум две деца.
- Нарича се дърво за търсене, защото може да се използва за търсене на присъствието на число във
O(log(n))времето.
Свойствата, които разделят бинарното дърво за търсене от обикновеното двоично дърво е
- Всички възли на лявото поддърво са по-малки от кореновия възел
- Всички възли на дясно поддърво са повече от коренния възел
- И двете поддървета на всеки възел също са BST, т.е. те имат горните две свойства
Показва се дърво с дясно поддърво с една стойност, по-малка от корена, за да покаже, че не е валидно бинарно дърво за търсене
Двоичното дърво вдясно не е двоично дърво за търсене, защото дясното поддърво на възела "3" съдържа стойност, по-малка от него.
Има две основни операции, които можете да извършите върху двоично дърво за търсене:
Операция за търсене
Алгоритъмът зависи от свойството на BST, че ако всяко ляво поддърво има стойности под корена и всяко дясно поддърво има стойности над корена.
Ако стойността е под корена, със сигурност можем да кажем, че стойността не е в правилното поддърво; трябва да търсим само в лявото поддърво и ако стойността е над корена, можем да кажем със сигурност, че стойността не е в лявото поддърво; трябва да търсим само в правилното поддърво.
Алгоритъм:
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)
Нека се опитаме да визуализираме това с диаграма.
4 не е намерен така, пресичане през лявото поддърво на 8 
4 не е намерено така, пресичане през дясното поддърво на 3 
4 не е намерено така, преминаването през лявото поддърво на 6 4 е намерено
Ако стойността бъде намерена, ние връщаме стойността, така че тя да се разпространява във всяка стъпка на рекурсия, както е показано на изображението по-долу.
Ако може би сте забелязали, четири пъти сме извикали return search (struct node *). Когато върнем или новия възел, или NULL, стойността се връща отново и отново, докато търсенето (корен) върне крайния резултат.
Ако стойността бъде намерена в някое от поддърветата, тя се разпространява нагоре, така че в крайна сметка тя се връща, в противен случай се връща null
Ако стойността не бъде намерена, в крайна сметка достигаме до лявото или дясното дете на листен възел, който е NULL, и той се разпространява и връща.
Вмъкване на операция
Вмъкването на стойност в правилната позиция е подобно на търсенето, защото се опитваме да поддържаме правилото, че лявото поддърво е по-малко от рут, а дясното поддърво е по-голямо от корен.
Продължаваме да се движим към дясно подляво или ляво поддърво в зависимост от стойността и когато достигнем точка лявото или дясното поддърво е нула, поставяме новия възел там.
Алгоритъм:
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;
Алгоритъмът не е толкова прост, колкото изглежда. Нека се опитаме да визуализираме как добавяме число към съществуващ BST.
4 <8 така, напречно през лявото дете на 8 
4> 3 така, напречно през дясното дете на 8 
4 <6 така, напречно през лявото дете на 6 
Вмъкнете 4 като ляво дете на 6
Прикрепихме възела, но все пак трябва да излезем от функцията, без да нанасяме щети на останалата част от дървото. Това е мястото, където return node;в края е полезно. В случай на NULL, новосъздаденият възел се връща и прикачва към родителския възел, в противен случай същият възел се връща без никаква промяна, докато вървим нагоре, докато не се върнем към корена.
Това гарантира, че докато се връщаме нагоре по дървото, другите връзки на възли не се променят.
Изображение, показващо важността на връщането на кореновия елемент в края, така че елементите да не загубят позицията си по време на стъпката на рекурсия нагоре.
Операция по изтриване
Има три случая за изтриване на възел от бинарно дърво за търсене.
Дело I
В първия случай възелът, който трябва да бъде изтрит, е листният възел. В такъв случай просто изтрийте възела от дървото.
4 трябва да се изтрие 
Изтрийте възела
Дело II
Във втория случай възелът, който трябва да бъде изтрит, има единичен дъщерен възел. В такъв случай следвайте стъпките по-долу:
- Заменете този възел с неговия дъщерен възел.
- Премахнете дъщерния възел от първоначалното му положение.
6 трябва да бъде изтрит, 
копирайте стойността на неговото дъщерно устройство към възела и изтрийте дъщерното 
окончателно дърво
Дело III
В третия случай възелът, който трябва да бъде изтрит, има две деца. В такъв случай следвайте стъпките по-долу:
- Вземете наследника на inorder на този възел.
- Заменете възела с наследник inorder.
- Премахнете наследника на inorder от първоначалното му положение.
3 трябва да се изтрие Копирайте стойността на наследника inorder (4) във възела 
Изтрийте наследника inorder
Примери за Python, Java и 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); )
Сложности на бинарното дърво за търсене
Сложност във времето
| Операция | Най-добрата сложност | Средна сложност на случая | Сложност на най-лошия случай |
| Търсене | O (log n) | O (log n) | На) |
| Вмъкване | O (log n) | O (log n) | На) |
| Изтриване | O (log n) | O (log n) | На) |
Тук n е броят на възлите в дървото.
Сложност на пространството
Сложността на пространството за всички операции е O (n).
Приложения за бинарно дърво за търсене
- При многостепенно индексиране в базата данни
- За динамично сортиране
- За управление на области на виртуална памет в ядрото на Unix
