авл дерево что это

АВЛ-дерево.

АВЛ-дерево – структура данных, изобретенная в 1968 году двумя советскими математиками: Евгением Михайловичем Ландисом и Георгием Максимовичем Адельсон-Вельским. Прежде чем дать конструктивное определение АВЛ-дереву, сделаем это для сбалансированного двоичного дерева поиска.

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

АВЛ-дерево – сбалансированное двоичное дерево поиска с k=1. Для его узлов определен коэффициент сбалансированности (balance factor). Balance factor – это разность высот правого и левого поддеревьев, принимающая одно значение из множества <-1, 0, 1>. Ниже изображен пример АВЛ-дерева, каждому узлу которого поставлен в соответствие его реальный коэффициент сбалансированности.

Пример АВЛ-дерева

Положим B_i – коэффициент сбалансированности узла T_i (i – номер узла, отсчитываемый сверху вниз от корневого узла по уровням слева направо). Balance factor узла T_i рассчитывается следующим образом. Пусть функция h() с параметрами T_iи L возвращает высоту левого поддерева L узла T_i, а с T_i и R – правого. Тогда B_i=h(T_i, R)-h(T_i, L). Например, B₄=-1, так как h(T₄, R)-h(T₄, L)=0-1=-1.

Сбалансированное дерево эффективно в обработке, что следует из следующих рассуждений. Максимальное количество шагов, которое может потребоваться для обнаружения нужного узла, равно количеству уровней самого бинарного дерева поиска. А так как поддеревья сбалансированного дерева, «растущие» из произвольного корня, практически симметричны, то и его листья расположены на сравнительно невысоком уровне, т. е. высота дерева сводиться к оптимальному минимуму. Поэтому критерий баланса положительно сказывается на общей производительности. Но в процессе обработки АВЛ-дерева, балансировка может нарушиться, тогда потребуется осуществить операцию балансировки. Помимо нее, над АВЛ-деревом определены операции вставки и удаления элемента. Именно выполнение последних может привести к дисбалансу дерева.

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

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

Источник

АВЛ-дерево

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

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

Содержание

Высота дерева [ править ]

Допустим [math]m_h = F_ — 1[/math] — верно.

Таким образом, равенство [math]m_h = F_ — 1[/math] — доказано. [math]\triangleleft[/math]

[math]n \geqslant \varphi^[/math]

[math]\log_<\varphi>n \geqslant h[/math]

Балансировка [ править ]

Для балансировки вершины используются один из 4 типов вращений:

[math]diff[a] = 0[/math] и [math]diff[b] = 0[/math]

Малый левый поворот:

Большой левый поворот пишется проще:

Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению. В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на [math]1[/math] и не может увеличиться.

Все вращения, очевидно, требуют [math]O(1)[/math] операций.

Операции [ править ]

Добавление вершины [ править ]

Так как в процессе добавления вершины мы рассматриваем не более, чем [math] O(h) [/math] вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет [math] O(\log) [/math] операций.

Удаление вершины [ править ]

Поиск вершины, минимум/максимум в дереве, etc. [ править ]

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

Слияние двух AVL-деревьев [ править ]

Дерево [math]T_1[/math] и [math]T_2[/math] до слияния

Дерево [math]T_2[/math] после слияния

Алгоритм разделения AVL-дерева на два [ править ]

Алгоритм первый [ править ]

Далее действуем по алгоритму и в итоге получаем (рис. 4):

Алгоритм второй [ править ]

АВЛ-дерево с O(1) бит в каждом узле [ править ]

Идея [ править ]

Операции [ править ]

Балансировка [ править ]

Тип вращения	Иллюстрация	Когда используется	Расстановка балансов
Малое левое вращение

1 вариант: [math]balance[a] = 0[/math] и [math]balance[b] = 0[/math]

Примеры [ править ]

Ниже приведены примеры добавления и удаления вершины с подписанными изменениями факторов баланса каждой вершины.

Источник

АВЛ-деревья

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

Понятие АВЛ-дерева

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

