Сбалансированные деревья

ОПРЕДЕЛЕНИЯ. Одной из наиболее часто встречающихся задач яв-

ляется поиск необходимых данных. Существуют различные методы, от-

личающиеся друг от друга временем поиска, сложностью алгоритмов,

размерами требуемой памяти. Обычно стремятся всячески сократить

время, затрачиваемое на поиск необходимого элемента. Одним из са-

мых быстрых методов является поиск по упорядоченному бинарному

дереву. При удачной структуре дерева время поиска элементов не

превышает в среднем log N. Но при неудачной структуре время поис-

ка может значительно возрасти, достигая N2. ( N - число элемен-

тов дерева).

Одним из методов, улучшающих время поиска в бинарном дереве

является создание сбалансированных деревьев обладающих минималь-

ным временем поиска.

Одно из определений сбалансированности было дано Адельсо-

ном-Вельским и Ландисом:

Дерево является СБАЛАНСИРОВАННЫМ тогда и только тогда, когда

для каждого узла высота его двух поддеревьев различается не более

чем на 1.

Поэтому деревья, удовлетворяющие этому условию, часто назы-

вают "АВЛ-деревьями" (по фамилиям их изобретателей).

Операции выполняемые над сбалансированным деревом: поиск,

вставка, удаление элемента.

Обратимся к задаче поддержания структуры дерева таким обра-

зом, чтобы за время, не превышающее (log N), могла быть выполнена

каждая из следующих операций:

1) вставить новый элемент;

2) удалить заданный элемент;

3) поиск заданного элемента.

С тем чтобы предупредить появление несбалансированного дере-

ва, вводится для каждого узла (вершины) дерева показатель сбалан-

сированности, который не может принимать одно из трех значений,

левое - (L), правое - (R), сбалансированное - (B), в соответствии

со следующими определениями:

левое - узел левоперевешивающий, если самый длинный путь по

ее левому поддереву на единицу больше самого длинного пути по ее

правому поддереву;

сбалансированное - узел называется сбалансированный, если

равны наиболее длинные пути по обеим ее поддеревьям;

правое - узел правоперевешивающий, если самый длинный путь

по ее правому поддереву на единицу больше самого длинного пути по

ее левому поддереву;

В сбалансированном дереве каждыйя узел должен находится в

одном из этих трех состояний. Если в дереве существует узел,

для которого это условие несправедливо, такое дерево называется

несбалансированным.

ОПЕРАЦИЯ ВСТАВКИ ВЕРШИНЫ В СБАЛАНСИРОВАННОЕ ДЕРЕВО. Предпо-

лагается, что новая вершина вставляется на уровне листьев, или

терминальных вершин (как левое или правое поддерево). При такой

вставке показатели сбалансированности могут изменится только у

тех вершин, которые лежат на пути между корнем дерева и вновь

вставляемым листом.

Алгоритм включения и балансировки полностью определяется

способом хранения информации о сбалансированности дерева. Опреде-

ление типа узла имеет вид:

TYPE ref=^node; { указатель }

node=record

key:integer; { ключ узла }

left,right:ref; { указатели на ветви }

bal:-1..+1; { флаг сбалансированности }

end;

Процесс включения узла состоит из последовательности таких

трех этапов:

1. Следовать по пути поиска, (по ключу), пока не будет най-

ден ключ или окажется,что ключа нет в дереве.

2. Включить новый узел и определить новый показатель сбалан-

сированности.

3. Пройти обратно по пути поиска и проверить показатель сба-

лансированности у каждого узла.

На каждом шаге должна передаваться информация о том, увели-

чилась ли высота поддерева (в которое произведено включение). По-

этому можно ввести в список параметров переменную h, означающую

"высота поддерева увеличилась".

Необходимые операции балансировки полностью заключаются в

обмене значениями ссылок. Фактически ссылки обмениваются значени-

ями по кругу, что приводит к однократному или двукратному "пово-

роту" двух или трех узлов.

ПРИНЦИП РАБОТЫ АЛГОРИТМА. Рассмотрим бинарное дерево предс-

