предыдущее звено;
новое звено;
фиксированное звено;
Кроме того, необходимо знать, с какого из полей (левого или правого) вставляемого элемента надо делать ссылку на оставшуюся часть дерева, а какое поле оставить незаполненным, т.е. сделать его терминальным (листом).
Чтобы избежать этой неопределенности, условились делать процедуру вставки по следующему алгоритму:
1) вставлять новый элемент S2 между S и S1;
2) если S ссылается на S1 левым полем, то вставляемый элемент S2 будет также ссылаться на S1 левым полем;
3) если S ссылается на S1 правым полем, то и вставляемый элемент должен ссылаться на S1 правым полем.
а). Левое
б). Правое
S
…
S2
nil
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
¦ ¦ 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
NIL
Si+1
Некоторые деревья по своей семантике допускают удаление вершины вместе с выходящими из нее поддеревьями. В этом случае ссылке вершины - предшественницы присваивается значение 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
Сбалансированное Несбалансированное
Организация ИДЕАЛЬНО СБАЛАНСИРОВАННЫХ деревьев не всегда оправдана, т.к. деревья часто строят для поиска того или иного элемента в структуре данных. В дереве общего вида для поиска одного элемента иногда приходится перебрать и все другие, если этот элемент является листом. Такой путь нерационален, т.к. теряется сама идея построения дерева. Лучше создать линейный список в виде стека, дека или очереди. Вот почему для упрощения поиска при организации дерева его строят в виде ДЕРЕВА ПОИСКА, т.к. число переборов для нахождения нужного элемента здесь значительно меньше.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39
