(* 1962 год: Георгий Максимович Адельсон-Вельский *) (* Евгений Михайлович Ландис *) |
type pDoTree = ^DoTree; DoTree = record Key : integer; Depth : integer; Left,Right : pDoTree; REFF : pRecord end; |
(* Ba(P) := Баланс вершины P *) function Ba(P : pDoTree) : integer; var L,R : integer; begin L:=0; R:=0; if P <> nil then with P^ do begin if Left <> nil then L:= Left^.Depth; if Right <> nil then R:=Right^.Depth end; Ba:=R-L end; |
(* xDepth(P) - вычислить поле P^.Depth при условии, что *) (* P^.Left^.Depth и P^.Right^.Depth - правильные значения *) procedure xDepth(P : pDoTree); var L,R : integer; begin if P <> nil then with P^ do begin L:=0; R:=0; if Left <> nil then L:= Left^.Depth; if Right <> nil then R:=Right^.Depth; if L < R then Depth:=R+1 else Depth:=L+1 end end; |
(* Take и Link - элементарные операции для модификации бинарных деревьев *) procedure Take(var A,B,C : pDoTree); begin B:=A^.Left; C:=A^.Right end; procedure Link(var A,B,C : pDoTree); begin A^.Left:=B; A^.Right:=C end; |
(* Здесь и далее используется *) (* Соглашение о скобочной записи бинарных деревьев поиска >> см. *) |
(* RR-правило преобразования AVL-деревьев: *) (* Фрагмент дерева вида (A A1 (B B1 C)), где Ba(A)=2 и Ba(B)=1 *) (* преобразовать к виду (B (A A1 B1) C) *) (* Замечание 1. A1 и B1 могут быть nil, лист или поддерево. *) (* Замечание 2. В результате преобразования балансы вершин *) (* A и B изменяют значения на Ba(A)=0 и Ba(B)=0 *) function RR(var P : pDoTree) : boolean; var A,A1,B,B1,C : pDoTree; begin RR:=false; if Ba(P ) = 2 then if Ba(P^.Right) = 1 then begin A:=P; (* Левая часть *) Take(A,A1,B ); Take(B,B1,C ); Link(A,A1,B1); xDepth(A); (* Правая часть *) Link(B,A ,C ); xDepth(B); P:=B; RR:=true end end; |
(* RL-правило преобразования AVL-деревьев: *) (* Фрагмент дерева вида (A A1 (C (B B1 B2) C1)), *) (* где Ba(A)=2 и Ba(C)=-1 *) (* преобразовать к виду (B (A A1 B1) (C B2 C1)) *) (* Замечание 1. A1, B1, B2 и C1 могут быть nil/лист/поддерево. *) (* Замечание 2. В результате преобразования: *) (* Ba(B) = 0, abs(Ba(A)) <= 1 и abs(Ba(C)) <= 1 *) function RL(var P : pDoTree) : boolean; var A,A1,B,B1,B2,C,C1 : pDoTree; begin RL:=false; if Ba(P ) = 2 then if Ba(P^.Right) = -1 then begin A:=P; (* Левая часть *) Take(A,A1,C ); Take(C,B ,C1); Take(B,B1,B2); Link(A,A1,B1); xDepth(A); (* Правая часть *) Link(C,B2,C1); xDepth(C); Link(B,A ,C ); xDepth(B); P:=B; RL:=true end end; |
(* RL1 - альтернативная реализация RL-правила, *) (* минимизирующая изменения в дереве и набор переменных. *) (* Почувствуйте разницу. *) function RL1(var P : pDoTree) : boolean; var Q,R : pDoTree; begin RL1:=false; if Ba(P ) = 2 then if Ba(P^.Right) = -1 then begin Q:=P^.Right; R:=Q^.Left; Q^.Left :=R^.Right; R^.Right:=Q; P^.Right:=R^.Left; R^.Left :=P; xDepth(P); xDepth(Q); xDepth(R); P:=R; RL1:=true end end; |
(* LL-правило преобразования AVL-деревьев: *) (* Фрагмент дерева вида (C (B A B1) C1), где Ba(A)=-2, Ba(B)=-1 *) (* преобразовать к виду (B A (C B1 C1)) *) (* Замечание 1. B1 и C1 могут быть nil/лист/поддерево. *) (* Замечание 2. В результате преобразования: Ba(B)=0, Ba(C)=0 *) function LL(var P : pDoTree) : boolean; var A,B,B1,C,C1 : pDoTree; begin LL:=false; if Ba(P ) = -2 then if Ba(P^.Left) = -1 then begin C:=P; (* Левая часть *) Take(C,B ,C1); Take(B,A ,B1); Link(C,B1,B1); xDepth(C); (* Правая часть *) Link(B,A ,C ); xDepth(B); P:=B; LL:=true end end; |
(* LR-правило преобразования AVL-деревьев: *) (* Фрагмент дерева вида (C (A A1 (B B1 B2)) C1), *) (* где Ba(A)=-2 и Ba(A)=1 *) (* преобразовать к виду (B (A A1 B1) (C B2 C1)) *) (* Замечание 1. A1, B1, B2 и C1 могут быть nil/лист/поддерево. *) (* Замечание 2. В результате преобразования: *) (* Ba(B) = 0, abs(Ba(A)) <= 1 и abs(Ba(C)) <= 1 *) function LR(var P : pDoTree) : boolean; var A,A1,B,B1,B2,C,C1 : pDoTree; begin LR:=false; if Ba(P ) = -2 then if Ba(P^.Left) = 1 then begin C:=P; (* Левая часть *) Take(C,A ,C1); Take(A,A1,B ); Take(B,B1,B2); Link(A,A1,B1); xDepth(A); (* Правая часть *) Link(C,B2,C1); xDepth(C); Link(B,A ,C ); xDepth(B); P:=B; LR:=true end end; |
(* MDF - сводная процедура модификации вершины *) (* P в области изменений AVL-дерева *) procedure MDF(var P : pDoTree); begin if RR(P) then else if RL(P) then else if LL(P) then else if LR(P) then else xDepth(P) end; |
(* BRN : связать с указателем P новую *) (* вершину AVL-дерева, соответствующую ключу K *) procedure BRN(var P : pDoTree; K : integer); begin new(P); with P^ do begin Key :=K; Depth:=1; Left :=nil; Right:=nil; REFF :=nil end end; |
(* FormAVL - включить в AVL-дерево D вершину с ключом K *) (* FormAVL(D,K)= указатель X на вершину с ключом K *) (* если X^.REFF = nil, то X - новая вершина *) (* если X^.REFF<> nil, то X - уже была *) function FormAVL(var D : pDoTree; K : integer) : pDoTree; var Res : pDoTree; procedure Fo(var D : pDoTree); begin if D = nil then begin BRN(D,K); Res:=D end else with D^ do if Key = K then Res:=D else if Key < K then Fo(Right) else Fo(Left ); MDF(D) end; begin Fo(D); FormAVL:=Res end; |
(* FormAVL1 - альтернативная реализация функции FormAVL, без Res *) function FormAVL1(var D : pDoTree; K : integer) : pDoTree; procedure Fo(var D : pDoTree); begin if D = nil then begin BRN(D,K); FormAVL1:=D end else with D^ do if Key = K then FormAVL1:=D else if Key < K then Fo(Right) else Fo(Left ); MDF(D) end; begin Fo(D) end; |
(* Пример. Пусть D указывает на AVL-дерево (T20 T10 (T30 T25 T40)) *) (* где T20 - вершина с ключом 20, T10 - вершина с ключом 10 и т.д. *) (* Рассмотрим ход вычисления X:=FormAVL(D,22): Fo(D) - рек.вызов *) (* Fo(D^.Right); MDF(D) - рек.вызов *) (* Fo(D^.Right^.Left); MDF(D^.Right); MDF(D) - рек.вызов *) (* Fo(DRLL); MDF(DRLL); MDF(D^.Right^.Left); MDF(D^.Right); MDF(D) - конец рек.*) (* где DRLL = D.Right^.Left^.Left *) (* Фактически вызов FormAVL(D,22) развернулся в последовательность вызовов: *) (* BRN(D^.Right^.Left^.Left,22), причем D^.Right^.Left^.Left = T25.Left = nil *) (* MDF(D^.Right^.Left^.Left), причем D^.Right^.Left^.Left - ук. на новую T22 *) (* MDF(D^.Right^.Left), причем D^.Right^.Left - указатель на T25 *) (* MDF(D^.Right); причем D^.Right - указатель на T30 *) (* MDF(D) *) (* Вычисление этой последовательности приводит к следующим результатам: *) (* BRN(D^.Right^.Left^.Left,22): создать T22, T25^.Left:=T22 *) (* MDF(D^.Right^.Left^.Left) : T22^.Depth:=1 *) (* MDF(D^.Right^.Left) : T25^.Depth:=2 *) (* MDF(D^.Right) : T30^.Depth:=3 *) (* MDF(D) : RL(D) *) (* Окончательно. Результат вычисления X:=FormAVL(D,22): *) (* -1- D указывает на AVL-дерево (T25 (T20 T10 T22) (T30 nil T40)) *) (* -2- X = T22 (X указывает на вершину с ключом 22) Конец примера. *) |