Операции над деревом поиска

 

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

Вставка нового элемента осуществляется по тому же принципу, что и построение. Эта процедура напоминает поиск, т.к. для вставки нового элемента необходимо пройти по нужному маршруту.

Например, пусть в дерево надо вставить элемент 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

¦ if Z^.left^.k = X^.k then

¦ begin

¦ ¦ Z^.left:= X^.left;

¦ ¦ X^.left^.right:= X^.right;

¦ end

¦ else begin

¦ ¦ Z^.right:=X^.left;

¦ ¦ X^.left^.right:= X^.right;

¦ ¦ Z^.right:=X^.right

¦ end

¦ else begin {Удал-е внутр. вершин}

¦ ¦ P:=X^.left^.right; M:=X^.left;

¦ ¦ while P^.right <> nil do

¦ ¦ begin M:=P; P:=P^.right; end;

¦ ¦ X^.k:=P^.k;

¦ ¦ M^.right:=nil; {Отрезание листа}

¦ end;

end.

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

Все это показано в следующей программе:

program POISK_I_UDALENIE;

label 1,2,3;

type SS = ^ZVENO;

ZVENO = record

k,n: integer;

left, right: SS; end;

var DER,Z,X,T:ss; I,J:integer;

Y:real; O:char;

begin

1:clrscr; gotoxy(20,2); write('ПОИСК И УДАЛЕНИЕ');

writeln(' ДЕРЕВО ПОИСКА '); PRINTTREE(DER,3,Y);

writeln(' УДАЛЕНИЕ УКАЗАННОГО ЭЛЕМЕНТА ');

2:writeln;write('Укажите элемент для удаления: '); readln(I);

POISK(DER,I,X); if X^.k <> I then begin

{ X - ссылка на вершину I }

write('Такого элемента нет в деpеве ! '); readln;goto 2 end;

if X^.k = DER^.k then begin

writeln('ВHИМАHИЕ ! Это - коpень деpева !'); goto 2 end;

3:write('Укажите элемент, перед которым идет удаление:');

readln(J); POISK(DER,J,Z);

{ Z - ссылка на вершину J}

if Z^.k <> J then begin

write('Такого элемента нет в деpеве ! '); goto 3 end;

if (Z^.left^.k <> I) and (Z^.right^.k <> I) then

begin write('Такой паpы элементов нет в деpеве ! ');

goto 3 end; clrscr;

gotoxy(41,3); write(' ДЕРЕВО до удаления '); writeln;

PRINTTREE(der,43,y); UDALEN(Z,X);

gotoxy(3,3);write(' ДЕРЕВО после удаления ');writeln;

PRINTTREE(der,3,y); writeln;

writeln('Удален элемент',i:3,' после элемента ',j:3);writeln;

write('Еще ?(y/n): '); readln(o); if O='y' then goto 1;

end.