тавленное на рис. 6.28 (а), которое состоит только из двух узлов.

Включение ключа 7 дает вначале несбалансированное дерево (т.е.

линейный список). Его балансировка требует однократного правого

(RR) поворота, давая в результате идеально сбалансированное дере-

во (b). Последующее включение узлов 2 и 1 дает несбалансированное

поддерево с корнем 4. Это поддерево балансируется однократным ле-

вым (LL) поворотом (d). Далее включение ключа 3 сразу нарушает

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

Сбалансированность теперь восстанавливается с помощью более

сложного двукратного поворота налево и направо (LR); результатом

является дерево (e). Теперь при следующем включении потерять сба-

лансированность может лишь узел 5. Действительно, включение узла

6 должно привести к четвертому виду балансировки: двукратному по-

вороту направо и налево (RL). Окончательное дерево показано на

рис.6.33 (а - f).

 

 

а) b) c)

4 5 5

/ /

5 4 ┌───┐ 4 7

│ 7 │ /

└───┘ ┌───┐

│ 2 │

└───┘

d) e) f)

5 4 4

/ / /

2 7 2 5 2 ┌───┐

/ / / │ 6 │

┌───┐ 4 1 ┌───┐ 7 1 3 └───┘

│ 1 │ │ 3 │ /

└───┘ └───┘ 5 7

 

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

ное дерево.

 

АЛГОРИТМ 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};

ТЕКСТ ПРОЦЕДУРЫ ДОБАВЛЕНИЯ ЭЛЕМЕНТА. Процедура создает новый

элемент, заполняет его информационные поля и обнуляет указатели.

При создании первого элемента он автоматически становится корнем

дерева.

Procedure Create (x:integer; var p:ref; var h:boolean);

{ создание нового элемента }

Begin

NEW(p); h:=true; with p^ do

begin key:=x; left:=nil; right:=nil; BAL:=0; end;

if count=0 then root:=p; count:=count+1; End;

ОПЕРАЦИЯ УДАЛЕНИЯ ИЗ СБАЛАНСИРОВАННОГО ДЕРЕВА. Удаление эле-

мента из сбалансированного дерева является еще более сложной опе-

рацией чем включение, так как может удаляться не только какой-ли-

бо из листьев, но и любой узел (в том числе и корень). Поэтому

при удалении необходимо правильно изменить структуру связей между

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

В результате удаления какого-либо узла могут возникнуть си-

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

1. Вершина была лево- или правоперевешивающей, а теперь ста-

ла сбалансированной.

2. Вершина была сбалансированной, а стала лево- или правопе-

ревешивающей.

3. Вершина была перевешивающей, а вставка новой вершины в

перевешивающее поддерево создала несбалансированное поддерево -

привело к появлению критической вершины. Необходимо провести ба-

лансировку.

В общем процесс удаления элемента состоит из следующих эта-

пов:

1. Следовать по дереву, пока не будет найден удаляемый эле-

мент.

2. Удалить найденный элемент, не разрушив структуры связей

между элементами.

3. Произвести балансировку полученного дерева и откорректи-

ровать показатели сбалансированности.

На каждом шаге должна передаваться информация о том, умень-

шилась ли высота поддерева (из которого произведено удаление).

Поэтому мы введем в список параметров переменную h, означающую

"высота поддерева уменьшилась".

Простыми случаями являются удаление терминальных узлов и уз-

лов с одним потомком. Если же узел, который надо удалить имеет

два поддерева, мы будем заменять его самым правым узлом левого

поддерева.

Для балансировки дерева после удаления используем две (сим-

метричные) операции балансировки: Balance_R используется, когда

уменьшается высота правого поддерева, а Balance_L - левого подде-

рева. Процедуры балансировки используют те же способы (LL- LR-

RL- и RR-повороты), что и в процедуре вставки элемента.

ПРИМЕР УДАЛЕНИЯ РАЗЛИЧНЫХ УЗЛОВ ИЗ СБАЛАНСИРОВАННОГО ДЕРЕВА.

Узел, который необходимо удалить, обозначен двойной рамкой.

