Алгоритм процедуры 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

_то.:

_если. p=ROOT _то. ROOT=LPTR(p); { перенос корня }

LPTR(p)=RPTR(p1); RPTR(P1)=p;

{ корректировка показателей сбалансированности }

_если. b1=0

_то.: BAL(p)=-1; BAL(p1)=1; h=false;

_иначе.: BAL(p)=0; BAL(p1)=0;

p=p1;

_конец

3. Двукратный RL-поворот:

_если. 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 <= 0 then begin { однократный LL-поворот }

if p=root then root:=p^.left;

p^.left:=p1^.right; p1^.right:=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-кратный LR-поворот }

if p1=root then root:=p1^.left;

p2:=p1^.right; b2:=p2^.BAL;

p1^.right:=p2^.left; p2^.left:=p1;

p^.left:=p2^.right; p2^.right:=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_R}

Procedure Del (var r:ref; var h:boolean);

begin { h-false }

if r^.right <> 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};