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

Если ты знаешь инвариант BST (левое < узел < правое в каждом узле), умеешь искать и вставлять спуском от корня и понимаешь, почему цена операций - это высота дерева, листай до «Теперь сам».

Как думаешь, как искать быстро И вставлять дёшево

Отсортированный массив ищет за Θ(log n) двоичным поиском - но вставка в него Θ(n): чтобы воткнуть элемент в середину, надо сдвинуть половину. Связный список вставляет за O(1), но искать в нём Θ(n) - порядок не помогает, прыгать нельзя. Хочется забрать лучшее от обоих: быстрый поиск КАК в массиве и дешёвую вставку КАК в списке. Массив не даёт этого из-за непрерывности в памяти. А что если хранить элементы не подряд, а СВЯЗЯМИ - как список, но организованными так, чтобы можно было прыгать? Дерево поиска - ровно эта идея: порядок задаётся не адресами, а структурой ссылок, и потому и поиск дёшев, и вставка.

На что это похоже

Турнирная сетка наоборот - или, точнее, справочник-определитель растений: «цветок жёлтый? да - листай налево, нет - направо; лепестков больше пяти? …». Каждый вопрос делит оставшиеся варианты, и за десяток вопросов из тысячи видов остаётся один. Дерево поиска - такой определитель для чисел: в каждом узле вопрос «твой ключ меньше здешнего?», и ответ уводит в одну ветку, отсекая другую целиком. А добавить новый вид в определитель легко - дописать листок в нужном месте, не перетряхивая всю книгу. Это и есть дешёвая вставка.

Механизм: инвариант BST и спуск

Узел дерева хранит ключ и две ссылки - на левое и правое поддерево (любая может быть пустой). Инвариант BST: для каждого узла все ключи ЛЕВОГО поддерева меньше его ключа, все ключи ПРАВОГО - больше. Важно: это про ВСЁ поддерево, а не только про непосредственных детей.

поиск(узел, x):
    пока узел не пуст:
        если x == узел.ключ:  нашли
        если x <  узел.ключ:  узел = узел.лево      # ответ в левом поддереве
        иначе:                узел = узел.право     # в правом
    вернуть «нет»

вставка(x):
    спускаемся как в поиске, пока не упрёмся в пустую ссылку,
    и подвешиваем новый узел с ключом x на её место

Несколько слов для точности. Верхний узел - КОРЕНЬ, узлы без детей - ЛИСТЬЯ, узел вместе со всеми его потомками - ПОДДЕРЕВО. ВЫСОТА дерева - число узлов на самом длинном пути от корня до листа (у дерева из одного узла высота 1, у пустого 0).

Поиск и вставка идут по ОДНОМУ пути от корня вниз: на каждом узле одно сравнение отсекает целое поддерево. Минимум - иди всё время влево, максимум - всё время вправо. Цена любой из этих операций - длина пройденного пути, а она не больше ВЫСОТЫ дерева h.

Правило

Двоичное дерево поиска - структура, где в КАЖДОМ узле все ключи левого поддерева меньше ключа узла, а правого - больше (инвариант BST). Поиск, вставка, минимум, максимум идут по одному пути от корня вниз, отсекая на каждом узле целое поддерево; их цена - O(h), где h - высота дерева. У сбалансированного дерева h = Θ(log n), и все операции Θ(log n). Это динамическое упорядоченное множество: и быстрый поиск (как в массиве), и дешёвые вставка с удалением (как в списке).

Разбор: почему инвариант должен держаться во ВСём поддереве, а не у детей

Тонкость, которую легко упустить. Свойство BST - «левое поддерево целиком меньше, правое целиком больше», а не «левый ребёнок меньше, правый больше». Разница критична. Возьми дерево: корень 8, правый ребёнок 10, а у 10 левый ребёнок 7. Локально всё цело: 10 > 8, 7 < 10. Но 7 оказался в ПРАВОМ поддереве восьмёрки, а 7 < 8 - инвариант BST нарушен! И поиск сломается: ища 7, мы в корне сравним 7 < 8 и уйдём ВЛЕВО, а 7 лежит справа - не найдём. Поэтому при вставке новый ключ должен попасть туда, куда приводит спуск ОТ КОРНЯ: только так он окажется в согласии со всеми предками, а не только с будущим родителем. Инвариант - глобальное свойство дерева, и держать его надо на каждом уровне спуска.

Разбор: почему обход «левый-узел-правый» даёт отсортированный порядок

У BST есть красивое следствие: если обойти его В ПОРЯДКЕ «сначала всё левое поддерево, потом сам узел, потом всё правое» (это называют СИММЕТРИЧНЫМ обходом, или inorder), ключи выйдут по ВОЗРАСТАНИЮ. Почему: по инварианту всё левое поддерево меньше узла, поэтому его надо выписать раньше узла; всё правое больше - позже. Применяя это правило рекурсивно в каждом узле, получаем полностью упорядоченную последовательность. Значит BST - это ещё и способ ХРАНИТЬ данные так, что отсортированный список достаётся одним обходом за Θ(n), без отдельной сортировки. Отсюда и практическая роль: упорядоченное множество, которое умеет и быстро искать, и в любой момент выдать всё по порядку, и при этом дёшево принимать новые элементы. (Обходы разберём отдельным уроком - там же прямой и обратный.)

Что ломается без этого

Первая ошибка - проверять инвариант только у непосредственных детей: дерево может выглядеть «локально правильным», но иметь ключ не на своём месте относительно ДАЛЬНЕГО предка - и поиск будет молча промахиваться. Вторая - вставлять узел «куда удобно», а не туда, куда приводит спуск от корня: нарушишь порядок, дерево перестанет быть BST. Третья - путать высоту с числом узлов: цена операций - это O(h), и если дерево вырождено в цепочку (урок про вырождение), h = n и всё становится O(n), а не O(log n). Четвёртая - ждать Θ(log n) от ЛЮБОГО BST: это верно только для СБАЛАНСИРОВАННОГО; обычный BST такой гарантии не даёт.

Зачем это в работе

Деревья поиска - фундамент упорядоченных структур данных. std::map и std::set в C++, TreeMap/TreeSet в Java - это сбалансированные деревья поиска (красно-чёрные, следующая глава): они держат элементы упорядоченными, дают O(log n) на поиск/вставку/удаление и позволяют то, чего не умеет хеш-таблица, - обход по порядку, поиск ближайшего, диапазонные запросы «все ключи от a до b». Индексы баз данных (B-деревья, тоже в этом разделе) - деревья поиска на диске. Понимать BST - значит понимать, ПОЧЕМУ упорядоченный контейнер медленнее хеш-таблицы в среднем (log n против 1), но даёт то, что хеш не может: порядок и гарантию худшего случая. И понимать главную опасность - вырождение, ради борьбы с которым придумана вся балансировка.

Теперь сам

В дерево поиска (изначально пустое) вставляют по очереди 5, 3, 8, 4. Нарисуй результат и скажи, за сколько сравнений найдётся 4 и почему обход «левое-узел-правое» даст 3, 4, 5, 8.