Каков принцип работы дерева поиска

# Дерево поиска: принципы работы

Дерево поиска (бинарное дерево поиска, BST) — это фундаментальная структура данных, которая обеспечивает эффективный поиск, вставку и удаление элементов за O(log n) в среднем случае.

Основной принцип

Дерево поиска строится на следующем свойстве: для каждого узла все значения в левом поддереве меньше значения узла, а все значения в правом поддереве больше. Это упорядочение позволяет исключать половину оставшихся элементов на каждом шаге поиска.

Базовая структура

class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

Операция поиска

Поиск работает как двоичный поиск в отсортированном массиве, но без необходимости доступа к индексам:

def search(root, target):
    if root is None:
        return False
    
    if root.val == target:
        return True
    elif target < root.val:
        return search(root.left, target)
    else:
        return search(root.right, target)

Время выполнения: O(log n) в сбалансированном дереве, O(n) в худшем случае (при вырождении в список).

Вставка элемента

Новые элементы добавляются как листья, следуя свойству упорядочения:

def insert(root, val):
    if root is None:
        return TreeNode(val)
    
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    
    return root

Удаление элемента

Удаление — самая сложная операция. Возможны три случая:

• Узел без детей: просто удаляем
• Узел с одним ребёнком: заменяем узел его ребёнком
• Узел с двумя детьми: ищем наименьший элемент в правом поддереве (inorder successor) и заменяем удаляемый узел на него

def delete(root, val):
    if root is None:
        return None
    
    if val < root.val:
        root.left = delete(root.left, val)
    elif val > root.val:
        root.right = delete(root.right, val)
    else:
        # Узел найден
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        
        # Два ребёнка: найти inorder successor
        min_larger_node = find_min(root.right)
        root.val = min_larger_node.val
        root.right = delete(root.right, min_larger_node.val)
    
    return root

def find_min(node):
    while node.left:
        node = node.left
    return node

Обход дерева

In-order обход (левое поддерево → узел → правое) даёт элементы в отсортированном порядке:

def inorder(root):
    if root is None:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

Сложность операций

Проблема разбалансировки

Если последовательно вставлять отсортированные данные, дерево вырождается в список и теряет эффективность. Для решения используют самобалансирующиеся деревья (AVL, Red-Black Tree).

# Пример вырождения
bst = None
for val in [1, 2, 3, 4, 5]:  # Отсортированные значения
    bst = insert(bst, val)
# Результат: 1 -> 2 -> 3 -> 4 -> 5 (список!)

Практическое применение

Деревья поиска используются в:

• Базах данных для индексирования (B-trees, B+ trees)
• Файловых системах
• TreeMap в Java, SortedDict в Python
• Приоритетных очередях (heap-based)