Дерево двоичного поиска
В этом руководстве вы узнаете, как работает двоичное дерево поиска. Здесь же собраны примеры реализации дерева двоичного поиска на Си, C++, Java и Python.
Дерево двоичного поиска — это структура данных, которая позволяет быстро работать с отсортированном списком чисел.
- Дерево двоичное, потому что у каждого узла не более двух дочерних элементов.
- Дерево поиска, потому что его можно использовать для проверки вхождения числа — за время
O(log(n)).
Чем отличается от обычного двоичного дерева
- Все узлы левого поддерева меньше корневого узла.
- Все узлы правого поддерева больше корневого узла.
- Оба поддерева каждого узла тоже являются деревьями двоичного поиска, т. е. также обладают первыми двумя свойствами.
У правого дерева есть поддерево со значением 2, которое меньше, чем корень 3 — таким дерево двоичного поиска быть не может.
Операции с двоичным деревом поиска
Поиск элемента
Сложность в среднем: O(log n)
Сложность в худшем случае: O(n)
Алгоритм зависит от свойств дерева: у каждого левого поддерева есть значения, которые ниже корня или у каждого правого поддерева есть значения, которые выше корня.
Если значение ниже корня, мы можем точно сказать, что оно находится не в правильном поддереве. Тогда нам нужно искать только в левом поддереве. А если значение выше корня, можно точно сказать, что значения нет в левом поддереве. Тогда ищем только в правом поддереве.
Алгоритм:
If root == NULL
return NULL;
If number == root->data
return root->data;
If number < root->data
return search(root->left)
If number > root->data
return search(root->right)
Изобразим это на диаграмме.
• Не нашли 4 → идем по левому поддереву корня 8
• Не нашли 4 → идем по левому поддереву корня 3
• Не нашли 4 → идем по левому поддереву корня 6
• Нашли 4 — ура.
Если мы нашли значение, мы возвращаем его так, чтобы оно распространялось на каждом шаге рекурсии — рассмотрите рисунок ниже.
Как вы могли заметить, мы четыре раза вызывали search(struct node*). Когда мы возвращаем новый узел или NULL, значение возвращается снова и снова, пока search(root) не вернет окончательный результат.
Если мы не нашли значение, значит, мы достигли левого или правого дочернего элемента листового узла, который имеет значение NULL — это значение также рекурсивно распространяется и возвращается.
Вставка элемента
Сложность в среднем: O(log n)
Сложность в худшем случае: ΘO(n)
Операция вставки значения похожа на поиск элемента. Мы также придерживаемся правила: левое поддерево меньше корня, правое поддерево — больше.
Мы продолжаем переходить либо к правому поддереву, либо к левому поддереву в зависимости от значения узла, и когда достигаем точки, в которой левое или правое поддерево имеет значение NULL, помещаем туда новый узел.
Алгоритм:
If node == NULL
return createNode(data)
if (data < node->data)
node->left = insert(node->left, data);
else if (data > node->data)
node->right = insert(node->right, data);
return node;
Алгоритм не такой простой, как может показаться на первый взгляд. Давайте визуализируем процесс.
• 4 < 8 → идем через левого «ребенка» 8.
• 4 > 3 → идем через правого «ребенка» 3.
• 4 < 6 → идем через левого «ребенка» 6.
• Левого «ребенка» у 6 нет → вставляем 4 как левый дочерний элемент 6.
Мы вставили узел в нужное место, но нам всё еще нужно выйти из функции, не повредив при этом остальную часть дерева. Здесь пригодится return node;. В случае с NULL, вновь созданный узел возвращается и присоединяется к родительскому узлу, иначе тот же узел возвращается без каких-либо изменений по мере продвижения вверх, пока мы не вернемся к корню.
Таким образом, когда мы будем двигаться обратно вверх по дереву, связи других узлов не изменятся.
Корень возвращаем в конце — так ничего не сломается.
Удаление элемента
Сложность в среднем: O(log n)
Сложность в худшем случае: O(n)
Всего может быть три случая при удаление элемента из дерева двоичного поиска. Давайте рассмотрим каждый.
Случай I: лист
Первый случай — когда нужно удалить листовой элемент. Просто удаляем узел из дерева.
• Нужно удалить 4.
• Просто удалили узел.
Случай II: есть дочерний элемент
Во втором случае у узла, который мы хотим удалить, есть один дочерний узел. В этом случае действуем так:
- Заменяем удаляемый узел на дочерний узел.
- Удаляем дочерний узел.
• Нужно удалить 6.
• Меняем 6 на 7 и удаляем узел 7.
•Нужный узел удален.
Случай III: два дочерних элемента
Если у узла, который мы хотим удалить, есть два потомка, делаем так:
- Получаем значение inorder-преемника этого узла.
- Заменяем удаляем узел на inorder-преемника.
- Удаляем inorder-преемника.
• Хотим удалить 3.
• Копируем значение inorder-преемника — 4.
• Удаляем inorder-преемника.
Реализация на языках программирования
Python
# Операции с двоичным деревом поиска на Python
# Создаем узел
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
# Отсортированный (inorder) обход
def inorder(root):
if root is not None:
# Обходим левое поддерево
inorder(root.left)
# Обходим корень
print(str(root.key) + "->", end=' ')
# Обходим правое поддерево
inorder(root.right)
# Вставка элемента
def insert(node, key):
# Возвращаем новый узел, если дерево пустое
if node is None:
return Node(key)
# Идем в нужное место и вставляет узел
if key < node.key:
node.left = insert(node.left, key)
else:
node.right = insert(node.right, key)
return node
# Поиск inorder-преемника
def minValueNode(node):
current = node
# Найдем крайний левый лист — он и будет inorder-преемником
while(current.left is not None):
current = current.left
return current
# Удаление узла
def deleteNode(root, key):
# Возвращаем, если дерево пустое
if root is None:
return root
# Найдем узел, который нужно удалить
if key < root.key:
root.left = deleteNode(root.left, key)
elif(key > root.key):
root.right = deleteNode(root.right, key)
else:
# Если у узла только один дочерний узел или вообще их нет
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
# Если у узла два дочерних узла,
# помещаем центрированного преемника
# на место узла, который нужно удалить
temp = minValueNode(root.right)
root.key = temp.key
# Удаляем inorder-преемниа
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("Отсортированный обход: ", end=' ')
inorder(root)
print("\nПосле удаления 10")
root = deleteNode(root, 10)
print("Отсортированный обход: ", end=' ')
inorder(root)Java
// Операции с двоичным деревом поиска на 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);
}
// Вставляем в дерево элемент
Node insertKey(Node root, int key) {
// Возвращаем новый узел, если дерево пустое
if (root == null) {
root = new Node(key);
return root;
}
// Идем в нужное место и вставляем узел
if (key < root.key)
root.left = insertKey(root.left, key);
else if (key > root.key)
root.right = insertKey(root.right, key);
return root;
}
void inorder() {
inorderRec(root);
}
// Отсортированный (inorder) обход
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) {
// Возвращаем, если дерево пустое
if (root == null)
return root;
// Ищем узел, который нужно удалить
if (key < root.key)
root.left = deleteRec(root.left, key);
else if (key > root.key)
root.right = deleteRec(root.right, key);
else {
// Если у узла только один дочерний элемент или их вообще нет
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
// Если у узла два дочерних элемента
// Помещаем inorder-преемника на место узла, который хотим удалить
root.key = minValue(root.right);
// Удаляем inorder-преемника
root.right = deleteRec(root.right, root.key);
}
return root;
}
// Ищем inorder-преемника
int minValue(Node root) {
int minv = root.key;
while (root.left != null) {
minv = root.left.key;
root = root.left;
}
return minv;
}
// Тестим функции
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("Отсортированный обход: ");
tree.inorder();
System.out.println("\n\nПосле удаления 10");
tree.deleteKey(10);
System.out.print("Отсортированный обход: ");
tree.inorder();
}
}C
// Операции с двоичным деревом поиска на C
#include <stdio.h>
#include <stdlib.h>
struct node {
int key;
struct node *left, *right;
};
// Создаем узел
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) обход
void inorder(struct node *root) {
if (root != NULL) {
// Обходимо лево
inorder(root->left);
// Обходим корень
printf("%d -> ", root->key);
// Обходимо право
inorder(root->right);
}
}
// Вставка узла
struct node *insert(struct node *node, int key) {
// Возвращаем новый узел, если дерево пустое
if (node == NULL) return newNode(key);
// Проходим в нужное место и вставляем узел
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
return node;
}
// Поиск inorder-преемника
struct node *minValueNode(struct node *node) {
struct node *current = node;
// Находим крайний левый лист — он и будет inorder-преемником
while (current && current->left != NULL)
current = current->left;
return current;
}
// Удаляем узел
struct node *deleteNode(struct node *root, int key) {
// Возвращаем, если дерево пустое
if (root == NULL) return root;
// Ищем узел, который нужно удалить
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else {
// Если у узла только один дочерний элемент или их вообще нет
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;
}
// Если у узла два дочерних элемента
struct node *temp = minValueNode(root->right);
// Помещаем inorder-преемника на место узла, который хотим удалить
root->key = temp->key;
// Удаляем inorder-преемника
root->right = deleteNode(root->right, temp->key);
}
return root;
}
// Тестим функции
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(root);
printf("\nПосле удаления 10\n");
root = deleteNode(root, 10);
printf("Отсортированный обход: ");
inorder(root);
}C++
// Операции с двоичным деревом поиска на C++
#include <iostream>
using namespace std;
struct node {
int key;
struct node *left, *right;
};
// Создаем узел
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) обход
void inorder(struct node *root) {
if (root != NULL) {
// Обходим лево
inorder(root->left);
// Обходим корень
cout << root->key << " -> ";
// Обходим право
inorder(root->right);
}
}
// Вставка узла
struct node *insert(struct node *node, int key) {
// Возвращаем новый узел, если дерево пустое
if (node == NULL) return newNode(key);
// Проходим в нужное место и вставляет узел
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
return node;
}
// Поис inorder-преемника
struct node *minValueNode(struct node *node) {
struct node *current = node;
// Ищем крайний левый лист — он и будет inorder-преемником
while (current && current->left != NULL)
current = current->left;
return current;
}
// Удаление узла
struct node *deleteNode(struct node *root, int key) {
// Возвращаем, если дерево пустое
if (root == NULL) return root;
// Ищем узел, который хотим удалить
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else {
// Если у узла один дочерний элемент или их нет
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;
}
// Если у узла два дочерних элемента
struct node *temp = minValueNode(root->right);
// Помещаем inorder-преемника на место узла, который хотим удалить
root->key = temp->key;
// Удаляем inorder-преемника
root->right = deleteNode(root->right, temp->key);
}
return root;
}
// Тестим функции
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(root);
cout << "\nПосле удаления 10 10\n";
root = deleteNode(root, 10);
cout << "Отсортированный обход: ";
inorder(root);
}Где используется
- При многоуровневой индексации в базе данных.
- Для динамической сортировки.
- Для управления областями виртуальной памяти в ядре Unix.