Если задано сбалансированное дерево (рис.6.34. a), то последова-

тельное удаление узлов с ключами 4,8,6,5,2,1 и 7 дает деревья

(рис.6.34 b...h).

Удаление ключа 4 само по себе просто, т.к. он представляет

собой терминальный узел. Однако при этом появляется несбалансиро-

ванность в узле 3. Его балансировка требует однократного левого

поворота налево. Балансировка вновь становится необходимой после

удаления узла 6. На этот раз правое поддерево корня балансируется

однократным поворотом направо.

Удаление узла 2, хотя само по себе просто, так как он имеет

только одного потомка, вызывает сложный двукратный поворот напра-

во и налево.

И четвертый случай: двукратный поворот налево и направо вы-

зывается удалением узла 7, который прежде заменяется самым правым

элементом левого поддерева, т.е. узлом с ключом 3.

 

a) b)

5 5

/ /

3 8 2 ┌───┐

/ / / │ 8 │

2 ┌───┐ 7 10 1 3 └───┘

/ │ 4 │ / / /

1 └───┘8 9 11 7 10

/ /

6 9 11

c) d)

5 ┌───┐

/ │ 5 │

2 7 └───┘

/ / /

1 3┌───┐ 10 2 10

│ 6 │ / / /

└───┘ 9 11 1 3 7 11

/

e) f) q) h)

3 7 ┌───┐

/ / │ 7 │ 10

┌───┐ 10 3 10 └───┘ /

│ 2 │ / / / / 3 11

└───┘7 11 ┌───┐ 9 11 3 10

/ │ 1 │ / 9

1 9 └───┘ 9 11

 

Рис.6.34 а..h Удаление узлов из сбалансированого дерева.

 

Удаление элемента из сбалансированного дерева удобнее раз-

бить на 4 отдельных процедуры:

1. Delete - осуществляет рекурсивный поиск по дереву удаляе-

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

2. Del - осуществляет собственно удаление элемента и вызов

при необходимости процедуры балансировки.

3. Balance_L и Balance_R - производят балансировку и коррек-

цию показателей сбалансированности после удаления элемента из ле-

вого (правого) поддерева.

АЛГОРИТМ ПРОЦЕДУРЫ Delete. Дано: сбалансированное бинарное

дерево с корнем ROOT. Поля: LPTR, RPTR, KEY (ключ), BAL (показа-

тель сбалансированности), DATA (информация).

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

Алгоритм находит удаляемый элемент и вызывает процедуры уда-

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

отсутствует в дереве, выдается соответствующее сообщение.

Переменная h используется как флаг, указывающий на то, что

было произведено удаление элемента. P - текущий указатель при пе-

ремещении по дереву, q - вспомогательный указатель.

_Начало . Delete

1. Поиск удаляемого элемента

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

_то .: p=LPTR(p);

Вызов Delete;

_если . h=true _то . Вызов Balance_L;

перейти к п.5

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

_то .: p=RPTR(p);

Вызов Delete;

_если . h=true _то . вызов Balance_R;

перейти к п.5

_Если . p=nil

_то .: напечатать "Ключа в дереве нет!";

_конец .;

2. Удаление элемента : (если все предыдущие условия не вы-

полнены, то указатель указывает на элемент, подлежащий удалению).

Удаляется элемент с одним поддеревом.

q=p; { вводим вспомогательный указатель }

_если . RPTR(q)=nil

_то .: p=LPTR(q);

h=true;

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

_если . LPTR(q)=nil

_то .: p=RPTR(q);

h=true;

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

3. Удаление элемента с двумя поддеревьями:

q=LPTR(q);

_если . h=true _то .: вызов Balance_L;

перейти к п.4

4. Напечатать "Узел удален из дерева".

5. Выход.

_Конец . Delete;

 

ОПИСАНИЕ РАБОТЫ АЛГОРИТМА:

П.1 - осуществляет поиск удаляемого элемента с помощью ре-

курсивных вызовов процедуры Delete (т.е. - самой себя). При этом

в стеке сохраняется весь путь поиска. Если было произведено уда-

