Деревья и двоичные деревья поиска: практическое руководство

Что такое дерево и BST

Дерево — это структура из узлов, где у каждого узла есть родитель (кроме корня) и ноль или больше потомков. Циклов нет. Так устроены файловая система, DOM в браузере, меню сайта.

Двоичное дерево поиска (BST) — дерево, где у каждого узла не больше двух потомков и выполняется правило:

• все ключи в левом поддереве меньше ключа узла;
• все ключи в правом поддереве больше.

Благодаря этому правилу на каждом шаге поиска вы отбрасываете половину оставшегося дерева — как при бинарном поиске в отсортированном массиве. Отличие в том, что вставка и удаление не требуют сдвигать элементы.

Реализация: вставка и поиск

Минимальная реализация на Python. Дубликаты здесь игнорируются — это нужно решить заранее.

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root

def search(root, key):
    while root is not None and root.key != key:
        root = root.left if key < root.key else root.right
    return root

Вставка всегда добавляет новый узел как лист: спускаемся по правилу «меньше — налево, больше — направо», пока не найдём пустое место.

Удаление: три случая

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

1. У узла нет потомков — просто убираем его.
2. Один потомок — подставляем потомка на место узла.
3. Два потомка — находим in-order преемника (минимальный ключ в правом поддереве), копируем его ключ в узел и удаляем преемника из правого поддерева.

def delete(root, key):
    if root is None:
        return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        succ = root.right
        while succ.left is not None:
            succ = succ.left
        root.key = succ.key
        root.right = delete(root.right, succ.key)
    return root

У преемника никогда нет левого потомка, поэтому его удаление сводится к случаю 1 или 2.

Обходы дерева

def inorder(root):
    if root is not None:
        yield from inorder(root.left)
        yield root.key
        yield from inorder(root.right)

Если in-order обход вашего дерева выдаёт неотсортированную последовательность — в реализации ошибка. Это удобная проверка для тестов.

Почему важен баланс

Скорость BST зависит от высоты дерева. В сбалансированном дереве высота растёт как log n, и поиск, вставка, удаление работают за O(log n).

Но если вставлять уже отсортированные данные (1, 2, 3, 4…), каждый новый узел уходит вправо, и дерево вырождается в связный список. Операции становятся O(n), а рекурсивные функции рискуют упереться в лимит глубины стека.

На практике данные часто приходят отсортированными: id из базы, даты, импорт из таблицы. Поэтому «голый» BST редко используют в продакшене.

AVL и красно-чёрные деревья

Самобалансирующиеся деревья после каждой вставки и удаления восстанавливают баланс с помощью поворотов — локальной перестановки нескольких узлов, которая сохраняет порядок ключей.

• AVL-дерево хранит в узле высоту и следит, чтобы высоты левого и правого поддеревьев отличались не больше чем на 1. Баланс строгий, поэтому поиск быстрый, но при изменениях поворотов бывает больше.
• Красно-чёрное дерево красит узлы в два цвета и соблюдает правила, при которых самый длинный путь от корня до листа не больше чем вдвое длиннее самого короткого. Баланс мягче, зато вставка и удаление обычно дешевле.

Красно-чёрные деревья лежат в основе многих стандартных библиотек — например, TreeMap в Java. Писать их самому стоит в учебных целях; в рабочем коде берите готовую реализацию.

Частые ошибки

• Проверять правило BST только для прямых потомков, а не для всего поддерева.
• Не решить заранее, что делать с дубликатами.
• Забыть вернуть новый корень из рекурсивной функции удаления.
• Использовать BST там, где хватит хеш-таблицы: если не нужен порядок ключей и поиск по диапазону, словарь проще и быстрее.