Алгоритм процедуры balance_r.

АЛГОРИТМ ПРОЦЕДУРЫ Balance_R.

Дано: бинарное дерево, в левом поддереве которого было произведено удаление элемента.

Алгоритм, входные данные и вспомогательные переменные аналогичны алгоритму Balance_L, изменены на противоположные только условия выбора и направления указателей.

_Начало . Balance_R: 1. Корректировка показателей сбалансированности: _Если . BAL(p)=1 _то .: BAL(p)=0; { перевеш. -> сбалансированная. } _конец _Если . BAL(p)=0 _то .: BAL(p)=-1; h=false; { сбалансир. -> перевешивающая. } _конец p1=LPTR(p); b1=BAL(p1); { BAL(p)=1 - критическая. } 2. Однократный LL-поворот : _если . b1 0 _если . p1=ROOT _то . ROOT=LPTR(p); { перенос корня } p2=RPTR(p1); b2=BAL(p2); RPTR(p1)=LPTR(p2); LPTR(p2)=p1; LPTR(p)=RPTR(p2); RPTR(p2)=p; { корректировка показателей сбалансированности } _если . b2=-1 _то . BAL(p)=1 _иначе . BAL(p)=0; _если . b2=1 _то . BAL(p1)=-1 _иначе . BAL(p1)=0; p=p2; BAL(p2)=0; _конец _Конец . Balance_R;

Метод работы аналогичен алгоритму Balance_L.

ТЕКСТЫ ПРОЦЕДУР Delete 1, 0 Del 1, 0Balance_L и Balance_R.

Так как процедуры Del, Balance_L и Balance_R используются только процедурой Delete, то их можно выполнить вложенными в Delete.

{=====Программный пример 6.20 ========} 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^.right; 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^.right; 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; { begin 3 } end; { case } 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(а,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; GotoXY(а,b); writeln(' Узел с ключом ',x,' удален из дерева.'); end; End{Delete};