ПРИНЦИП РАБОТЫ АЛГОРИТМА.

Рассмотрим бинарное дерево представленное на рис. 6.28 (а), которое состоит только из двух узлов. Включение ключа 7 дает вначале несбалансированное дерево (т.е. линейный список). Его балансировка требует однократного правого (RR) поворота, давая в результате идеально сбалансированное дерево (b). Последующее включение узлов 2 и 1 дает несбалансированное поддерево с корнем 4. Это поддерево балансируется однократным левым (LL) поворотом (d). Далее включение ключа 3 сразу нарушает критерий сбалансированности в корневом узле 5.

Сбалансированность теперь восстанавливается с помощью более сложного двукратного поворота налево и направо (LR); результатом является дерево (e). Теперь при следующем включении потерять сбалансированность может лишь узел 5. Действительно, включение узла 6 должно привести к четвертому виду балансировки: двукратному повороту направо и налево (RL). Окончательное дерево показано на рис.6.35 (а-f).

Рис. 6.35 Последовательное включение узлов в сбалансированное дерево.

АЛГОРИТМ Insert_&_Balanse включения узла в сбалансированное дерево.

Дано: сбалансированное бинарное дерево с корнем ROOT.

Поля: LPTR, RPTR, KEY (ключ), BAL (показатель сбалансированности), DATA (информация).

Заданы переменные: ключ - х, информация - INF.

Алгоритм вставляет в дерево новый элемент, сохраняя сбалансированность дерева. Если элемент уже присутствует в дереве, то выводится соответствующее сообщение.

Переменная h используется как флаг, указывающий на то, что было произведено включение элемента. P - текущий указатель при перемещении по дереву, p1 и p2 - вспомогательные указатели. Count - счетчик вставленных элементов.

_Начало . Insert_&_Balanse:

1. Поиск места для вставки:

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

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

_то .: ВСТАВИТЬ_ЭЛЕМЕНТ и перейти к п. 3;

_иначе .: p=LPTR(p) и перейти к п. 1;

повторный вызов Insert_&_Balanse;

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

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

_то .: ВСТАВИТЬ_ЭЛЕМЕНТ и перейти к п. 5;

_иначе .: p=RPTR(p) и перейти к п. 1;

повторный вызов Insert_&_Balanse;

2. Совпадение:

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

3. Изменение показателей сбалансированности:

(производилась вставка в левое поддерево)

_если . BAL(p)=1 _то .:

BAL(p)=0; h=false; { перевеш.-> сбалансир.}

перейти к п. 7

_если . BAL(p)=0 _то .

BAL(p)=-1; { перевеш.-> критическ.}

перейти к п. 7

4. Балансировка при возрастании левого поддерева:

_если . p=ROOT _то . ROOT=LPTR(p);

{ перенос корневой вершины }

p1=LPTR(); { вводим дополнительный указатель }

_если . BAL(p1)=-1

_то .:

{ однокр. LL-поворот }

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

BAL(p)=0; p=p1;

перейти к п. 7

_иначе .:

{ двукратн. LR-поворот }

_если . p1=ROOT

_то . ROOT=RPTR(p1); { перенос корневой вершины }

p2:=RPTR(p1); RPTR(p1)=LPTR(p2);

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

RPTR(p2)=p;

(изменение показателей сбалансированности )

_если . BAL(p2)=-1 _то . BAL(p)=1 _иначе . BAL(p)=0;

_если . BAL(p2)=1 _то . BAL(p1)=-1 _иначе . BAL(p1)=0;

p=p2;

BAL(p)=0; h=false;

перейти к п. 7;

5. Изменение показателей сбалансированности:

(производилась вставка в правое поддерево)

_если . BAL(p)=-1 _то .:

BAL(p)=0; h=false; { перевеш.-> сбалансир.}

перейти к п. 7

_если . BAL(p)=0 _то

BAL(p)=1; { перевеш.-> критическ.}

перейти к п. 7

6. Балансировка при возрастании правого поддерева:

_если . p=ROOT _то . ROOT=RPTR(p); { перенос корневой вершины }

p1=RPTR(p); { вводим дополнительный указатель }

_если . BAL(p1)=1

_то .:

{ однокр. RR-поворот }

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

BAL(p)=0; p=p1;

перейти к п. 7

_иначе .:

{ двукратн. LR-поворот }

_если . p1=ROOT

_то . ROOT=LPTR(p1); { перенос корневой вершины }

p2:=LPTR(p1); LPTR(p1)=RPTR(p2);

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

LPTR(p2)=p;

(изменение показателей сбалансированности )

_если . BAL(p2)=1 _то . BAL(p)=-1 _иначе . BAL(p)=0;

_если . BAL(p2)=-1 _то . BAL(p1)=1 _иначе . BAL(p1)=0;

p=p2;

BAL(p)=0; h=false;

7. Выход.

(Т.к. процедура осуществляет рекурсивный вызов самой

себя в п.3, то здесь производится возврат в место

предыдущего вызова. Последний выход осуществляется

в вызывающую программу).

_Конец . Insert_&_Balanse.

8. Алгоритм процедуры ВСТАВИТЬ_ЭЛЕМЕНТ:

_Начало .:

LPTR(p)=nil; RPT(p)=nil; BAL=0; { обнуление указателей }

DATA=INF; KEY=x; { занесение информации }

h=true; { установка флага вставки элемента }

_если . count=0 { это первый элемент ? }

_то . ROOT=p;

count=count+1;

_Конец ..

Описание работы:

· П.1 - осуществляется поиск места для вставки элемента. Производится последовательный рекурсивный вызов процедурой самой себя. При нахождении места для вставки к дереву добавляется новый элемент с помощью процедуры ВСТАВИТЬ_ЭЛЕМЕНТ.

· П.2 - Если такой элемент уже существует в дереве, то выводится сообщение об этом и выполнение процедуры завершается.

· П.3 (П.5) - производит изменение показателей сбалансированности после включения нового элемента в левое (правое для П.5) поддерево.

· П.4 (П.6) - производит балансировку дерева путем перестановки указателей - т.е. LL- и LR-повороты (RR- и RL-повороты в П.6)

· П.7 - с помощью рекурсивных вызовов в стеке запоминается весь путь до места создания новой вершины. В П.7 производится обратный обход дерева, корректировка всех изменившихся показателей сбалансированности (в П. 3 и 5) и при необходимости балансировка. Это позволяет производить правильную балансировку, даже если критическая вершина находится далеко то места вставки.

ТЕКСТ ПРОЦЕДУРЫ Insert_&_Balanse.

Процедура выполняет действия по вставка элемента в бинарное дерево с последующей балансировкой в соответствии с приведенным выше алгоритмом.

{=====Программный пример 6.18=========}

Procedure Insert_&_Balanse (x:integer; var p,root:ref;

var h:boolean);

{ x=KEY, p=p, root=ROOT, h=h }

var p1,p2:ref; {h=false}

Begin

if p=nil

then Create(x,p,h) {слова нет в дереве,включить его}

else if x=p^.key then

begin gotoXY(35,3); write('Ключ найден!');

readln; exit; end;

if x < p^.key then

begin Insert_&_Balanse(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;{case}

end { h then}

else if x > p^.key then begin

Insert_&_Balanse(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; { begin 3 }

end;{ case }

end; {then }

End {Search};