Определение и свойства АВЛ-деревьев

АВЛ-дерево названо в честь изобретателей этого метода Г.М. Адельсона-Вельского и E.М. Ландиса, которые дали ему следующее определение. Дерево называется АВЛ-деревом, если для любого его узла высоты левого и правого поддеревьев отличаются не более чем на 1. АВЛ-дерево называют сбалансированным по высоте.

Согласно определению, сбалансированность АВЛ-дерева должна проверяться для каждого его узла. С этой целью вводится дополнительная характеристика каждого узла, которая называется показателем сбалансированности узла или балансом узла. Этот показатель представляет собой разность между высотой правого и левого поддерева узла (сами высоты поддеревьев не важны, так как только разность является мерой сбалансированности). Для сбалансированного дерева этот показатель может принимать всего три значения (рис.5.4):

· 0— высоты поддеревьев равны;

· -1 — левое поддерево немного перевешивает;

· 1 — правое поддерево немного перевешивает.

Рис.5.4. Значения показателя сбалансированности

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

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

Рис.5.5. Пример АВЛ-дерева с расставленными балансами узлов

Авторами АВЛ-дерева доказано, что при наличии n узлов высота дерева находится в интервале от log₂(n+1)-1, что соответствует полному бинарному дереву, до 1,44 log₂(n+2)-1,33 для наихудшего случая (доказательство приводится в [8, 21]). Иными словами, оно гарантированно обеспечивает время поиска, не превышающее наилучший случай более чем на 45%.

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

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

Вращения

Вращениями называются такие изменения структуры дерева, которые не меняют содержащуюся в нем информацию и не нарушают упорядоченности, но приводят к более сбалансированной структуре. Иными словами, после выполнения вращения последовательность, полученная при помощи ЛКП обхода дерева, не должна измениться.

Для балансировки АВЛ-дерева используют четыре вида вращений: левое и правое малые вращения затрагивают два узла вместе с их поддеревьями, левое и правое большое вращения затрагивают три узла с их поддеревьями. Большие вращения представляют собой комбинацию двух малых, поэтому их иногда называют комбинированными или двукратными (а малые — однократными).

Начнем с малых вращений. Сначала рассмотрим примеры. На рис.5.6 показано дерево всего с двумя узлами (узел 7 является правым сыном узла 5). Ясно, что поворот рисунка не нарушил упорядоченности дерева, но изменил его структуру. Теперь узел 5 стал левым сыном узла 7. Такое преобразование называется малым правым вращением (понятия левое и правое в данном случае весьма условны, мы пользуемся терминологией из [Вирт, Шень]). Если на рис.5.6 изменить направление стрелки, то будем иметь левое малое вращение.

Рис.5.6. Простой пример малого правого вращения

Однако в данном случае никакой необходимости во вращении не было, так как дерево из двух узлов всегда сбалансировано. Поэтому усложним пример — нарушен баланс в узле 5 (рис.5.7). Сбалансированность можно восстановить при помощи малого правого вращения для узлов 5 и 7, как на предыдущем рисунке, при этом получим идеально сбалансированное дерево. Из данного примера понятно, что вращение не сводится к простому повороту рисунка, поскольку левое поддерево узла 7 стало теперь правым поддеревом узла 5.

Рис.5.7. Восстановление сбалансированности при помощи малого правого вращения

Сформулируем правило малого правого вращения. Пусть вершина a имеет правого сына b. Обозначим через P левое поддерево вершины a, через Q и R — левое и правое поддеревья вершины b (рис.5.8). Упорядоченность дерева требует выполнения условия P<a<Q<b<R. Точно того же требует упорядоченность дерева с корнем b, которое изображено на рисунке справа. Поэтому данное преобразование не нарушает упорядоченности дерева, но уменьшает на единицу его высоту, что нам и нужно. Аналогично выполняется малое левое вращение.

 

Рис.5.8. Общее правило для малого правого вращения

Кроме малых вращений в АВЛ-дереве используются еще большие вращения, которые затрагивают три узла дерева с их поддеревьями. Сначала простой пример — дерево из трех узлов (рис.5.9), у которого нарушенный баланс узла 4, восстанавливается с помощью большого правого вращения.

Рис.5.9. Простой пример большого правого вращения

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

Рис.5.10. Более сложный пример большого правого вращения

Общее правило показано на рис.5.11. Аналогично определяется большое левое вращение — достаточно поменять направление стрелки на рис.5.11.

Рис.5.11. Общее правило большого правого вращения

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

Например, рассмотрим процесс построения АВЛ-дерева из последовательности элементов 4 5 7 2 1 3 6 (данный пример приводится в [4] и хорош тем, что позволяет продемонстрировать все четыре вида вращений). Если использовать обычный алгоритм вставки каждого узла в качестве листа бинарного дерева поиска, то получим дерево, изображенное на рис. 5.12.

Рис.5.12. Бинарное дерево поиска, построенное при помощи обычного алгоритма вставки

Данное дерево не сбалансировано в узлах 2 и 5, его высота равна трем. Попробуем построить из этой же последовательности сбалансированное дерево высоты 2, используя вращения. Процесс построения дерева изображен на рис.5.13, пунктирная связь проведена к тому узлу, который добавляется на каждом этапе.

а) добавление одного элемента к корню не может нарушить упорядоченности

 

 

б) теперь корень(4) не сбалансирован— выполнили малое правое вращение (узлы 4 и 5)

в)сбалансированность не нарушилась

г) выполнили малое левое вращение (узлы 4 и 2)

д) выполнили большое левое вращение (узлы 5, 2 и 4)

е) выполнили большое правое вращение (узлы 5,7 и 6)

Рис.5.13. Последовательность построения АВЛ-дерева из значений 4 5 7 2 1 3 6.

Теперь дерево полностью сбалансировано, а высота его равна двум. Интересно, что в данном случае удалось получить полное бинарное дерево (все листья в одном нижнем уровне), поскольку количество узлов равно 7. При произвольных данных результат был бы несколько хуже.

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