10-05-2024
АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.
АВЛ — аббревиатура, образованная первыми буквами создателей (советских учёных) Адельсон-Вельского Георгия Максимовича и Е. М. Ландиса.
Содержание |
В АВЛ-дереве высоты имеется не меньше узлов, где — число Фибоначчи. Поскольку ,
где — золотое сечение,
то имеем оценку на высоту АВЛ-дерева , где — число узлов. Следует помнить, что — мажоранта, и ее можно использовать только для оценки (Например, если в дереве только два узла, значит в дереве два уровня, хотя ). Для точной оценки глубины дерева следует использовать пользовательскую подпрограмму.
function TreeDepth(Tree : TAVLTree) : byte; begin if Tree <> nil then result := 1 + Max(TreeDepth(Tree^.left),TreeDepth(Tree^.right)) else result := 0; end;
Тип дерева можно описать так
TKey = LongInt; TInfo = LongInt; TBalance = -1..1; TAVLTree = ^ TAVLNode; TAVLNode = record left, right : TAVLTree; key : TKey; info : TInfo; { Поле определяющее сбалансированность вершины } balance : TBalance; end;
Относительно АВЛ-дерева балансировкой вершины называется операция, которая в случае разницы высот левого и правого поддеревьев = 2, изменяет связи предок-потомок в поддереве данной вершины так, что разница становится <= 1, иначе ничего не меняет. Указанный результат получается вращениями поддерева данной вершины.
Используются 4 типа вращений:
1.Малое левое вращение
Данное вращение используется тогда, когда (высота b-поддерева - высота L) = 2 и высота С <= высота R.
2.Большое левое вращение
Данное вращение используется тогда, когда (высота b-поддерева - высота L) = 2 и высота c-поддерева > высота R.
3.Малое правое вращение
Данное вращение используется тогда, когда (высота b-поддерева — высота R) = 2 и высота С <= высота L.
4.Большое правое вращение
Данное вращение используется тогда, когда (высота b-поддерева - высота R) = 2 и высота c-поддерева > высота L.
В каждом случае достаточно просто доказать то, что операция приводит к нужному результату и что полная высота уменьшается не более чем на 1 и не может увеличиться.
Из-за условия балансированности высота дерева О(lg(N)), где N- количество вершин, поэтому добавление элемента требует O(lg(N)) операций.
Показатель сбалансированности в дальнейшем будем интерпретировать как разность между высотой левого и правого поддерева, а алгоритм будет основаться на типе TAVLTree, описанном выше. Непосредственно при вставке (листу) присваивается нулевой баланс. Процесс включения вершины состоит из трех частей:
Расширим список параметров обычной процедуры вставки параметром-переменной flag, означающим, что высота дерева увеличилась. Предположим, что процесс из левой ветви возвращается к родителю (рекурсия идет назад), тогда возможны три случая: { hl - высота левого поддерева, hr - высота правого поддерева } Включение вершины в левое поддерево приведет к
В третьей ситуации требуется определить балансировку левого поддерева. Если левое поддерево этой вершины (Tree^.left^.left) выше правого (Tree^.left^.right), то требуется большое правое вращение, иначе хватит малого правого. Аналогичные (симметричные) рассуждения можно привести и для включение в правое поддерево. Процедура вставки, предложенная Н.Виртом
procedure TAVL.InsertNode(Var Tree : TAVLTree; const akey : TKey; const ainfo : TInfo; Var flag : Boolean); Var Node1, Node2 : TAVLTree; begin if Tree = nil then begin New(Tree); flag := true; with Tree^ do begin key := akey; info := ainfo; left := nil; right := nil; balance := 0; end; inc(AVL.FNodes); end else if Tree^.key > akey then begin InsertNode(Tree^.left,akey,ainfo,flag); if flag then case Tree^.balance of 1 : begin Tree^.balance := 0; flag := false; end; 0 : Tree^.balance := -1; -1 : { Balance } begin Node1 := Tree^.left; if Node1^.balance = -1 then { LL } begin Tree^.left := Node1^.right; Node1^.right := Tree; Tree^.balance := 0; Tree := Node1; end else {LR} begin Node2 := Node1^.right; Node1^.right := Node2^.left; Node2^.left := Node1; Tree^.left := Node2^.right; Node2^.right := Tree; if Node2^.balance = -1 then Tree^.balance := 1 else Tree^.balance := 0; if Node2^.balance = 1 then Node1^.balance := -1 else Node1^.balance := 0; Tree := Node2; end; Tree^.balance := 0; flag := false end end end else if Tree^.key < akey then begin InsertNode(Tree^.right,akey,ainfo,flag); if flag then case Tree^.balance of -1 : begin Tree^.balance := 0; flag := false; end; 0 : Tree^.balance := 1; 1 : { Balance } begin Node1 := Tree^.right; if Node1^.balance = 1 then { RR } begin Tree^.right := Node1^.left; Node1^.left := Tree; Tree^.balance := 0; Tree := Node1; end else {RL} begin Node2 := Node1^.left; Node1^.left := Node2^.right; Node2^.right := Node1; Tree^.right := Node2^.left; Node2^.left := Tree; if Node2^.balance = 1 then Tree^.balance := -1 else Tree^.balance := 0; if Node2^.balance = -1 then Node1^.balance := 1 else Node1^.balance := 0; Tree := Node2; end; Tree^.balance := 0; flag := false end end end end;
Для простоты опишем рекурсивный алгоритм удаления. Если вершина - лист, то удалим её и вызовем балансировку всех её предков в порядке от родителя к корню. Иначе найдём самую близкую по значению вершину в поддереве наибольшей высоты (правом или левом) и переместим её на место удаляемой вершины, при этом вызвав процедуру её удаления.
Докажем, что данный алгоритм сохраняет балансировку. Для этого докажем по индукции по высоте дерева, что после удаления некоторой вершины из дерева и последующей балансировки высота дерева уменьшается не более, чем на 1. База индукции: Для листа очевидно верно. Шаг индукции: Либо условие балансированности в корне (после удаления корень может изменится) не нарушилось, тогда высота данного дерева не изменилась, либо уменьшилось строго меньшее из поддеревьев => высота до балансировки не изменилась => после уменьшится не более чем на 1.
Очевидно, в результате указанных действий процедура удаления вызывается не более 3 раз, так как у вершины, удаляемой по 2-му вызову, нет одного из поддеревьев. Но поиск ближайшего каждый раз требует O(N) операций, отсюда видна очевидная оптимизация: поиск ближайшей вершины производится по краю поддерева. Отсюда количество действий O(log(N)).
Как уже говорилось, если удаляемая вершина — лист, то она удаляется, и обратный обход дерева происходит от родителя удалённого листа. Если не лист — ей находится «замена», и обратный обход дерева происходит от родителя «замены». Непосредственно после удаления элемента — «замена» получает баланс удаляемого узла.
При обратном обходе: если при переходе к родителю пришли слева — баланс увеличивается на 1, если же пришли справа — уменьшается на 1.
Это делается до тех пор, пока при изменении баланса он не станет равным −1 или 1 (обратите внимание на различие с вставкой элемента!): в данном случае такое изменение баланса будет гласить о неизменной дельта-высоте поддеревьев. Повороты происходят по тем же правилам, что и при вставке.
Обозначим:
«Current» — узел, баланс которого равен −2 или 2: то есть тот, который нужно повернуть (на схеме - элемент a)
«Pivot» — ось вращения. +2: левый сын Current’а, −2: правый сын Current’а (на схеме - элемент b)
Если поворот осуществляется при вставке элемента, то баланс 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 требует порядка log2(N) сравнений. Экспериментально выяснено, что одна балансировка приходится на каждые два включения и на каждые пять исключений.
Это заготовка статьи по информатике. Вы можете помочь проекту, исправив и дополнив её. |
Дерево (структура данных) | |
---|---|
Двоичное дерево поиска · Дерево (теория графов) · Древовидная структура | |
Двоичные деревья | Двоичное дерево · T-дерево |
Самобалансирующиеся двоичные деревья | АА-дерево · АВЛ-дерево · Красно-чёрное дерево · Расширяющееся дерево · Дерево со штрафами · Декартово дерево · Дерево Фибоначчи |
B-деревья | B-дерево · 2-3-дерево · B+ дерево · B*-дерево · UB-дерево · 2-3-4 дерево · (a,b)-дерево · Танцующее дерево |
Префиксные деревья | Суффиксное дерево · Radix tree · Ternary search tree |
Двоичное разбиение пространства | k-мерное дерево · VP-дерево |
Недвоичные деревья | Дерево квадрантов · Октодерево · Sparse Voxel Octree · Экспоненциальное дерево · PQ-дерево |
Разбиение пространства | R-дерево · R+-дерево · R*-дерево · X-дерево · M-дерево · Дерево Фенвика · Дерево отрезков |
Другие деревья | Куча · TTH · Finger tree · Metric tree · Cover tree · BK-tree · Doubly-chained tree · iDistance · Link-cut tree |
Алгоритмы | Поиск в ширину · Поиск в глубину · DSW-алгоритм · Алгоритм связующего дерева |
Авл-дерево приложения теории графов, авл-дерево питон, авл дерево и бинарное дерево, авл дерево онлайн построение.