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

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

¶История

Идея автоматического поддержания баланса в деревьях поиска возникла в середине XX века как ответ на проблему вырождения деревьев при неслучайных данных. Первой широко известной самобалансирующейся структурой стало АВЛ-дерево, предложенное советскими учёными Георгием Адельсоном-Вельским и Евгением Ландисом в 1962 году. В 1964 году Роберт Седжвик и Леонард Адлеман (соавтор криптосистемы RSA) разработали красно-чёрное дерево, которое отличается более слабыми, но практичными условиями балансировки. В 1970-х годах появились B-деревья (Рудольф Байер и Эдвард МакКрейт), предназначенные для работы с внешней памятью, и splay-деревья (Дэниел Слейтор и Роберт Тарьян, 1985), использующие принцип «выстреливания» часто запрашиваемого элемента в корень. В 1990-х годах были разработаны декартовы деревья (treap), сочетающие свойства двоичного дерева поиска и кучи. В России и странах бывшего СССР наибольшее распространение получили АВЛ-деревья и красно-чёрные деревья, которые активно изучаются в курсах алгоритмов и структур данных.

¶Классификация

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

¶По числу потомков в узле

• Бинарные (двоичные): каждый узел имеет не более двух потомков. Примеры: АВЛ-дерево, красно-чёрное дерево, splay-дерево, декартово дерево.
• Многопутевые (B-деревья): узлы могут содержать от 2 до m ключей и иметь до m+1 потомков. Примеры: B-дерево, B+-дерево, B*-дерево.

¶По критерию баланса

• Строго сбалансированные: разность высот левого и правого поддеревьев не превышает 1 (АВЛ-дерево).
• Слабо сбалансированные: баланс поддерживается через цветовые или ранговые свойства, допускающие большие локальные перекосы, но гарантирующие логарифмическую высоту (красно-чёрное дерево, AA-дерево).
• Амортизационно сбалансированные: баланс не гарантируется для каждой отдельной операции, но среднее время работы за последовательность операций остаётся логарифмическим (splay-дерево).

¶По способу реализации

• Детерминированные: балансировка выполняется строго по заданным правилам (АВЛ, красно-чёрное, B-дерево).
• Вероятностные: баланс достигается за счёт случайных приоритетов (декартово дерево, рандомизированное бинарное дерево поиска).

¶Устройство и принципы работы

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

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

1. Стандартная операция — вставка нового узла или удаление существующего по правилам двоичного дерева поиска.
2. Восстановление баланса — выполнение поворотов (левого, правого, двойных) и/или перекрашивание узлов для восстановления свойств дерева.

¶Повороты

Поворот — это локальная операция, изменяющая структуру дерева без нарушения свойства упорядоченности. Различают левый и правый повороты. Например, при левом повороте вокруг узла A его правый потомок B становится новым корнем поддерева, а A становится левым потомком B. Правый поворот симметричен. Повороты выполняются за O(1) и являются основным инструментом балансировки в АВЛ и красно-чёрных деревьях.

¶АВЛ-дерево

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

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

Красно-чёрное дерево накладывает пять свойств:

1. Каждый узел окрашен в красный или чёрный цвет.
2. Корень всегда чёрный.
3. Все листья (nil-узлы) чёрные.
4. Если узел красный, то оба его потомка чёрные (нет двух красных подряд).
5. Для любого узла все пути от него до листьев содержат одинаковое количество чёрных узлов (чёрная высота).

Эти свойства гарантируют, что самый длинный путь от корня до листа не более чем вдвое длиннее самого короткого. Вставка и удаление в красно-чёрном дереве требуют не более O(1) поворотов и O(log n) перекрашиваний. Красно-чёрные деревья широко используются в стандартных библиотеках языков программирования (например, std::map в C++, TreeMap в Java).

¶B-дерево

B-дерево — это обобщение двоичного дерева, где каждый узел может содержать от t-1 до 2t-1 ключей (t — параметр порядка). Узлы имеют от t до 2t потомков. B-деревья оптимизированы для работы с дисковыми накопителями: высота дерева мала (обычно 2-3 уровня), что минимизирует количество обращений к внешней памяти. B+-деревья, в которых все данные хранятся только в листьях, являются основой индексов в большинстве реляционных баз данных.

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

Декартово дерево сочетает свойства двоичного дерева поиска по ключу и кучи по случайному приоритету. Каждый узел имеет ключ (по которому строится двоичное дерево) и приоритет (случайное число, по которому строится куча). Вставка и удаление выполняются через операции split (разделение) и merge (слияние) за O(log n) в среднем. Баланс достигается за счёт случайности приоритетов, что делает treap простым в реализации и эффективным на практике.

¶Применение

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

