Сбалансированное дерево поиска — описание, особенности и принципы

Сбалансированные деревья поиска позволяют быстро находить нужные данные среди огромных объемов информации. В этой статье мы подробно разберем, что такое сбалансированное дерево, какие бывают его виды и принципы работы. Узнаете, как с помощью балансировки оптимизировать поиск и сократить число операций.

Общее определение и свойства сбалансированного дерева

Сбалансированное дерево — это дерево, в котором высоты поддеревьев отличаются не более чем на единицу для каждого узла. Такое свойство позволяет добиться высокой скорости поиска по сравнению с обычными несбалансированными деревьями, где разница в высоте поддеревьев может быть значительной.

Если говорить точнее, то различают сбалансированное дерево и идеально сбалансированное дерево . В идеально сбалансированном дереве все уровни заполнены полностью, кроме возможно последнего. А в просто сбалансированном дереве допускается разница высот поддеревьев в 1 уровень.

Преимущества сбалансированного дерева:

• Высокая скорость поиска, вставки и удаления элементов
• Минимально возможная высота дерева при данном количестве узлов
• Хорошая масштабируемость - с ростом элементов эффективность не падает

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

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

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

АВЛ-деревья

Наиболее известный класс сбалансированных деревьев - АВЛ-деревья. АВЛ в названии происходит от фамилий создателей - Адельсон-Вельский и Ландис. Для АВЛ-деревьев справедливо следующее свойство:

Высоты правого и левого поддеревьев любого узла отличаются не более чем на 1

То есть разница в высоте поддеревьев строго ограничена. Это позволяет гарантировать эффективный поиск за O(log n) операций, где n - число элементов в дереве.

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

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

1. Корень дерева черный
2. Листья (NULL указатели) считаются черными
3. Красный узел не может иметь красного родителя
4. Все пути от узла до листьев содержат одинаковое число черных узлов

Такие правила гарантируют, что дерево остается сбалансированным при любых вставках и удалениях.

Другие разновидности

Кроме АВЛ и красно-черных, существуют и другие сбалансированные деревья - например, деревья Бейлей-Боруэ, АА-деревья, различные гибриды. Однако АВЛ и красно-черные деревья являются наиболее известными и часто используемыми на практике.

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

Принцип работы и операции над АВЛ-деревом

Сбалансированное дерево является одним из ключевых компонентов многих алгоритмов и структур данных. Рассмотрим подробнее устройство АВЛ-деревьев и как с их помощью поддерживается балансировка.

Каждый узел АВЛ-дерева состоит из следующих полей:

• Ключ (значение узла)
• Указатели на левое и правое поддеревья
• Балансировочный фактор (balance factor) - число от -1 до 1

Балансировочный фактор отражает разницу в высоте между поддеревьями данного узла. Он используется, чтобы определить, требуется ли производить балансировку дерева в данной ветви.

Вращения для балансировки

Чтобы восстановить сбалансированность дерева при добавлении или удалении узлов, используются специальные операции вращения поддеревьев. Различают правые и левые вращения.

Правое вращение выполняется за 3 шага:

1. Левое поддерево текущего узла становится правым поддеревом левого потомка
2. Левый потомок становится текущим узлом
3. Текущий узел становится правым потомком старого левого потомка

Алгоритм вставки узла

Процесс вставки нового узла в АВЛ-дерево состоит из следующих этапов:

1. Выполняется стандартная вставка в бинарное дерево поиска
2. По пути наверх обновляются значения балансировочных факторов
3. Если где-либо нарушается свойство балансировки (фактор становится <-1 или > 1), производится вращение этого поддерева
4. Процесс повторяется до корня дерева

Так восстанавливается балансировка после добавления нового элемента.

Алгоритм удаления узла

При удалении узла также сначала происходит стандартное удаление из дерева, как в случае с бинарным деревом поиска. Затем идет процесс балансировки аналогично вставке:

1. Обновляются значения балансировочных факторов при возврате по пути к корню
2. При нарушении баланса производится вращение
3. Балансировка доходит до корня или до первого сбалансированного поддерева

Примеры операций над АВЛ-деревом

Для наглядности рассмотрим на примерах, как при добавлении или удалении элементов происходят вращения в АВЛ-дереве, чтобы сохранить его сбалансированность.

Вставка элемента 50

Пусть имеется следующее сбалансированное АВЛ-дерево. Добавим в него значение 50.

