Поиск в двоичном дереве поиска: алгоритм и сложность

Двоичное дерево поиска (BST, binary search tree) - одна из базовых структур данных, которую разбирают в каждом курсе по алгоритмам. Суть простая: в каждом узле хранится ключ, все ключи левого поддерева меньше него, все ключи правого - больше. Эта инвариантность позволяет искать, вставлять и удалять элементы за $O(\log n)$ в среднем случае, не просматривая всё дерево целиком. Чтобы сразу увидеть, как изменяется число сравнений при разных размерах дерева и разных целевых ключах, покрутите калькулятор ниже.

Как работает алгоритм поиска в BST

Поиск начинается с корня и на каждом шаге делает одно сравнение:

Рассчитать для своей задачи

1. Если дерево пусто - ключ не найден, возвращаем null.
2. Сравниваем искомый ключ $k$ с ключом текущего узла $v$.
   • $k = v$ - узел найден, возвращаем его.
   • $k < v$ - переходим в левое поддерево.
   • $k > v$ - переходим в правое поддерево.
3. Повторяем с нового текущего узла.

В итоге алгоритм идёт по одному пути от корня до нужного узла (или до пустого места, если ключа нет). Никакие другие ветки не просматриваются - в этом вся сила BST. На псевдокоде рекурсивная версия выглядит так:

search(node, k):
    if node == null: return null
    if k == node.key: return node
    if k < node.key: return search(node.left, k)
    else: return search(node.right, k)

Итеративный вариант делает то же самое без рекурсии: заводит переменную cur = root и в цикле смещает её влево или вправо, пока не найдёт ключ или не дойдёт до null.

Сложность поиска: O(log n) и O(n)

Число сравнений в поиске равно глубине целевого узла плюс один (корень находится на глубине 0, его проверка - первое сравнение). Глубина зависит от формы дерева.

Сбалансированное дерево. Если при каждом разветвлении дерево делится примерно пополам, высота $h = \lfloor \log_2 n \rfloor$. Поиск занимает от 1 сравнения (корень) до $h + 1$ сравнений (лист). Среднее по всем ключам:

$$\overline{c}(n) = \frac{1}{n} \sum_{d=0}^{h} (d+1) \cdot |L_d|,$$

где $|L_d|$ - число узлов на уровне $d$. Для полного BST из $n = 2^h - 1$ узлов среднее приближённо равно $\log_2 n - 1 + 2/n \approx \log_2 n$.

Вырожденное дерево (цепочка). Если ключи вставлялись в порядке возрастания или убывания, каждый новый узел становится правым (или левым) ребёнком предыдущего. Дерево превращается в связный список, высота равна $n - 1$, а поиск в худшем случае требует $n$ сравнений - $O(n)$.

Рассчитать для своей задачи

Вот почему порядок вставки элементов в BST критически важен: одни и те же ключи, добавленные в разном порядке, дают деревья с кардинально разной производительностью. Эту проблему решают самобалансирующиеся деревья - AVL-дерево и красно-чёрное дерево.

Путь поиска: пример для BST[1..15]

Рассмотрим сбалансированный BST с ключами от 1 до 15. Корень - ключ 8 (середина), его левый ребёнок - 4, правый - 12, и так далее до листьев.

Ищем ключ 11:

1. Корень 8: $11 > 8$ → идём вправо.
2. Узел 12: $11 < 12$ → идём влево.
3. Узел 10: $11 > 10$ → идём вправо.
4. Узел 11: $11 = 11$ → найден.

Потребовалось 4 сравнения при высоте дерева $h = \lfloor \log_2 15 \rfloor = 3$. Максимально возможное число сравнений - $h + 1 = 4$, и мы в него попали, потому что 11 - это лист. Если искать корень (8), хватит одного сравнения.

Инвариант BST и почему он работает

BST работает благодаря строгому инварианту: для любого узла $v$ все ключи в левом поддереве $v$ строго меньше $v.key$, а все ключи в правом поддереве строго больше. Этот инвариант гарантирует, что на каждом шаге поиска мы точно знаем, в какую половину дерева идти. При равенстве ключей (дубликаты) разные реализации поступают по-разному: кладут дубликат влево, вправо или запрещают его. Важно, чтобы выбранная политика соблюдалась при всех операциях - иначе инвариант нарушится и поиск будет давать неверный результат.

Простая итеративная реализация на Python:

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

def search(root, k):
    cur = root
    while cur:
        if k == cur.key:
            return cur
        cur = cur.left if k < cur.key else cur.right
    return None

Успешный и безуспешный поиск

Поиск бывает успешным (ключ найден) и безуспешным (ключа нет). В безуспешном случае алгоритм доходит до null и возвращает «не найдено». Число сравнений при безуспешном поиске равно высоте узла, в поддерево которого «упал бы» искомый ключ, плюс один. В сбалансированном BST это тоже $O(\log n)$.

Асимптотика в таблице:

Рассчитать для своей задачи

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

• Путают BST с кучей. В BST левый потомок меньше родителя и правого. В куче (heap) каждый родитель больше обоих потомков, но порядок между левым и правым потомками не задан - поиск произвольного ключа в куче работает за $O(n)$, а не за $O(\log n)$.
• Забывают про вырождение. Если вставлять элементы по возрастанию, получается список. Многие думают, что BST всегда даёт $O(\log n)$, - это справедливо только для сбалансированных деревьев.
• Некорректный инвариант при дубликатах. Если не определить однозначную политику для равных ключей (влево или вправо), поиск может пропустить существующий элемент.
• Путают глубину и высоту. Глубина узла - расстояние от корня до него. Высота дерева - максимальная глубина листа. Число сравнений при поиске равно глубине узла плюс один.
• Рекурсивная реализация без базового случая. Если не проверить node == null в начале, рекурсия упадёт с NullPointerException при попытке обратиться к .left пустого узла.

FAQ

Чем BST отличается от бинарного поиска по массиву? Бинарный поиск по отсортированному массиву тоже работает за $O(\log n)$, но вставка и удаление элемента занимают $O(n)$ - нужно сдвигать элементы. В BST вставка и удаление - $O(\log n)$ для сбалансированного дерева, но поиск требует обхода указателей, что медленнее доступа по индексу в массиве из-за кэш-промахов.

Что такое AVL-дерево и зачем оно нужно? AVL-дерево - это BST с дополнительным инвариантом: для каждого узла высоты левого и правого поддеревьев различаются не более чем на 1. После каждой вставки или удаления выполняются повороты, восстанавливающие баланс. Это гарантирует высоту $O(\log n)$ и, следовательно, поиск за $O(\log n)$ в любом случае, без риска вырождения.

Как найти минимальный и максимальный ключ в BST? Минимальный ключ - в самом левом узле: идём влево от корня, пока не дойдём до null. Максимальный - в самом правом. Обе операции выполняются за $O(h)$ шагов, то есть $O(\log n)$ для сбалансированного дерева.

Коротко

Поиск в двоичном дереве поиска движется от корня к листьям, на каждом шаге делая одно сравнение и уходя в левое или правое поддерево. Для сбалансированного BST из $n$ узлов высота $h = \lfloor \log_2 n \rfloor$, число сравнений - от 1 до $h + 1$, среднее $\approx \log_2 n$. Вырожденное дерево (цепочка) деградирует до $O(n)$ сравнений. Самобалансирующиеся структуры (AVL, красно-чёрное дерево) гарантируют $O(\log n)$ независимо от порядка вставки.