• Базы данных: B-деревья и B+-деревья — стандартный способ организации индексов для ускорения поиска, вставки и удаления записей. Например, в PostgreSQL и MySQL индексы по умолчанию реализованы как B+-деревья.
• Стандартные библиотеки языков программирования: красно-чёрные деревья лежат в основе контейнеров std::map и std::set в C++, TreeMap и TreeSet в Java, SortedDictionary и SortedSet в C#. В Python dict и set используют хеш-таблицы, но для упорядоченных коллекций применяются библиотеки на основе деревьев (например, bisect с отсортированными списками).
• Файловые системы: некоторые файловые системы (например, HFS+, ReiserFS) используют B-деревья для каталогов и метаданных.
• Сетевые маршрутизаторы: для быстрого поиска маршрутов по IP-адресам применяются сбалансированные деревья, в том числе trie-подобные структуры.
• Компиляторы и интерпретаторы: синтаксические деревья, таблицы символов, ассоциативные массивы часто реализуются через самобалансирующиеся деревья.
• Алгоритмы обработки данных: в задачах, требующих поддержания упорядоченного множества с операциями поиска, вставки, удаления, поиска минимума/максимума, предшественника/последователя.

¶Примеры

¶АВЛ-дерево в стандартной библиотеке

В языке C++ стандартная библиотека не включает АВЛ-дерево напрямую, но в учебных целях часто реализуется в курсах алгоритмов. В Java класс AVLTree не входит в стандартную библиотеку, но существует в сторонних библиотеках (например, Apache Commons). В Python реализация АВЛ-дерева доступна в модуле bisect не напрямую, а через пользовательские классы.

¶Красно-чёрное дерево в C++ (std::map)

В C++ контейнер std::map гарантирует логарифмическое время для операций вставки, удаления и поиска. Внутренняя реализация в GCC (libstdc++) основана на красно-чёрном дереве. Аналогично в Java TreeMap использует красно-чёрное дерево.

¶B-дерево в базах данных

В PostgreSQL индексы типа B-tree (B+-дерево) создаются командой CREATE INDEX. Для таблицы с миллионом записей высота B-дерева обычно составляет 3-4 уровня, что позволяет выполнять поиск за 3-4 обращения к диску.

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

• Связь с криптографией: Леонард Адлеман, один из соавторов красно-чёрного дерева, позже стал соавтором RSA — одной из первых асимметричных криптосистем. Однако красно-чёрное дерево не имеет прямого отношения к криптографии.
• Рекордная высота: АВЛ-дерево имеет минимально возможную высоту среди всех бинарных деревьев поиска при заданном числе узлов — около 1.44 log n. Для n=10^6 высота АВЛ-дерева не превышает 28, а для n=10^9 — 40.
• Использование в операционных системах: ядро Linux использует красно-чёрные деревья для реализации планировщика задач (CFS — Completely Fair Scheduler) и для управления виртуальной памятью (структуры vm_area_struct).
• Эффективность на практике: хотя АВЛ-дерево строже сбалансировано, чем красно-чёрное, на практике красно-чёрные деревья часто оказываются быстрее из-за меньшего числа поворотов при вставке. Однако для операций, где поиск доминирует (например, в базах данных), АВЛ-деревья могут быть предпочтительнее.
• Название «декартово дерево»: термин «декартово» (treap) происходит от сочетания «tree» (дерево) и «heap» (куча). В русскоязычной литературе также используется название «куча-дерево» или «рандомизированное бинарное дерево поиска».

¶Критика и ограничения

Несмотря на широкое распространение, самобалансирующиеся деревья имеют ряд недостатков:

• Накладные расходы памяти: для хранения дополнительной информации (высота, цвет, приоритет) требуется дополнительная память. Например, в АВЛ-дереве каждый узел хранит коэффициент сбалансированности (обычно 2 бита), в красно-чёрном — цвет (1 бит), но на практике из-за выравнивания памяти это может занимать целый байт или больше.
• Сложность реализации: особенно для АВЛ-деревьев и красно-чёрных деревьев, где требуется аккуратная обработка всех случаев балансировки. Это повышает вероятность ошибок при ручной реализации.
• Альтернативы: в некоторых сценариях хеш-таблицы обеспечивают O(1) в среднем для поиска, вставки и удаления, хотя не поддерживают упорядоченный обход. Для задач, где требуется только поиск без вставок/удалений, эффективнее отсортированные массивы с бинарным поиском.
• Проблемы с кэш-памятью: бинарные деревья, особенно рекурсивные, могут плохо использовать кэш-память процессора из-за случайного доступа к узлам. B-деревья, напротив, оптимизированы для работы с блоками памяти.

¶Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013. — 1328 с.
• Адельсон-Вельский Г. М., Ландис Е. М. Один алгоритм организации информации // Доклады АН СССР. — 1962. — Т. 146, № 2. — С. 263–266.
• Седжвик Р. Фундаментальные алгоритмы на C++. — М.: ДиаСофт, 2002. — 688 с.
• Bayer R., McCreight E. Organization and maintenance of large ordered indexes // Acta Informatica. — 1972. — Vol. 1, no. 3. — P. 173–189.
• Sleator D. D., Tarjan R. E. Self-adjusting binary search trees // Journal of the ACM. — 1985. — Vol. 32, no. 3. — P. 652–686.
• Официальная документация PostgreSQL: Chapter 11. Indexes. — https://www.postgresql.org/docs/current/indexes.html (дата обращения: 2025).
• Документация GNU libstdc++: std::map. — https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html (дата обращения: 2025).