АЛГОРИТМ ПРОЦЕДУРЫ 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};

ПОИСК ЭЛЕМЕНТА.

Поиск элемента в сбалансированном дереве уже применялся в операциях вставки и удаления элементов. Поэтому необходимо отдельно рассмотреть эту операцию.

Пусть дано некоторое бинарное дерево, в котором каждый левый элемент меньше вышележащего, а правый - больше.

Для нахождения элемента с заданным ключом начинаем поиск с корневого элемента, сравнивая его ключ с искомым. Если искомый ключ меньше, то продолжаем поиск по левому поддереву (так как его элемент меньше текущего), а если ключ больше - то по правому (его элемент больше). Сравнивая аналогичным образом искомый ключ с ключом текущего элемента мы будем последовательно спускаться по дереву до тех пор, пока ключи искомого и текущего элемента не совпадут - элемент найден. Если мы дошли до уровня листьев (ниже элементов уже нет), а элемент не найден, значит он отсутствует в дереве.

Этот алгоритм пригоден для поиска в любых бинарных деревьях, но при работе со сбалансированными деревьями время поиска элемента минимально.

АЛГОРИТМ Search.

Дано: ключ - X.

Алгоритм производит рекурсивный обход сбалансированного дерева и находит элемент с заданным ключом, либо сообщает об отсутствии такого элемента.

1. Поиск элемента:

_Если . x < key(p)

_то .: _если . p=nil

_то .: напечатать "Элемент отсутствует" и _конец ..

_иначе .: p=LPTR(p) и вызвать процедуру Search;

_Если . x > key(p)

_то .: _если . p=nil

_то .: напечатать "Элемент отсутствует" и _конец ..