ление элемента, то производится вызов соответствующей процедуры

балансировки. Если элемент с заданным ключом не найден, то выво-

дится соответствующее сообщение.

П.2 - производится удаление элемента с одной ветвью простым

переносом указателя. Устанавливается флаг удаления элемента.

П.3 - производится вызов процедуры Del, производящей удале-

ние элемента с двумя поддеревьями.

П.5 - т.к. эта процедура рекурсивная, то производится возв-

рат в место предыдущего вызова, либо в главную программу.

АЛГОРИТМ ПРОЦЕДУРЫ Del. Дано: указатель - r на элемент дере-

ва с двумя поддеревьями.

Алгоритм производит удаление этого элемента, с сохранением

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

Используется вспомогательный указатель q, описанный в проце-

дуре Delete.

_Начало . Del.

1. Поиск последнего элемента в правом поддереве

_Если . RPTR(r) <> nil { элемент не найден }

_то .: r=RPTR(r);

вызов процедуры Del;

_если . h=true _то . вызов процедуры Balance_R;

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

_иначе .: KEY(q)=KEY(r); r=RPTR(r); h=true;

2. Выход.

_Конец . Del;

ОПИСАНИЕ РАБОТЫ:

П.1 - производится рекурсивный поиск самого правого элемента

в поддереве. Если элемент найден, то он ставится на место удален-

ного элемента, устанавливается флаг удаления, и осуществляется

выход. Если установлен флаг удаления элемента, то вызывается про-

цедура балансировки.

П.5 - т.к. эта процедура рекурсивная, то производится возв-

рат в место предыдущего вызова, либо в вызывающую процедуру (De-

lete).

АЛГОРИТМ ПРОЦЕДУРЫ Balance_L. Дано: бинарное дерево, в левом

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

Задан: указатель p на место удаленного элемента.

Алгоритм производит балансировку бинарного дерева и коррек-

тировку показателей сбалансированности.

P1 и P2 - вспомогательные указатели, b1 и b2 - вспомогатель-

ные показатели сбалансированности.

_Начало . Balance_L:

1. Корректировка показателей сбалансированности:

_Если . BAL(p)=-1

_то .: BAL(p)=0; { перевеш. -> сбалансир. }

_конец

_Если . BAL(p)=0

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

_конец

p1=RPTR(p); b1=BAL(p1); { BAL(p)=1 - критическая. }

2. Однократный RR-поворот :

_Если . b1 >= 0

_то .:

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

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

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

_если . b1=0

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

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

p=p1;

_конец

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

_если . b1 < 0

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

p2=LPTR(p1); b2=BAL(p2);

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

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

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

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

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

p=p2; BAL(p2)=0;

_конец

_Конец . Balance_L;

ОПИСАНИЕ РАБОТЫ АЛГОРИТМА:

П.1 - если вершина не является критической, то производится

изменение показателей сбалансированности. Если вершина критичес-

кая - создаются вспомогательные указатели.

П.2 и 3 - производят балансировку дерева однократным RR(п.2)

и двукратным RL- (п.3) поворотами и изменение показателей сбалан-

сированности.

АЛГОРИТМ ПРОЦЕДУРЫ 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, то их можно выполнить вложенными в De-

lete.

