 |
Принцип работы алгоритма.
|
|
|
|
Рассмотрим бинарное дерево представленное на рис. 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};|
|
|