Особенностью АВЛ-дерева является то, что оно является сбалансированным в следующем смысле: для любого узла дерева высота его правого поддерева отличается от высоты левого поддерева не более чем на единицу. Доказано, что этого свойства достаточно для того, чтобы высота дерева логарифмически зависела от числа его узлов: высота h АВЛ-дерева с n ключами лежит в диапазоне от log₂(n + 1) до 1.44 log₂(n + 2) − 0.328. А так как основные операции над двоичными деревьями поиска (поиск, вставка и удаление узлов) линейно зависят от его высоты, то получаем гарантированную логарифмическую зависимость времени работы этих алгоритмов от числа ключей, хранимых в дереве. Напомним, что рандомизированные деревья поиска обеспечивают сбалансированность только в вероятностном смысле: вероятность получения сильно несбалансированного дерева при больших n хотя и является пренебрежимо малой, но остается не равной нулю.

Структура узлов

Будем представлять узлы АВЛ-дерева следующей структурой:

Поле key хранит ключ узла, поле height — высоту поддерева с корнем в данном узле, поля left и right — указатели на левое и правое поддеревья. Простой конструктор создает новый узел (высоты 1) с заданным ключом k.

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

Вторая вычисляет balance factor заданного узла (и работает только с ненулевыми указателями):

Третья функция восстанавливает корректное значение поля height заданного узла (при условии, что значения этого поля в правом и левом дочерних узлах являются корректными):

Заметим, что все три функции являются нерекурсивными, т.е. время их работы есть величина О(1).

Балансировка узлов

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

Левый поворот является симметричной копией правого:

Рассмотрим теперь ситуацию дисбаланса, когда высота правого поддерева узла p на 2 больше высоты левого поддерева (обратный случай является симметричным и реализуется аналогично). Пусть q — правый дочерний узел узла p, а s — левый дочерний узел узла q.

Анализ возможных случаев в рамках данной ситуации показывает, что для исправления расбалансировки в узле p достаточно выполнить либо простой поворот влево вокруг p, либо так называемый большой поворот влево вокруг того же p. Простой поворот выполняется при условии, что высота левого поддерева узла q больше высоты его правого поддерева: h(s)≤h(D).

Большой поворот применяется при условии h(s)>h(D) и сводится в данном случае к двум простым — сначала правый поворот вокруг q и затем левый вокруг p.

Код, выполняющий балансировку, сводится к проверке условий и выполнению поворотов:

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

Вставка ключей

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

Чтобы проверить соответствие реализованного алгоритма вставки теоретическим оценкам для высоты АВЛ-деревьев, был проведен несложный вычислительный эксперимент. Генерировался массив из случайно расположенных чисел от 1 до 10000, далее эти числа последовательно вставлялись в изначально пустое АВЛ-дерево и измерялась высота дерева после каждой вставки. Полученные результаты были усреднены по 1000 расчетам. На следующем графике показана зависимость от n средней высоты (красная линия); минимальной высоты (зеленая линия); максимальной высоты (синяя линия). Кроме того, показаны верхняя и нижняя теоретические оценки.

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

Удаление ключей

С удалением узлов из АВЛ-дерева, к сожалению, все не так шоколадно, как с рандомизированными деревьями поиска. Способа, основанного на слиянии (join) двух деревьев, ни найти, ни придумать не удалось. Поэтому за основу был взят вариант, описываемый практически везде (и который обычно применяется и при удалении узлов из стандартного двоичного дерева поиска). Идея следующая: находим узел p с заданным ключом k (если не находим, то делать ничего не надо), в правом поддереве находим узел min с наименьшим ключом и заменяем удаляемый узел p на найденный узел min.

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

Пусть теперь правое поддерево у p есть. Находим минимальный ключ в этом поддереве. По свойству двоичного дерева поиска этот ключ находится в конце левой ветки, начиная от корня дерева. Применяем рекурсивную функцию:

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

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

Как только ключ k найден, переходим к плану Б: запоминаем корни q и r левого и правого поддеревьев узла p; удаляем узел p; если правое поддерево пустое, то возвращаем указатель на левое поддерево; если правое поддерево не пустое, то находим там минимальный элемент min, потом его извлекаем оттуда, слева к min подвешиваем q, справа — то, что получилось из r, возвращаем min после его балансировки.

При выходе из рекурсии не забываем выполнить балансировку:

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

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

Источник

АВЛ-дерево

АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

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

Содержание

Общие свойства

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

где — золотое сечение,

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

Тип дерева можно описать так

AVL-условия можно проверить так

Балансировка

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

Данное вращение используется тогда, когда (высота b-поддерева — высота R) = 2 и высота С высота L.

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

Также можно заметить, что большое вращение это комбинация правого и левого малого вращения.

