Дерево двоичного поиска

Содержание

Поисковая операция
Вставить операцию
Операция удаления
Примеры Python, Java и C / C ++
Сложности двоичного дерева поиска
Приложения двоичного дерева поиска

В этом руководстве вы узнаете, как работает двоичное дерево поиска. Также вы найдете рабочие примеры дерева двоичного поиска на языках 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

Если значение найдено, мы возвращаем значение, чтобы оно распространялось на каждом шаге рекурсии, как показано на изображении ниже.

Если вы могли заметить, мы четыре раза вызывали поиск с возвратом (struct node *). Когда мы возвращаем новый узел или NULL, значение возвращается снова и снова, пока поиск (root) не вернет окончательный результат.

Если значение найдено в любом из поддеревьев, оно распространяется вверх, так что в конце возвращается, в противном случае возвращается 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 необходимо удалить,

скопируйте значение его дочернего элемента в узел и удалите дочернее

дерево Final.

Дело III

В третьем случае удаляемый узел имеет двух потомков. В таком случае выполните следующие действия:

Получите неупорядоченного преемника этого узла.
Замените узел на преемника inorder.
Удалите неупорядоченный преемник из исходного положения.

3 подлежит удалению

Скопируйте значение преемника в порядке (4) в узел

Удалите преемника в порядке

Примеры 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)	На)