Алгоритмический язык Паскаль (стр. 27 из 31)
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
15.4 Дерево поиска
До сих пор мы рассматривали построение идеально сбалансированных деревьев с произвольным расположением элементов в вершинах. Напомним, что идеально сбалансированным называется дерево, у которого разница между числом вершин в левом и правом поддеревьях не более 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.
15.5 Операции над деревом поиска
В дереве поиска возможны те же операции, что и в дереве общего вида (поиск, вставка, удаление). Однако здесь уже поиск осуществляется быстрее (проходит по одному маршруту), процедура печати дерева совпадает с процедурой его построения.
Вставка нового элемента осуществляется по тому же принципу, что и построение. Эта процедура напоминает поиск, т.к. для вставки нового элемента необходимо пройти по нужному маршруту.
Например, пусть в дерево надо вставить элемент 4:
10
/ \
5 12
/ \ / \
3 7 11 15
1) т.к. 4 < 10, то нужно идти в левое поддерево(т.е. на 5);
2) т.к. 4 < 5, следует спуститься ниже 5;
3) т.к. 4 > 3, необходимо вставить этот элемент в правое поддерево.
ÑÕÅÌÀ ÂÑÒÀÂÊÈ
10
/ \
5 12
/ \ / \
3 7 11 15
\
4
Итак, для вставки в дерево DER элемента 4 надо записать оператор TREEPOISK(DER,4).
Заметим еще раз, что рассмотренная выше процедура TREEPOISK, используемая для формирования дерева, может быть применена и для поиска в нем данного элемента. Действительно, если на вход этой процедуры подать элемент, не содержащийся в дереве, то он будет добавлен к этому дереву. Если же элемент S входит в дерево, то его нового добавления не произойдет, а по значению поля S^.n можно узнать о вхождении данного элемента в дерево (S^.n > 1).
Например, для поиска некоторого элемента EL в дереве DER необходимо выполнить TREEPOISK(DER, EL), добавив в процедуре TREEPOISK оператор WRITELN(DER^.N), который следует поставить в начало ее тела (после слова BEGIN). Наличие в этом списке числа 2 говорит о вхождении элемента EL в дерево, причем можно даже узнать его порядковый номер.
Рассмотренные выше процедуры поиска и вставки элементов в дерево часто используются совместно. Например, с помощью этих процедур можно решать следующие комплексные задачи:
1) поместить данный элемент (не принадлежащий дереву) после указанного элемента дерева;
2) вставить определенный элемент дерева после некоторого элемента того же дерева (переместить элемент).
Следует отметить, что эти операции в дереве поиска надо проводить осторожно, чтобы не нарушить его упорядоченность.
Решение второй задачи может быть реализовано с помощью следующей программы:
program POISK_I_VSTAVKA;
label 1,2,3;
type SS = ^ZVENO;
ZVENO = record
k,n: integer;
left, right: SS;
end;
var DER1,Z,X,T:ss; I,J:integer;
Y:real; O:char;
begin
1:clrscr; gotoxy(20,2);write(' ПОИСКИВСТАВКА');
writeln; writeln(' ОБЩЕЕДЕРЕВО ');writeln;
PRINTTREE(DER1,3,Y); writeln;
writeln('ВСТАВКА HОВОГОЭЛЕМЕHТАПОСЛЕ HАЙДЕHHОГОВЛЕВО');
2:writeln;write('Укажите элемент для вставки: '); readln(I);
POISK(DER1,I,X);
if X^.k <> I then begin
write('Такого элемента нет в деpеве!'); goto 2 end;
3:write('Укажите элемент, за которым идет вставка:');read(j);
POISK(DER1,J,Z); if Z^.k <> J then begin
write('Такого элемента нет в деpеве ! ');
readln;goto 3 end; clrscr;
gotoxy(41,3); write(' ДЕРЕВО до вставки ');
PRINTTREE(DER1,3,Y);
new(T); T^.left:= nil; T^.right:= nil; T^.k:= X^.k;
VSTAVKA(Z,Z^.LEFT,T);
gotoxy(3,3);write(' ДЕРЕВО после вставки ');
PRINTTREE(DER1,3,Y); writeln;
writeln('Вставлен элемент',I:3,'влево после элемента',J:3);
write('Еще ?(y/n): '); readln(O); if O='y' then goto 1
end.
Дерево поиска есть упорядоченное дерево, поэтому для удаления его некоторого элемента необходимо применить принцип удаления, рассмотренный в 15.3.3.
Напомним, что согласно этому принципу, при удалении элемента из дерева на его место ставится любой крайний правый элемент левого поддерева, следующий за удаленным, или любой крайний левый элемент правого поддерева.
procedure UDALEN(var Z, X:ss);
{ X - удаляемый элемент, Z - предшествующий}
var P, M: SS; { Вспомогательные вершины }
begin
¦if X^.left = nil then { Удалениелевыхлистов }
¦ if Z^.left^.k = X^.k
¦ then Z^.left:= X^.right
¦ else Z^.right:= X^.right
¦ else { Удалениеправыхлистьев}
¦ if X^.left^.right = nil then