Бинарное дерево поиска

Бинарное дерево поиска (англ. binary search tree, BST) — это структура данных, представляющая собой корневое двоичное дерево, в котором для каждого узла выполняется свойство упорядоченности: все ключи в левом поддереве узла меньше ключа этого узла, а все ключи в правом поддереве — больше (или равны в зависимости от реализации). Данная структура обеспечивает эффективный поиск, вставку и удаление элементов, в среднем за время O(log n), где n — количество узлов.

Основные свойства

Ключевой особенностью бинарного дерева поиска является инвариант, накладываемый на значения узлов. Для любого узла с ключом \( K \):

• все ключи, находящиеся в левом поддереве узла, строго меньше \( K \);
• все ключи, находящиеся в правом поддереве узла, строго больше \( K \).

Допущение относительно равенства ключей варьируется: в большинстве реализаций дубликаты не допускаются, что делает дерево «строгим». В некоторых вариантах допускается хранение повторяющихся ключей (обычно в одном узле или в одном из поддеревьев). Отсутствие дубликатов упрощает алгоритмы и гарантирует уникальность ключей.

Каждый узел дерева, как правило, содержит три поля: ключ (или пару «ключ — значение» для ассоциативных массивов), указатель на левого потомка, указатель на правого потомка. В расширенных реализациях также может храниться ссылка на родительский узел для упрощения итераций.

История

Идея упорядоченных бинарных деревьев восходит к работам конца 1950-х — начала 1960-х годов. В 1960 году британский учёный Тони Хоар опубликовал алгоритм быстрой сортировки, который использует принцип разбиения массива на две части относительно опорного элемента — аналогично тому, как устроено BST. Однако само понятие структуры «бинарное дерево поиска» и её алгоритмы были формализованы в 1962 году американскими учёными Робертом Седжвиком и Дональдом Кнутом в рамках анализа алгоритмов сортировки и поиска. В 1970-е годы появилась концепция сбалансированных BST (АВЛ-деревья, красно-чёрные деревья), что устранило проблему вырождения в линейный список.

Основные операции

Поиск

Поиск элемента с заданным ключом выполняется рекурсивно или итеративно. Начиная с корня, алгоритм сравнивает искомый ключ с ключом текущего узла:

• если ключи совпадают — элемент найден;
• если искомый ключ меньше — поиск продолжается в левом поддереве;
• если больше — в правом поддереве.

Рекурсия заканчивается, если достигается пустой узел (null или nil) — тогда элемента в дереве нет.

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

Вставка

Операция вставки также начинается от корня. Сравнивая новый ключ с ключом текущего узла, алгоритм выбирает направление (левое или правое поддерево). Если в выбранном направлении есть потомок — рекурсивно переходит к нему. Если потомка нет — новый узел создаётся и подвешивается в соответствующую ветвь. При строгом BST с уникальными ключами при обнаружении дубликата обычно выбрасывается исключение или возвращается ошибка.

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

Удаление

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

1. Узел — лист (нет потомков). Просто удаляется — родительский указатель (или корень) устанавливается в null.
2. Узел имеет только одного потомка. Удаляемый узел заменяется его потомком (левым или правым). Если удаляется корень — корнем становится единственный потомок.
3. Узел имеет обоих потомков. В этом случае на место удаляемого узла помещается его преемник (наименьший ключ в правом поддереве) или предшественник (наибольший ключ в левом поддереве). После этого необходимо рекурсивно удалить преемника или предшественника, который гарантированно находится в одном из двух простых случаев (лист или узел с одним потомком).

Все операции сравнения выполняются над ключами, поэтому критически важно, чтобы ключи поддерживали операцию сравнения (например, целые числа, строки в лексикографическом порядке).

Обходы (Traversals)

Для работы с BST используются три основных способа обхода узлов:

• Прямой (pre-order): корень, левое поддерево, правое поддерево.
• Центрированный (in-order): левое поддерево, корень, правое поддерево. Для BST центрированный обход выводит элементы в порядке возрастания ключей.
• Обратный (post-order): левое поддерево, правое поддерево, корень.

Центрированный обход часто используется для сортировки данных, хранящихся в BST — достаточно построить дерево из входных данных и выполнить in-order обход.

Сложность и вырождение

Идеальное бинарное дерево поиска — сбалансированное, когда высота дерева минимально возможна (\( \approx \log_2 n \)). Однако при последовательной вставке уже отсортированных данных дерево вырождается в линейный односвязный список (все новые узлы добавляются только вправо или только влево). В этом случае все операции становятся \( O(n) \), что неприемлемо для больших наборов данных.

Для решения проблемы вырождения были разработаны самобалансирующиеся структуры на основе BST, например АВЛ-деревья и красно-чёрные деревья. Они автоматически перестраивают дерево после вставок и удалений, поддерживая высоту порядка \( O(\log n) \).