Из-за условия балансированности высота дерева О(log(N)), где N- количество вершин, поэтому добавление элемента требует O(log(N)) операций.

Алгоритм добавления вершины

Показатель сбалансированности в дальнейшем будем интерпретировать как разность между высотой левого и правого поддерева, а алгоритм будет основаться на типе TAVLTree, описанном выше. Непосредственно при вставке (листу) присваивается нулевой баланс. Процесс включения вершины состоит из трех частей:

В третьей ситуации требуется определить балансировку левого поддерева. Если левое поддерево этой вершины (Tree^.left^.left) выше правого (Tree^.left^.right), то требуется большое правое вращение, иначе хватит малого правого. Аналогичные (симметричные) рассуждения можно привести и для включение в правое поддерево.

вспомогательная функция сравнивающая два ключа

Рекурсивная процедура вставки:

Алгоритм удаления вершины

Упрощённый вариант удаления можно описать таким образом

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

Очевидно, в результате указанных действий процедура удаления вызывается не более 3 раз, так как у вершины, удаляемой по 2-му вызову, нет одного из поддеревьев. Но поиск ближайшего каждый раз требует O(N) операций, отсюда видна очевидная оптимизация: поиск ближайшей вершины производится по краю поддерева. Отсюда количество действий O(log(N)).

Нерекурсивная вставка в АВЛ-дерево сверху-вниз

Нерекурсивный алгоритм сложнее чем рекурсивная реализация.

Нерекурсивное удаление из АВЛ-дерева сверху-вниз

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

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

Расстановка балансов при удалении

Как уже говорилось, если удаляемая вершина — лист, то она удаляется, и обратный обход дерева происходит от родителя удалённого листа. Если не лист — ей находится «замена», и обратный обход дерева происходит от родителя «замены». Непосредственно после удаления элемента — «замена» получает баланс удаляемого узла.

При обратном обходе: если при переходе к родителю пришли слева — баланс увеличивается на 1, если же пришли справа — уменьшается на 1.

Это делается до тех пор, пока при изменении баланса он не станет равным −1 или 1 (обратите внимание на различие с вставкой элемента!): в данном случае такое изменение баланса будет гласить о неизменной дельта-высоте поддеревьев. Повороты происходят по тем же правилам, что и при вставке.

Расстановка балансов при одинарном повороте

Если поворот осуществляется при вставке элемента, то баланс Pivot’а равен либо 1, либо −1. В таком случае после поворота балансы обоих устанавливаются равными 0.

При удалении всё иначе: баланс Pivot’а может стать равным 0 (в этом легко убедиться).

Приведём сводную таблицу зависимости финальных балансов от направления поворота и исходного баланса узла Pivot:

Тип вращения	Иллюстрация	Факторы балансов до вращения	Факторы балансов после вращения
Малое левое вращение

Направление поворота	Old Pivot.Balance	New Current.Balance	New Pivot.Balance
Левый или Правый	-1 или +1	0	0
Правый	0	-1	+1
Левый	0	+1	-1

Расстановка балансов при двойном повороте

Pivot и Current — те же самые, но добавляется третий участник поворота. Обозначим его за «Bottom»: это (при двойном правом повороте) левый сын Pivot’а, а при двойном левом — правый сын Pivot’а.

При данном повороте — Bottom в результате всегда приобретает баланс 0, но от его исходного баланса зависит расстановка балансов для Pivot и Current.

Приведём сводную таблицу зависимости финальных балансов от направления поворота и исходного баланса узла Bottom:

Направление	Old Bottom.Balance	New Current.Balance	New Pivot.Balance
Левый или Правый	0	0	0
Правый	+1	0	-1
Правый	-1	+1	0
Левый	+1	-1	0
Левый	-1	0	+1

Оценка эффективности

Г.М.Адельсон-Вельский и Е.М.Ландис доказали теорему, согласно которой высота АВЛ-дерева с N внутренними вершинами заключена между log2(N+1) и 1.4404*log2(N+2)-0.328, то есть высота АВЛ-дерева никогда не превысит высоту идеально сбалансированного дерева более, чем на 45%. Для больших N имеет место оценка 1.04*log2(N). Таким образом, выполнение основных операций 1 – 3 требует порядка log₂(N) сравнений. Экспериментально выяснено, что одна балансировка приходится на каждые два включения и на каждые пять исключений.

Источник