У нас накопился неприятный компромисс. Упорядоченный массив быстро ищет (двоичный поиск, O(log N)), но медленно вставляет. Связанный список быстро вставляет, но медленно ищет. А хочется и то и другое сразу. Двоичное дерево поиска даёт именно это: быстрый поиск, вставку и удаление — все за O(log N), если дерево сбалансировано.

Термины

Дерево — это узлы, соединённые рёбрами. Немного слов, без которых не обойтись:

  • корень (root) — верхний узел, точка входа в дерево;
  • родитель и потомок — узел выше и связанные с ним узлы ниже;
  • лист (leaf) — узел без потомков, край дерева;
  • поддерево — узел вместе со всем, что под ним;
  • уровень — глубина узла: у корня 0, у его детей 1 и так далее.

«Двоичное» означает, что у каждого узла не больше двух потомков — левый и правый.

Правило дерева поиска

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

Именно оно делает поиск быстрым. Ищем ключ: сравниваем с корнем; меньше — идём влево, больше — вправо, и так спускаемся, отсекая на каждом шаге половину дерева. Это тот же двоичный поиск, но по структуре из узлов, а не по массиву.

Node find(Node node, long key) {
    while (node != null && node.key != key)
        node = (key < node.key) ? node.left : node.right;
    return node;
}

Вставка и обход

Вставка идёт по тому же спуску: находим, где ключа не хватает (пустое место слева или справа внизу), и подвешиваем туда новый узел. Тоже O(log N) в сбалансированном дереве.

Обход (traversal) — способ посетить все узлы. Самый полезный — симметричный (in-order): сначала левое поддерево, потом сам узел, потом правое. Магия в том, что симметричный обход дерева поиска выдаёт ключи строго по возрастанию — дерево «само отсортировано». Обход естественно записывается рекурсией: посети левого потомка, обработай узел, посети правого.

Удаление — самая хитрая операция

Удаление разбивается на три случая по числу потомков у удаляемого узла:

  1. нет потомков (лист) — просто отцепляем узел от родителя;
  2. один потомок — «перекидываем» ребёнка на место удаляемого, как в связанном списке;
  3. два потомка — сложный случай. Нельзя просто убрать узел, у него двое детей. Вместо этого находят преемника — наименьший ключ в правом поддереве (это следующий по величине элемент) — и ставят его на место удаляемого. Правило дерева при этом сохраняется.

Третий случай — источник большинства ошибок в реализации деревьев, поэтому его разбирают отдельно.

Проблема вырождения

У дерева поиска есть ахиллесова пята. Если вставлять ключи в уже отсортированном порядке (1, 2, 3, 4…), каждый новый узел цепляется справа от предыдущего, и дерево вытягивается в одну длинную ветку — фактически в связанный список. Поиск в нём деградирует до O(N).

То есть обещание O(log N) держится, только пока дерево остаётся сбалансированным — примерно одинаковой глубины во все стороны. Обычное дерево поиска этого не гарантирует. Решение — самобалансирующиеся деревья, которые перестраиваются при вставке: красно-чёрные деревья и деревья 2-3-4. Им посвящены следующие статьи.

Деревья не только для поиска: коды Хаффмана

Двоичные деревья полезны не только как хранилище. Классический пример — сжатие данных кодами Хаффмана. Идея: частым символам дать короткие битовые коды, редким — длинные (в обычной кодировке все символы занимают одинаково). Коды строят по дереву: символы — листья, а частые символы располагают ближе к корню, поэтому их путь (и код) короче. Дерево строят снизу вверх, многократно объединяя два самых редких символа. Такое дерево гарантирует, что ни один код не является началом другого, — поэтому сжатую последовательность можно однозначно раскодировать. Тот же принцип «дерево из частот» лежит в основе многих алгоритмов сжатия.

Коротко

  • Двоичное дерево поиска сочетает быстрый поиск упорядоченного массива с быстрой вставкой списка — всё за O(log N) в сбалансированном виде.
  • Правило: у каждого узла левое поддерево меньше, правое больше. Поиск и вставка — спуск с отсечением половины на каждом шаге.
  • Симметричный обход выдаёт ключи по возрастанию. Удаление узла с двумя потомками решается заменой на преемника.
  • Обычное дерево вырождается в список при вставке отсортированных данных (O(N)); гарантию баланса дают самобалансирующиеся деревья.
  • Двоичные деревья применяют и вне поиска — например, для сжатия кодами Хаффмана.

Дальше — красно-чёрные деревья: как сохранить баланс автоматически и не дать дереву выродиться.