{=====Программный пример 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

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

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

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

Напечатать "Элемент найден";

Произвести операции обработки элемента и _конец ..

ТЕКСТ ПРОЦЕДУРЫ Search.

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

Procedure Search (x:integer; var p:ref);

begin

if x > p^.key then

if p=nil then writeln('Элемент на найден')

else Search(x,p^.right);

if x < p^.key then

if p=nil then writeln('Элемент на найден')

else Search(x,p^.left);

writeln('элемент найден');

{ Здесь - процедура обработки элемента }

end;

Так как операция поиска применяется в процедуре вставки эле-

мента в сбалансированное дерево, то нет особого смысла выделять

эту операцию в отдельную процедуру. Проще предусмотреть, что при

отсутствии элемента производится его включение, а если элемент

уже есть - то производятся необходимые действия над элементом.

На первый взгляд работа со сбалансированными бинарными де-

ревьями требует лишних затрат времени на дополнительные операции

по поддержанию необходимой структуры дерева и усложнение алгорит-

мов.

Но на самом деле затраты на балансировку легко компенсируют-

ся минимальным временем поиска элементов при вставке, удалении и

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

то же время четкая структура расположения элементов не усложняет,

а наоборот - упрощает алгоритмы работы с такими деревьями.

ОПИСАНИЕ ПРОГРАММЫ РАБОТЫ СО СБАЛАНСИРОВАННЫМИ ДЕРЕВЬЯМИ.

1. Процедура NOTE.

В процессе работы пользователя с программой MAVERIC выводит

подсказку в нижней части экрана. Подсказка содержит коды кла-

виш,определяющих режим работы программы.

2. Процедура CREATE.

Создает новый узел дерева,в том числе и корень; записывает

ключ дерева и обнуляет указатели узла на его ветви. Включает

счетчик узлов и определяет корень дерева,путем установки на него

указателя ROOT. Указатель ROOT устанавливается только в слу-

чае,если счетчик узлов дерева равен 0.

3. Процедура SEARCH.

Входным элементом для процедуры SEARCH является определяемый

пользователем ключ для поиска или создания нового узла. Новый

ключ сравнивается с ключом предыдущего узла.Если узла с таким

ключом нет в дереве,то вызывается процедура CREATE.

В зависимости от того, больше или меньше ключ нового узла

ключа узла предыдущего выбирается вид включения нового узла в де-

рево - справа или слева. На каждом этапе работы процедуры прове-

ряется флаг "h" определяющий,увеличилась ли высота поддерева;а

также проверяется поле "p^.bal" определяющее способ балансировки.

Процедура SEARCH является рекурсивной процедурой,т.е. она

вызывает сама себя.При первом проходе процедура SEARCH обращается

к корню дерева,затем проходит по всему дереву,последовательно вы-

зывая ветви корня,затем ветви ветвей и так далее.

В случае,если необходима балансировка,процедура SEARCH про-

изводит так называемые "повороты" ветвей дерева,путем переопреде-

ления указателей.Если балансировка затрагивает корень дерева,

процедура переопределяет корень,меняя указатель ROOT,а затем про-

изводит балансировку.

4. Процедура DELETE.

Процедура DELETE удаляет ключ из дерева и,если необходи-

мо,производит балансировку.Входным параметром является определяе-

мый пользователем ключ. Процедура DELETE имеет три подпроцедуры:

balance_R,balance_L и Del.Подпроцедуры balance_R и balance_L яв-

ляются симметричными и выполняют балансировку при уменьшении вы-

соты правого или левого поддеревьев соответственно.

Если узла с заданным пользователем ключом нет в дереве,то

выводится соответствующее сообщение.Если данный ключ меньше ключа

предыдущего узла,то происходит рекурсивный вызов процедуры Delete

и обход дерева по левой ветви.Если возникает необходимость балан-

сировки,то вызывается подпроцедура balance_L.Если заданный поль-

зователем ключ больше ключа предыдущего узла,то производится об-

ход дерева по правой ветви и в случае необходимости балансировки

вызывается подпроцедура balance_R.

Если подпроцедуры балансировки затрагивают корень дерева,то

меняется указатель на корень дерева - ROOT.Эта операция заложена

в обоих подпроцедурах balance_R и balance_L.

При обнаружении узла с заданным пользователем ключом подпро-

цедура Del производит операцию удаления данного узла.

5. Процедура OUTTREE.

Рекурсивная процедура OutTree выводит изображение дерева на

монитор. Входными параметрами является указатель на корень дерева

ROOT и переменная F определяющая,является ли текущий узел корнем

или правой или левой ветвью.

После каждой операции над деревом процедура OutTree выводит

изображение дерева заново,предварительно очистив экран.

6. Основная программа.

Программа Maveric работает в текстовом режиме,для чего в на-

чале инициализируется модуль CRT. Основная программа выводит зас-

тавку и ожидает нажатия одной из определенных в программе клавиш.

При помощи процедуры Note внизу экрана выводится подсказка со

списком определенных клавиш и соответствующих им операций.При на-

жатии клавиши B вызывается процедура Create,при нажатии клавиши S

вызывается процедура Search,при нажатии D - процедура Dele-

te.Программа работает в диалоговом режиме.

Режим работы с пользователем прекращается при нажатии клави-

ши ESC.

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

{$T-}

Program Maveric;

USES CRT;

label L1,L2,L3,L4;

TYPE ref=^node; { указатель на узел }

node=record

key:integer; { ключ узла }

left,right:ref; { указатели на ветви }

bal:-1..+1; { флаг сбалансированности }

end;

VAR

root, { указатель на корень дерева }

p:ref; { новое дерево }

x:integer; { ключ узла }

h:boolean; { true-высота поддерева увеличилась }

n:char; { клавиша подсказки }

Ta,Tb, { координаты начала вывода дерева }

a,b:integer; { координаты вывода подсказки }

count:byte; { счетчик узлов дерева }

Procedure Note; { процедура вывода подсказки }

Begin

TextBackground (white); GotoXY(5,25); textcolor(black);

write('B-новое дерево S-поиск по ключу ');

write (' D-удаление по ключу Esc-выход');

End;

Procedure Create (x:integer; var p:ref; var h:boolean);

{ создание нового дерева }

Begin

NEW(p); h:=true;

with p^ do

begin key:=x;

left:=nil; right:=nil; bal:=0;

end;

if count=0 then root:=p;

count:=count+1;

End;

Procedure Search(x:integer; var p,root:ref; var h:boolean);

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

Begin

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

else if x < p^.key then

begin Search(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;

end else if x > p^.key then

begin Search(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; end; end;

End {Search};

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^.left;

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^.left;

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; end;

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

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

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(a,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;

{dispose(q);}

GotoXY(a,b);

writeln('Узел с ключом ',x,' удален из дерева.');

end;

End{Delete};

Procedure OutTree(pr:ref;f:byte);

Begin

Tb:=Tb+2;

If f=1 then Ta:=Ta-2;

if f=2 then Ta:=Ta+8;

if pr<>nil then begin GotoXY(TA,TB);

case f of

0: Writeln('[',pr^.key,']');

1: Writeln('[',pr^.key,']/');

2: Writeln('[',pr^.key,']');

end;

OutTree(pr^.left,1); OutTree(pr^.right,2);

end;

Tb:=Tb-2; Ta:=Ta-2;

End; {OutTree}

BEGIN {main program}

L4:

count:=0; a:=25; b:=5;

TextBackground(black); ClrScr;

TextBackground (red); gotoxy(a,b);

textcolor(white); writeln(' WELCOME TO THE LAND ');

gotoxy(a,b+1); WRITE(' OF BALANCED TREES ');

while n <> #27 do

begin note; n:=readkey;

case n of

#66: goto L1; {'B'}

#68: goto L3; {'D'}

#83: goto L2; {'S'}

#98: begin {'b'}

L1: clrscr; TextBackground (green); gotoxy(a,b);

writeln ('Введите ключ для нового дерева');

gotoxy(a+32,b); read(x); Create(x,p,h);

end;

#115: begin {'s'}

L2: ClrScr;

TextBackground (blue); gotoxy(a,b);

TextColor(white);

writeln('Введите ключ для поиска и включения');

gotoxy(a+40,b); read(x);

Search(x,p,root,h); Ta:=26; Tb:=10;

OutTree(root,0); end;

#100: begin {'d'}

L3: ClrScr; TextBackground (yellow);

gotoxy(a,b); TextColor(black);

writeln('Введите ключ для удаления узла');

gotoxy(a+32,b); read(x);

Delete(x,p,root,h);

Ta:=26; Tb:=10; OutTree(root,0);

end; end; end;

Dispose(p); ClrScr; TextBackground (red);

GotoXY(a,b); TextColor(white);

writeln('Are you sure? Yes/No');

GotoXY (a+23,b); n:=readkey;

if (n=#78) or (n=#110) then goto L4;

END. {main program}