У цьому посібнику ви дізнаєтесь, як працює бінарне дерево пошуку. Також ви знайдете робочі приклади бінарного дерева пошуку на мовах 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 return (struct node *). Коли ми повертаємо або новий вузол, або NULL, значення повертається знову і знову, поки пошук (root) не поверне кінцевий результат.
Якщо значення знайдено в будь-якому з піддерев, воно розповсюджується таким чином, що в підсумку воно повертається, інакше повертається 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 6 
Вставте 4 як ліву дитину 6
Ми приєднали вузол, але нам все одно доведеться вийти з функції, не завдаючи шкоди решті дерева. Тут return node;кінець пригодиться. У випадку NULL, щойно створений вузол повертається і приєднується до батьківського вузла, інакше той самий вузол повертається без будь-яких змін, коли ми піднімаємося вгору, доки ми не повернемося до кореня.
Це гарантує, що під час повернення вгору по дереву інші підключення вузлів не змінюються.
Зображення, що показує важливість повернення кореневого елемента в кінці, щоб елементи не втратили своє положення під час кроку рекурсії вгору.
Операція видалення
Є три випадки видалення вузла з бінарного дерева пошуку.
Справа I
У першому випадку вузлом, який потрібно видалити, є листовий вузол. У такому випадку просто видаліть вузол з дерева.
4 слід видалити 
Видалити вузол
Справа II
У другому випадку вузол, який потрібно видалити, має єдиний дочірній вузол. У такому випадку виконайте наведені нижче дії:
- Замініть цей вузол на його дочірній вузол.
- Видаліть дочірній вузол з початкового положення.
6 слід видалити, 
скопіюйте значення його дочірнього елемента на вузол і видаліть дочірнє 
остаточне дерево
Справа III
У третьому випадку вузол, який потрібно видалити, має двох дітей. У такому випадку виконайте наведені нижче дії:
- Отримайте наступника 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 (журнал n) | O (журнал n) | O (n) |
| Вставка | O (журнал n) | O (журнал n) | O (n) |
| Видалення | O (журнал n) | O (журнал n) | O (n) |
Тут n - кількість вузлів у дереві.
Складність простору
Складність простору для всіх операцій - O (n).
Бінарні програми пошуку дерева
- У багаторівневій індексації в базі даних
- Для динамічного сортування
- Для управління областями віртуальної пам'яті в ядрі Unix
