Описание программы работы со сбалансированными деревьями.

ОПИСАНИЕ ПРОГРАММЫ РАБОТЫ СО СБАЛАНСИРОВАННЫМИ ДЕРЕВЬЯМИ.

1. Процедура NOTE.

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

2. Процедура CREATE.

Создает новый узел дерева,в том числе и корень; записывает ключ дерева и обнуляет указатели узла на его ветви. Включает счетчик узлов и определяет корень дерева,путем установки на него указателя ROOT. Указатель ROOT устанавливается только в случае,если счетчик узлов дерева равен 0.

3. Процедура SEARCH.

Входным элементом для процедуры SEARCH является определяемый пользователем ключ для поиска или создания нового узла. Новый ключ сравнивается с ключом предыдущего узла.Если узла с таким ключом нет в дереве,то вызывается процедура CREATE.

В зависимости от того, больше или меньше ключ нового узла ключа узла предыдущего выбирается вид включения нового узла в дерево - справа или слева. На каждом этапе работы процедуры проверяется флаг "h" определяющий,увеличилась ли высота поддерева; а также проверяется поле "p^.bal" определяющее способ балансировки.

Процедура SEARCH является рекурсивной процедурой,т.е. она вызывает сама себя.При первом проходе процедура SEARCH обращается к корню дерева,затем проходит по всему дереву,последовательно вызывая ветви корня,затем ветви ветвей и так далее.

В случае,если необходима балансировка,процедура SEARCH производит так называемые "повороты" ветвей дерева,путем переопределения указателей.Если балансировка затрагивает корень дерева, процедура переопределяет корень,меняя указатель ROOT,а затем производит балансировку.

4. Процедура DELETE.

Процедура DELETE удаляет ключ из дерева и,если необходимо,производит балансировку.Входным параметром является определяемый пользователем ключ. Процедура DELETE имеет три одпроцедуры: balance_R,balance_L и Del.Подпроцедуры balance_R и balance_L являются симметричными и выполняют балансировку при уменьшении высоты правого или левого поддеревьев соответственно.

Если узла с заданным пользователем ключом нет в дереве,то выводится соответствующее сообщение.Если данный ключ меньше ключа предыдущего узла,то происходит рекурсивный вызов процедуры Delete и обход дерева по левой ветви.Если возникает необходимость балансировки,то вызывается подпроцедура balance_L.Если заданный пользователем ключ больше ключа предыдущего узла,то производится обход дерева по правой ветви и в случае необходимости балансировки вызывается подпроцедура balance_R.

Если подпроцедуры балансировки затрагивают корень дерева,то меняется указатель на корень дерева - ROOT.Эта операция заложена в обоих подпроцедурах balance_R и balance_L.

При обнаружении узла с заданным пользователем ключом подпроцедура Del производит операцию удаления данного узла.

5. Процедура OUTTREE.

Рекурсивная процедура OutTree выводит изображение дерева на монитор. Входными параметрами является указатель на корень дерева ROOT и переменная F определяющая,является ли текущий узел корнем или правой или левой ветвью.

После каждой операции над деревом процедура OutTree выводит изображение дерева заново,предварительно очистив экран.

6. Основная программа.

Программа Maveric работает в текстовом режиме,для чего в начале инициализируется модуль CRT. Основная программа выводит заставку и ожидает нажатия одной из определенных в программе клавиш. При помощи процедуры Note внизу экрана выводится подсказка со списком определенных клавиш и соответствующих им операций.При нажатии клавиши B вызывается процедура Create,при нажатии клавиши S вызывается процедура Search,при нажатии D - процедура Delete.Программа работает в диалоговом режиме.

Режим работы с пользователем прекращается при нажатии клавиши ESC.

