Двоичное дерево поиска¶

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

¶Основные свойства и определения

Каждый узел двоичного дерева поиска содержит ключ (значение) и ссылки на левого и правого потомков (которые могут быть пустыми). Дерево называется бинарным, так как каждый узел имеет не более двух потомков. Свойство упорядоченности (инвариант BST) формулируется следующим образом:

• Для любого узла N все ключи в левом поддереве N меньше ключа N.
• Все ключи в правом поддереве N больше ключа N.

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

¶Типы узлов

• Корень — единственный узел без родителя.
• Листья — узлы, не имеющие потомков.
• Внутренние узлы — узлы, имеющие хотя бы одного потомка.

Высота дерева — максимальное количество рёбер от корня до листа. В сбалансированном дереве высота пропорциональна log₂(n), где n — число узлов. В вырожденном случае (например, когда ключи вставляются в возрастающем порядке) дерево превращается в линейный список с высотой n.

¶Операции над двоичным деревом поиска

¶Поиск элемента

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

• Если равен — элемент найден.
• Если меньше — переходим к левому потомку.
• Если больше — к правому.

Процесс продолжается до достижения листа (элемент не найден) или нахождения совпадения. Сложность — O(h), где h — высота дерева.

¶Вставка

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

¶Удаление

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

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

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

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

• Симметричный (in-order): левое поддерево → узел → правое поддерево. Результат — отсортированная последовательность ключей.
• Прямой (pre-order): узел → левое поддерево → правое поддерево.
• Обратный (post-order): левое поддерево → правое поддерево → узел.

¶Сбалансированные и самобалансирующиеся деревья

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

¶AVL-дерево

Названо по фамилиям создателей — Адельсона-Вельского и Ландиса (1962). В AVL-дереве для каждого узла разница высот левого и правого поддеревьев (коэффициент сбалансированности) не превышает 1. При нарушении баланса выполняются повороты (левые, правые, двойные). Сложность операций — O(log n) в худшем случае.

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

Разработано Рудольфом Байером (1972). Каждый узел помечается как «красный» или «чёрный». Свойства: корень чёрный, красные узлы не могут иметь красных потомков, количество чёрных узлов на пути от корня к листу одинаково. Красно-чёрные деревья менее строго сбалансированы, чем AVL, но обеспечивают меньшее количество поворотов при вставке и удалении. Используются в стандартной библиотеке C++ (std::map, std::set) и в реализации HashMap в Java.

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

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

¶Применение

Двоичные деревья поиска являются фундаментальной структурой данных и используются в различных областях:

• Ассоциативные массивы (словари): реализация отображения «ключ — значение» с быстрым поиском.
• Множества: хранение уникальных элементов с возможностью проверки принадлежности.
• Базы данных: индексы в некоторых СУБД (например, в ранних версиях MySQL).
• Компиляторы: представление синтаксических деревьев и таблиц символов.
• Графические алгоритмы: поиск ближайших точек, пространственное разделение (например, k-d дерево — обобщение на многомерные случаи).

¶Варианты и обобщения

¶Двоичное дерево поиска с повторяющимися ключами

Если допускаются равные ключи, их можно хранить в одном узле (счётчик) или вставлять по соглашению в левое или правое поддерево. В последнем случае порядок вставки может влиять на структуру.

¶Самобалансирующиеся деревья

Как упоминалось выше, AVL и красно-чёрные деревья являются наиболее распространёнными самобалансирующимися вариантами BST.

¶Деревья с дополнительными свойствами

• Splay-дерево: недавно использованные узлы перемещаются к корню (амортизационная сложность O(log n)).
• B-дерево: обобщение на многоузловые страницы, используется в файловых системах и базах данных.

¶Ограничения и недостатки

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

¶История

Концепция двоичного дерева поиска была впервые формально описана в 1960-х годах, хотя идеи упорядоченных деревьев использовались и ранее. В 1962 году Адельсон-Вельский и Ландис предложили AVL-дерево — первую самобалансирующуюся структуру. В 1972 году Рудольф Байер разработал красно-чёрное дерево. С тех пор BST остаются одной из ключевых структур данных, изучаемых в курсах алгоритмов и структур данных.

¶Пример реализации на псевдокоде

``` class Node: key left right

function search(node, key): if node is None: return None if key == node.key: return node elif key < node.key: return search(node.left, key) else: return search(node.right, key)

function insert(node, key): if node is None: return new Node(key) if key < node.key: node.left = insert(node.left, key) else: node.right = insert(node.right, key) return node ```

¶Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013.
• Кнут Д. Искусство программирования. Том 3. Сортировка и поиск. — М.: Вильямс, 2007.
• Седжвик Р. Фундаментальные алгоритмы на C++. — М.: ДиаСофт, 2002.
• Адельсон-Вельский Г. М., Ландис Е. М. Один алгоритм организации информации // Доклады АН СССР. — 1962. — Т. 146, № 2. — С. 263–266.
• Bayer R. Symmetric binary B-trees: Data structure and maintenance algorithms // Acta Informatica. — 1972. — Vol. 1, No. 4. — P. 290–306.