Модели и структуры данных



         

Сбалансированные деревья - часть 14


При помощи процедуры 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}

КаталогИндекс раздела

НазадОглавлениеВперед




Содержание  Назад  Вперед