Основные операции над деревьями

 

Над деревьями, как и над другими связными списками, выполняются те же операции: поиск элемента, вставка элемента в дерево и удаление из него.

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

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

1) входные параметры (параметры-значения) - ссылка на дерево (т.е. на корень дерева, где ищется элемент) и значение элемента поиска;

2) выходной параметр (параметр-переменная) - ссылка на найденный элемент.

Таким образом, имеем следующую процедуру:

procedure POISK(S: SS; ZNACH: integer; var ELEM: SS);

begin

¦ if S <> nil then

if S^.k = ZNACH then ELEM:= S

¦ else

begin

¦ ¦ POISK(S^.left, ZNACH, ELEM);

¦ ¦ POISK(S^.right, ZNACH, ELEM);

¦ end;

end.

ЗАМЕЧАНИЕ. Из самой процедуры видно, что рекурсия заканчивается по достижению последнего элемента дерева, поэтому переменная ELEM получит значение ссылки на последний элемент, равный ZNACH. Если такого элемента в дереве нет, то переменная ELEM не будет определена, т.к. на оператор ELEM:= S программа выходит только при условии S^.K = ZNACH. В этом случае значение переменной ELEM^.K - "мусор".

В качестве элемента поиска может быть и корень дерева, но тогда никакой рекурсии не произойдет, а будет сразу получен ответ. Итак, процедура POISK "пробегает" все дерево независимо от результатов. Для приостановки поиска после получения положительного результата необходимо организовать досрочный выход, что реализует следующая процедура:

procedure POISK1(S: SS; ZNACH: integer; var ELEM: SS);

begin

¦ if (S^.k >= N1) and (S^.k <= N2) then

¦ begin write(S^.k:3); i:= i+1; end;

¦ if S^.k = ZNACH then begin j:=1;ELEM:= S end

¦ else if S <> nil then

¦ begin

¦ ¦ POISK1(S^.left, ZNACH, ELEM);

¦ ¦ if j = 0 then

¦ ¦ POISK1(S^.right, ZNACH, ELEM);

¦ end;

end.

ПОЯСНЕНИЕ. Данная процедура заканчивает работу либо при нахождении искомого элемента, либо при достижении конца дерева. В ней имеются две глобальные переменные I и J, которые должны быть обнулены в основной программе. Переменная I служит для подсчета просмотренных во время поиска элементов, которые попутно выводятся на печать. При нахождении элемента ZNACH в левом поддереве вырабатывается признак J = 1, препятствующий вхождению поиска в правое поддерево.

Условие (S^.k >= N1) and (S^.k <= N2) необходимо для того, чтобы не выводились на печать K - элементы "сухих" ветвей (выходящих из терминальных вершин) при обходе дерева. Здесь N1 - наименьший и N2 - наибольший из введенных в дерево элементов. Обе эти переменные должны быть определены в основной программе.

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

Если поставить вопрос о вставке нового элемента перед указанным, то, казалось бы, ситуация выглядит проще. Но это на самом деле не так. Ведь при вставке элемента перед указанным также следует держать ссылку на предыдущее звено. Поэтому задача имеет тот же вариант, что и раньше:

 

			предыдущее звено;
			новое звено;
			фиксированное звено;

 

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

Чтобы избежать этой неопределенности, условились делать процедуру вставки по следующему алгоритму:

1) вставлять новый элемент S2 между S и S1;

2) если S ссылается на S1 левым полем, то вставляемый элемент S2 будет также ссылаться на S1 левым полем;

3) если S ссылается на S1 правым полем, то и вставляемый элемент должен ссылаться на S1 правым полем.

 

а). Левое

б). Правое

S

S

…

…

S2

S2

nil

nil

S1

S1

…

…

 

Отсюда следует процедура вставки (нерекурсивная):

procedure VSTAVKA (S, S1, S2: SS);

begin

¦ if S^.left = S1 then

¦ begin

¦ ¦ S^.left:= S2;

¦ ¦ S2^.left:= S1;

¦ ¦ S2^.right:= nil;

¦ end

¦ else

¦ begin

¦ ¦ S^.right:= S2;

¦ ¦ S2^.right:= S1;

¦ ¦ S2^.left:= nil;

¦ end;

end.

ЗАМЕЧАНИЕ. В отличие от процедуры POISK здесь нет на входе явного указания на корень дерева. Однако при указании двух соседних вершин в ссылках на них фигурирует ссылка на корень дерева. Например, для вставки в дерево DER некоего элемента EL между вторым и третьим элементами левого поддерева необходимо выполнить следующие операторы:

new(Z); write ('Введите вставляемый элемент: ');

readln(EL); Z^.k:= EL: Z^.left:= nil; Z^.right:= nil;

VSTAVKA (DER^.left, DER^.left^.left, Z).

На практике ссылка S чаще всего есть результат работы процедуры поиска, т.е. получена путем применения POISK(DER,ZNACH,S). Тогда для вставки элемента Z в левое поддерево вершины S в качестве S1 надо взять S^.left, в противном случае – положить S1=S^.right.

Удаление звена из дерева осуществляется по разным правилам и зависит от характеристики дерева и предметной области его вершин. Здесь возможны различные варианты.