Сначала выполняется стандартная вставка в бинарное дерево поиска. Но при этом левое поддерево элемента 60 становится на 2 уровня глубже правого. Чтобы восстановить баланс, нужно сделать правый поворот в узле 60.

Особенности красно-черных деревьев

Красно-черные деревья имеют некоторые отличия в балансировке по сравнению с АВЛ. Рассмотрим их подробнее.

В дополнение к балансировке высоты поддеревьев, для красно-черных деревьев выполняются еще несколько важных свойств:

• Корень дерева всегда черный
• У каждого красного узла оба дочерних черные
• Все пути от узла до NULL-узлов содержат одинаковое число черных узлов

Эти свойства позволяют упростить проверку балансировки по сравнению с АВЛ-деревьями.

Цветные узлы

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

• Красные - нарушают свойства балансировки
• Черные - удовлетворяют балансировке

При этом чередование цветов в ветвях поддерживает его сбалансированность при любых изменениях.

Правила балансировки

В дополнение к вращениям поддеревьев, в красно-черном дереве действуют правила изменения цвета узлов:

1. Если добавляется красный узел - цвет его родителя меняется на красный
2. При вращениях цвета меняются так, чтобы сохранить правила балансировки
3. Корень всегда перекрашивается в черный после добавления узлов

Таким образом восстанавливается баланс дерева после вставки или удаления элементов.

Вставка и удаление узлов в красно-черном дереве

Процессы вставки и удаления узлов в красно-черных деревьях похожи на аналогичные процедуры для АВЛ, но имеют некоторую специфику.

Одной из ключевых характеристик сбалансированного дерева является его высота, которая напрямую влияет на эффективность работы.

Высоту сбалансированного дерева можно вычислить по следующей формуле:

h = log₂(n+1) - 1

где:

• h - высота дерева
• n - количество элементов (узлов) в дереве

Таким образом, высота пропорциональна двоичному логарифму от числа элементов и при росте дерева увеличивается гораздо медленнее, чем в случае несбалансированного дерева.

Зависимость от количества узлов

Конкретные значения высоты в зависимости от элементов:

• Дерево из 1 элемента - высота = 0
• Дерево из 3 элементов - высота = 1
• Дерево из 7 элементов - высота = 2
• Дерево из 15 элементов - высота = 3
• Дерево из 31 элемента - высота = 4

И так далее - с ростом элементов высота увеличивается медленно, примерно вдвое при удвоении узлов.

Связь высоты и скорости операций

Чем ниже высота сбалансированного дерева, тем меньше в среднем операций потребуется на:

• Поиск элемента в дереве
• Вставку нового узла
• Удаление существующего узла

А низкая высота как раз и поддерживается за счет правил балансировки дерева.

Различия для сбалансированных деревьев

Для разных типов сбалансированных деревьев (АВЛ, красно-черных, B-деревьев) высота одного и того же множества элементов может немного различаться.

Это связано с тем, что правила балансировки у них немного отличаются.

Рассмотрим, какие причины могут нарушить сбалансированность дерева.

Добавление и удаление узлов

Основной причиной нарушения балансировки является добавление или удаление элементов в неудачных местах дерева.

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

Пример добавления элементов

Пусть изначально было сбалансированное дерево. Затем в его правую ветвь последовательно добавили новые элементы.

В итоге правое поддерево стало гораздо выше левого, что нарушило балансировку.

Нарушение правил балансировки

Потеря равновесия также может произойти, если при добавлении элемента нарушаются конкретные правила балансировки.

К примеру, в АВЛ-дереве нельзя допускать разницу высот поддеревьев больше 1. А в красно-черном дереве есть ограничения на цвет узлов.

Как восстановить балансировку

Чтобы после добавления или удаления элементов вернуть дерево в сбалансированное состояние, выполняются специальные процедуры:

• Вращения поддеревьев
• Изменение балансировочных факторов
• Перекрашивание узлов

Эти преобразования возвращают дерево к допустимым значениям высоты ветвей и другим свойствам балансировки.

В этой статье мы подробно рассмотрели, что такое сбалансированное дерево - дерево поиска, в котором для каждого узла высоты его поддеревьев отличаются не более чем на единицу. Обсудили различные виды сбалансированных деревьев, их преимущества, принципы балансировки при добавлении и удалении элементов. Разобрали алгоритмы вставки и удаления узлов в популярных структурах данных - АВЛ-деревьях и красно-черных деревьях. Данная информация пригодится и будет полезна тем, кто интересуется математикой, физикой и информатикой.