{======Программный пример 6.22 ====== } {$T-} Program Maveric; USES CRT; label L1,L2,L3,L4; TYPE ref=^node; { указатель на узел } node=record key:integer; { ключ узла } left,right:ref; { указатели на ветви } bal:-1..+1; { флаг сбалансированности } end; VAR root, { указатель на корень дерева } p:ref; { новое дерево } x:integer; { ключ узла } h:boolean; { true-высота поддерева увеличилась } n:char; { клавиша подсказки } Ta,Tb, { координаты начала вывода дерева } a,b:integer; { координаты вывода подсказки } count:byte; { счетчик узлов дерева } Procedure Note; { процедура вывода подсказки } Begin TextBackground (white); GotoXY(5,25); textcolor(black); write('B-новое дерево S-поиск по ключу '); write (' D-удаление по ключу Esc-выход'); End; Procedure Create (x:integer; var p:ref; var h:boolean); { создание нового дерева } Begin NEW(p); h:=true; with p^ do begin key:=x; left:=nil; right:=nil; bal:=0; end; if count=0 then root:=p; count:=count+1; End; Procedure Search(x:integer; var p,root:ref; var h:boolean); var p1,p2:ref; {h=false} Begin if p=nil then Create(x,p,h) {слова нет в дереве,включить его} else if x < p^.key then begin Search(x,p^.left,root,h); if h then {выросла левая ветвь} case p^.bal of 1: begin p^.bal:=0; h:=false; end; 0: p^.bal:=-1; -1: begin {балансировка} if p=root then root:=p^.left; {смена указателя на вершину} p1:=p^.left; if p1^.bal=-1 then begin {однократный LL-поворот} p^.left:=p1^.right; p1^.right:=p; p^.bal:=0; p:=p1; end else begin {2-х кратный LR-поворот} if p1=root then root:=p1^.right; p2:=p1^.right; p1^.right:=p2^.left; p2^.left:=p1; p^.left:=p2^.right; p2^.right:=p; if p2^.bal=-1 then p^.bal:=+1 else p^.bal:=0; if p2^.bal=+1 then p1^.bal:=-1 else p1^.bal:=0; p:=p2; end; p^.bal:=0; h:=false; end; end; end else if x > p^.key then begin Search(x,p^.right,root,h); if h then {выросла правая ветвь} case p^.bal of -1: begin p^.bal:=0; h:=false; end; 0: p^.bal:=+1; 1: begin {балансировка} if p=root then root:=p^.right; {смена указателя на вершину} p1:=p^.right; if p1^.bal=+1 then begin {однократный RR-поворот} p^.right:=p1^.left; p1^.left:=p; p^.bal:=0; p:=p1; end else begin {2-х кратный RL-поворот} if p1=root then root:=p1^.left; p2:=p1^.left; p1^.left:=p2^.right; p2^.right:=p1; p^.right:=p2^.left; p2^.left:=p; if p2^.bal=+1 then p^.bal:=-1 else p^.bal:=0; if p2^.bal=-1 then p1^.bal:=+1 else p1^.bal:=0; p:=p2; end; p^.bal:=0; h:=false; end; end; end; End {Search}; Procedure Delete (x:integer; var p,root:ref; var h:boolean); var q:ref; {h:false} procedure balance_L ( var p:ref; var h:boolean); {уменьшается высота левого поддерева} var p1,p2:ref; b1,b2:-1..+1; begin {h-true,левая ветвь стала короче} case p^.bal of -1: p^.bal:=0; 0: begin p^.bal:=+1; h:=false; end; 1: begin {балансировка} p1:=p^.right; b1:=p1^.bal; if b1 >= 0 then begin {однократный RR-поворот} if p=root then root:=p^.left; p^.right:=p1^.left; p1^.left:=p; if b1 = 0 then begin p^.bal:=+1; p1^.bal:=-1; h:=false; end else begin p^.bal:=0; p1^.bal:=0; end; p:=p1; end else begin {2-х кратный RL-поворот} if p1=root then root:=p1^.left; p2:=p1^.left; b2:=p2^.bal; p1^.left:=p2^.right; p2^.right:=p1; p^.right:=p2^.left; p2^.left:=p; if b2=+1 then p^.bal:=-1 else p^.bal:=0; if b2=-1 then p1^.bal:=+1 else p1^.bal:=0; p:=p2; p2^.bal:=0; end; end; end; end; {balance_L} procedure balance_R (var p:ref; var h:boolean); {уменьшается высота правого поддерева} var p1,p2:ref; b1,b2:-1..+1; begin {h-true,правая ветвь стала короче} case p^.bal of 1: p^.bal:=0; 0: begin p^.bal:=-1; h:=false; end; -1: begin {балансировка} p1:=p^.left; b1:=p1^.bal; if b1 nil then begin Del(r^.right,h); if h then balance_R(r,h); end else begin q^.key:=r^.key; r:=r^.left; h:=true; end; end;{Del} Begin {Delete} if p=nil then begin TextColor(white); GotoXY(a,b+2); write ('Ключа в дереве нет'); h:=false; end else if x < p^.key then begin Delete(x,p^.left,root,h); if h then balance_L(p,h); end else if x > p^.key then begin Delete(x,p^.right,root,h); if h then balance_R(p,h); end else begin {удаление p^} q:=p; if q^.right=nil then begin p:=q^.left; h:=true; end else if q^.left=nil then begin p:=q^.right; h:=true; end else begin Del(q^.left,h); if h then balance_L(p,h); end; {dispose(q);} GotoXY(a,b); writeln('Узел с ключом ',x,' удален из дерева.'); end; End{Delete}; Procedure OutTree(pr:ref;f:byte); Begin Tb:=Tb+2; If f=1 then Ta:=Ta-2; if f=2 then Ta:=Ta+8; if pr<>nil then begin GotoXY(TA,TB); case f of 0: Writeln('[',pr^.key,']'); 1: Writeln('[',pr^.key,']/'); 2: Writeln('\[',pr^.key,']'); end; OutTree(pr^.left,1); OutTree(pr^.right,2); end; Tb:=Tb-2; Ta:=Ta-2; End; {OutTree} BEGIN {main program} L4: count:=0; a:=25; b:=5; TextBackground(black); ClrScr; TextBackground (red); gotoxy(a,b); textcolor(white); writeln(' WELCOME TO THE LAND '); gotoxy(a,b+1); WRITE(' OF BALANCED TREES '); while n <> #27 do begin note; n:=readkey; case n of #66: goto L1; {'B'} #68: goto L3; {'D'} #83: goto L2; {'S'} #98: begin {'b'} L1: clrscr; TextBackground (green); gotoxy(a,b); writeln ('Введите ключ для нового дерева'); gotoxy(a+32,b); read(x); Create(x,p,h); end; #115: begin {'s'} L2: ClrScr; TextBackground (blue); gotoxy(a,b); TextColor(white); writeln('Введите ключ для поиска и включения'); gotoxy(a+40,b); read(x); Search(x,p,root,h); Ta:=26; Tb:=10; OutTree(root,0); end; #100: begin {'d'} L3: ClrScr; TextBackground (yellow); gotoxy(a,b); TextColor(black); writeln('Введите ключ для удаления узла'); gotoxy(a+32,b); read(x); Delete(x,p,root,h); Ta:=26; Tb:=10; OutTree(root,0); end; end; end; Dispose(p); ClrScr; TextBackground (red); GotoXY(a,b); TextColor(white); writeln('Are you sure? Yes/No'); GotoXY (a+23,b); n:=readkey; if (n=#78) or (n=#110) then goto L4; END. {main program}