Если вершина Si является терминальной (листом) или из нее выходит только одна ветвь, то удаление реализуется довольно просто - для этого надо скорректировать соответствующую ссылку у вершины предшественника:

 

а).

…

б).

…

Si-1

Si-1

Si

Si

Si-1

NIL

Si-1

®

Si+1

Si-1

®

NIL

Некоторые деревья по своей семантике допускают удаление вершины вместе с выходящими из нее поддеревьями. В этом случае ссылке вершины - предшественницы присваивается значение NIL.

Однако для большинства деревьев удаление одной из вершин не должно приводить к потере остальных. Чтобы избежать этого, надо найти в дереве звено, которое можно вставить на место удаленного, причем подходящее звено должно быть листом. Такое звено всегда существует - это либо самый правый элемент левого поддерева, либо самый левый элемент правого.

Для первого случая надо перейти в следующее звено по левой ветви, а потом все время идти по правой, пока не найдется NIL.

Для второго - надо перейти в следующее звено по правой ветви, а потом идти все время по левой до NIL.

ПРИМЕР. Пусть требуется удалить в дереве вершину 50.

Для решения этой задачи переходим в правое поддерево на вершину 55 и затем идем все время по левым ветвям к вершине 33, которую ставим на место 50.

Заметим, что такой способ удаления звена с замещением его на другое не нарушает упорядоченности (в смысле отношения порядка в множестве целых чисел). Особенно это важно для дерева поиска, в котором и будет рассмотрена процедура удаления звена.

100 | 100

/ \ | / \

20 120 | 20 120

/ \ \ | / \ \

15 50 130 | 15 33 130

/ \ | / \

30 55 | 30 55

/ / \ | / / \

28 35 60 | 28 35 60

/ \ |

33 50 |

Вид дерева |

ДО удаления | Вид дерева ПОСЛЕ удаления 50

 

Дерево поиска

 

До сих пор мы рассматривали построение идеально сбалансированных деревьев с произвольным расположением элементов в вершинах. Напомним, что идеально сбалансированным называется дерево, у которого разница между числом вершин в левом и правом поддеревьях не более 1:

a) A б) A

/ \ / \

B C C B

/ / \

D D E

Сбалансированное Несбалансированное

Организация ИДЕАЛЬНО СБАЛАНСИРОВАННЫХ деревьев не всегда оправдана, т.к. деревья часто строят для поиска того или иного элемента в структуре данных. В дереве общего вида для поиска одного элемента иногда приходится перебрать и все другие, если этот элемент является листом. Такой путь нерационален, т.к. теряется сама идея построения дерева. Лучше создать линейный список в виде стека, дека или очереди. Вот почему для упрощения поиска при организации дерева его строят в виде ДЕРЕВА ПОИСКА, т.к. число переборов для нахождения нужного элемента здесь значительно меньше.

Принцип построения такого дерева состоит в следующем: новый элемент добавляется в левое поддерево, если его значение меньше данного, и в правое, если оно больше данного; элемент не входит в дерево, если он равен данному элементу.

Например, пусть заданы элементы: 10,5,7,12,15,3,7,9. Расположить их в виде дерева поиска с корнем 10.

10

/ \

5 12

/ \ \

3 7 15

\

9

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

Рассмотрим теперь процедуру формирования дерева поиска с учетом принципа его построения:

procedure TREEPOISK(var S: SS; ZNACH: integer);

begin

¦ if S = nil then begin

¦ ¦ new(S); S^.k:= ZNACH;

¦ ¦ S^.left:= nil;

¦ ¦ S^.right:= nil; S^.n:= 1;

¦ end

¦ else

¦ if ZNACH < S^.k then TREEPOISK(S^.left,ZNACH)

¦ else

¦ if ZNACH > S^.k then TREEPOISK(S^.right,ZNACH)

¦ else S^.n:= S^.n + 1;

end.

ЗАМЕЧАНИЕ. Из этой процедуры видно, что звено дерева поиска уже состоит из четырех полей: К, LEFT, RIGHT и N. Целочисленное поле N добавлено для того, чтобы увеличивать его значение при появлении в дереве нескольких одинаковых элементов. Поле S^.n позволяет узнать для каждой вершины число породивших ее элементов (кратность вершины). Дело в том, что в отличие от сбалансированного дерева, в дерево поиска элемент входит только один раз. Например, если подавать на вход процедуры TREEPOISK элементы 7,5,3,2,8,4,3,1,7,9, то сформируется дерево из вершин 7,5,3,2,8,4,1,9, а в 4-м поле звена 7 (в нашем случае корень дерева) будет находиться 2.

Заметим также, что указанная процедура построения дерева поиска добавляет лишь один элемент к дереву. Для организации же всего дерева (от корня до его листьев) надо предусмотреть программу, в которой идет обращение к этой процедуре. Основная часть этой программы может выглядеть так:

var DER: SS; EL: integer;

begin write('Введите элемент: '); readln(EL);

¦ DER:=nil;

¦ while EL <> 0 do begin TREEPOISK(DER, EL);

¦ readln(EL); end;

end.