Сбалансированное дерево

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

История

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

В 1972 году Рудольф Байер и Эдвард МакКрейт разработали красно-чёрные деревья, которые используют цветовую маркировку узлов для поддержания баланса. В 1978 году Леон Гвибас и Роберт Седжвик предложили сплей-деревья, где балансировка происходит за счёт перемещения часто запрашиваемых узлов к корню. В 1980-х годах появились B-деревья (обобщение, используемое в базах данных и файловых системах), а в 1990-х — treap (декартово дерево), сочетающее свойства двоичного дерева и кучи.

Основные виды сбалансированных деревьев

АВЛ-деревья

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

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

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

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

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

B-деревья

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

Сплей-деревья

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

Декартовы деревья (treap)

Декартово дерево (treap) сочетает свойства двоичного дерева поиска по ключу и кучи по приоритету. Каждый узел имеет ключ и случайно сгенерированный приоритет. Дерево строится так, что по ключам оно является двоичным деревом поиска, а по приоритетам — кучей (приоритет родителя больше приоритетов потомков). При случайном выборе приоритетов высота дерева с высокой вероятностью составляет O(log n). Операции вставки и удаления выполняются через разделение и слияние деревьев.

Принципы балансировки

Фактор сбалансированности

Фактор сбалансированности узла — это разность высот его правого и левого поддеревьев. В АВЛ-деревьях он может принимать значения -1, 0 или 1. При нарушении этого диапазона выполняются повороты.

Повороты

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

• Правый поворот — левый потомок становится родителем текущего узла.
• Левый поворот — правый потомок становится родителем текущего узла.
• Двойные повороты — комбинация двух одинарных поворотов (левый-правый, правый-левый) для коррекции сложных нарушений баланса.

Инварианты

Каждый тип сбалансированного дерева поддерживает определённый набор инвариантов — условий, которые должны выполняться после каждой операции. Нарушение инварианта влечёт за собой перестройку структуры (повороты, перекрашивание, сплей).

Применение

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

• Базы данных: B-деревья и их разновидности (B+, B*) являются основой индексов в реляционных СУБД (PostgreSQL, MySQL, Oracle) и NoSQL-системах (MongoDB).
• Файловые системы: B-деревья применяются в NTFS, ext4, HFS+ для организации каталогов и метаданных.
• Стандартные библиотеки языков программирования: красно-чёрные деревья реализованы в std::map, std::set (C++), java.util.TreeMap, java.util.TreeSet, SortedDictionary (.NET).
• Операционные системы: для управления виртуальной памятью, планирования задач.
• Компиляторы: для хранения таблиц символов, синтаксических деревьев.
• Сетевые маршрутизаторы: для хранения таблиц маршрутизации (используются Patricia-деревья, вариант сбалансированных деревьев).
• Графические движки: для пространственного разделения (BSP-деревья, квадродеревья, октодеревья — обобщения на многомерные пространства).

Сравнение характеристик

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

• Термин «красно-чёрное дерево» возник из-за использования цветной ленты в струйном плоттере, на котором авторы печатали диаграммы.
• АВЛ-деревья названы в честь Адельсона-Вельского и Ландиса, которые опубликовали первую работу по самобалансирующимся деревьям в журнале «Доклады Академии наук СССР» в 1962 году.
• B-деревья не имеют однозначной расшифровки: по одной версии, «B» означает «Bayer» (по имени соавтора), по другой — «balanced» (сбалансированное) или «Boeing» (место работы авторов).
• Сплей-деревья обладают свойством «статической оптимальности»: если к некоторым элементам обращаются значительно чаще, чем к другим, дерево приближается к оптимальному статическому дереву для этого распределения.
• Декартовы деревья (treap) получили название от сочетания «tree» (дерево) и «heap» (куча).

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

• АВЛ-деревья требуют больше операций при вставке и удалении по сравнению с красно-чёрными, что может быть критично в системах с высокой частотой модификаций.
• Красно-чёрные деревья имеют большую высоту, чем АВЛ, что может увеличивать время поиска на несколько процентов.
• B-деревья неэффективны для полностью резидентных в памяти данных, так как накладные расходы на поддержание узлов с множеством ключей могут превышать выигрыш.
• Сплей-деревья не гарантируют логарифмической оценки для каждой отдельной операции — только амортизированную.
• Treap с неудачным выбором случайных приоритетов (например, при детерминированной генерации) может выродиться в линейную структуру.
• В многопоточных средах балансировка требует синхронизации, что может приводить к блокировкам и снижению производительности.

Источники

• Адельсон-Вельский Г. М., Ландис Е. М. «Один алгоритм организации информации» // Доклады АН СССР, 1962.
• Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. «Introduction to Algorithms» (3rd ed.), MIT Press, 2009.
• Bayer R., McCreight E. «Organization and Maintenance of Large Ordered Indices» // Acta Informatica, 1972.
• Tarjan R. E. «Data Structures and Network Algorithms», SIAM, 1983.
• Weiss M. A. «Data Structures and Algorithm Analysis in C++» (4th ed.), Pearson, 2013.
• Sedgewick R., Wayne K. «Algorithms» (4th ed.), Addison-Wesley, 2011.