Сбалансированные варианты

АВЛ-дерево

Изобретено в 1962 году советскими математиками Георгием Адельсоном-Вельским и Евгением Ландисом. Для каждого узла хранится разность высот левого и правого поддеревьев (коэффициент сбалансированности), которая не должна превышать 1 по модулю. При нарушении баланса выполняются повороты — перестановки узлов, восстанавливающие свойство. АВЛ-деревья обеспечивают строгую сбалансированность, но требуют дополнительных затрат памяти на хранение высоты и более сложных операций восстановления.

Красно-чёрное дерево

Разработано в 1972 году Рудольфом Байером (первоначально как «симметричные бинарные B-деревья»). В каждом узле хранится дополнительный атрибут — цвет (красный или чёрный). Правила дерева гарантируют, что ни один путь от корня до листа не более чем вдвое длиннее любого другого, что обеспечивает логарифмическую высоту. Красно-чёрные деревья используются в стандартной библиотеке C++ (std::map, std::set), в Java (TreeMap, TreeSet) и в ядре Linux для управления памятью.

Декартово дерево (Treap)

Гибрид BST и кучи. Каждому узлу присваивается случайный приоритет; дерево строится так, что по ключам оно является BST, а по приоритетам — кучи (max-heap или min-heap). Это обеспечивает ожидаемую логарифмическую высоту при любой последовательности вставок. Treap прост в реализации и широко применяется в задачах олимпиадного программирования.

Применение

Бинарные деревья поиска (в том числе сбалансированные) используются во многих областях:

• Ассоциативные массивы (словари). BST позволяет реализовать отображение «ключ → значение» с логарифмическим временем доступа. Примеры: std::map в C++, TreeMap в Java.
• Множества (sets). Структура для хранения уникальных элементов с операциями поиска, вставки, удаления. Используется в базах данных для индексации.
• Поиск по диапазону. Благодаря упорядоченности можно эффективно найти все элементы, ключи которых находятся в заданном интервале (range query).
• Сортировка. Построение BST из первоначально неупорядоченных данных и последующий центрированный обход даёт отсортированную последовательность (древовидная сортировка). В среднем работает за \( O(n \log n) \).
• Построение деревьев решений в машинном обучении.
• Реализация планировщиков и кэшей. Например, красно-чёрное дерево используется в ядре Linux для управления объектами памяти и процессорами.

Недостатки

• Чувствительность к порядку вставки. При неблагоприятном исходном порядке BST вырождается, что снижает производительность до линейной. Это решается использованием сбалансированных вариантов.
• Отсутствие поддержки повторяющихся ключей в строгих реализациях (необходимо дорабатывать логику).
• Потребление памяти. Каждый узел хранит минимум три указателя (левый, правый, иногда родительский) и сам ключ, что в несколько раз больше, чем в компактных структурах, например хеш-таблицах.
• Плохая кэш-локальность. В отличие от массивов, узлы BST могут располагаться в памяти случайным образом, что снижает эффективность работы процессорного кэша.

Альтернативы

В случаях, когда критична скорость поиска (O(1)) и не нужны операции с упорядоченными данными, чаще применяются хеш-таблицы. Для работы с большими объёмами данных на диске используются B-деревья и их производные. Для поддержки эффективной вставки, удаления и поиска в условиях жёстких требований к времени используют сбалансированные BST. Выбор структуры данных зависит от конкретной задачи: если часто требуются операции поиска по диапазону или упорядоченный вывод — BST предпочтительнее хеш-таблиц.

Интересные факты

• Бинарные деревья поиска лежат в основе алгоритма быстрой сортировки (quicksort): упорядоченное дерево фактически моделирует процесс рекурсивного деления массива.
• В 2008 году математики К. Дженкинс и Г. Моррисон доказали, что минимальная высота BST, содержащего n узлов, равна \( \lfloor \log_2 n \rfloor \) (полностью сбалансированное дерево). Теоретически достичь этого можно только при определённых последовательностях вставок.
• В стандартной библиотеке C++ контейнер std::map реализован как красно-чёрное дерево, что объясняет гарантированное время операций \( O(\log n) \), в отличие от хеш-таблицы std::unordered_map, которая в среднем работает за \( O(1) \), но не поддерживает порядок элементов.

Источники

• Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. «Алгоритмы: построение и анализ» (3-е издание), глава 12: «Бинарные деревья поиска».
• Д. Кнут. «Искусство программирования», том 3: «Сортировка и поиск».
• G. M. Adelson-Velsky and E. M. Landis. «An algorithm for the organization of information» (1962).
• R. Sedgewick. «Algorithms in C++» (1992).
• Материалы лекций МФТИ и НИУ ВШЭ по алгоритмам и структурам данных.