Реализации алгоритмов/АВЛ-дерево: различия между версиями

то имеем оценку на высоту АВЛ-дерева <math>h = O(log(n))</math>, где <math>n</math> — число узлов. Следует помнить, что <math>O(log(n))</math> — [[wikt:мажоранта|мажоранта]], и её можно использовать только для оценки (Например, если в дереве только два узла, значит в дереве два уровня, хотя <math>log(2)=1</math>). Для точной оценки глубины дерева следует использовать пользовательскую подпрограмму.

 

function TreeDepth(Tree : TAVLTree) : byte;

begin

result := 0;

end;

 

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

TKey = LongInt;

TInfo = LongInt;

end;

TAVLTree = PAVLNode;

 

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

function TestAVLTree(V:PAVLNode):integer; //возвращает высоту дерева

var a,b:integer;

Result:=1+max(a,b);

end;

 

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

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

//Функция для устранения правого нарушения с помощью вышеописанных поворотов,

//возвращает True если высота дерева уменьшилась, False - если осталась той же

end;

end;

 

3.'''Малое правое вращение'''

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

 

//Функция для устранения левого нарушения с помощью вышеописанных поворотов,

//возвращает True если высота дерева уменьшилась, False - если осталась той же

end;

 

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

 

 

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

function KeyCompare(const V1,V2:TKey):integer;

begin

Result:=1;

end;

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

function AVL_InsertNode(Var Tree : TAVLTree; const aKey : TKey; const ainfo : TInfo): Boolean;

Var

end;

end;

 

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

 

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

// Функция очень далека от оптимальной,

// сравнение происходит даже после нахождения удаляемого ключа

end;

end;

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

 

 

 

type

PAVLTree = ^TAVLTree; //дополнительный тип для указания на место, где хранится указатель на лист

Result := true;

end;

 

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

# высота дерева по направлению движения меньше противоположной(«брат» направления) и баланс «брата» равен 0 (разбор этого варианта довольно сложен, так что пока без доказательства)

 

function AVL_DropNode2(var Root : PAVLNode; const Key : TKey): Boolean;

var PrimeNode, p, q, b : PAVLTree;

Dispose(DroppedNode);

end;

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

# ищем удаляемый элемент и попутно находим нашу замечательную вершину