C.Ю.Соловьев

Методические материалы
по курсу
"Алгоритмы и алгоритмические языки"

Программа курса
Программирование в машинных кодах
Примеры-1
Примеры-2
Пример "большой" программы
Нисходящее программирование
Ссылочные типы
Структуры данных
Очереди и стеки
Деревья поиска
AVL-деревья
Таблицы
Хеш-таблицы
Динамические страницы

AVL-деревья (АВЛ-деревья)

(* 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)  Конец примера.              *)

Вопросы?