42Поиск записи в дереве

Рассмотрим реализацию поиска записи в двоичном дереве на примере.

Пример 7.23.

Логическая функция, отыскивающая вершину дерева с заданным ключом.

Формальные параметры: К - заданный ключ, D - ссылка на корень дерева, вкотором ведется поиск, Rez- переменная, которой присваивается ссылка на

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

поиска (закончилась ветвь).

Function Poisk (K: Integer; Var D, Rez: Adrzv): Boolean;

Var

P, Q: Adrzv;

B: Boolean;

Begin

B := False; P := D;

Q := Nil;

If D <> Nil Then Repeat

Q := P;

If P^.Kl = K If P^.Kl = K

B := True Else

If K < P^.Kl Then P := P^.Lev

Else

P := P^.Prav Until B Or (P = Nil);

Poisk := B;

Rez := Q;

End;

Включение записи в дерево

Для включения записи в дерево нужно найти в нем вершину, к которой

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

Алгоритм поиска нужной вершины аналогичен алгоритму поиска вершины с заданным ключом (см. пример 7.23). Нужная вершина найдена, если в качестве

очередной ссылки, определяющей ветвь продолжения поиска, окажется ссылка Nil.

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

заданным ключом, реализованным в примере 7.23. Такая вершина найдена, если В = False. В этом случае в Rez находится адрес вершины, к которой можно подсоединить включаемую вершину.

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

Пусть имеется объявление по примеру 7.22.

Пример 7.24.

Процедура включения записи в дерево. Параметры процедуры: К - ключ,

D - адрес корня дерева, Zap - текст вставляемой записи.

Procedure Vkl (K: Integer; Var D: Adrzv; Zap: Tekst);

Var Q, S: Adrzv; T: Adrt;

Begin

If Not Poisk (K, D, Q) Then

Begin

New (T); T^ := Zap; New (S);

S^.Kl := K; S^.Adr := T;

S^.Lev := Nil;

S^.Prav := Nil;

If D = Nil Then D := S

Else

If K < Q^.Kl

Then

Q^.Lev := S Else

Q^.Prav := S

End

End;

43. Удаление записи из дерева

Если соответствующая вершина является конечной (“лист” дерева) или из

нее выходит только одна ветвь, то для удаления записи достаточно

скорректировать соответствующую ссылку у вершины-предшественника

(рисунок 7.25).

Рисунок 7.25 – Удаление записи из дерева:

а) из удаляемой записи выходит одна ветвь;

б) удаляемая запись является «листом» дерева

В этих случаях в соответствующее поле Lev или Prav вершины-

предшественника нужно занести содержимое поля Lev или Prav удаляемой

вершины (если удаляемая вершина является “листом”, то это будет ссылка Nil).

Если из удаляемой вершины выходит две ветви, то нужно найти

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

удаляемого. Таким звеном является:

а) Самый правый элемент левого поддерева.

Данный элемент является самым большим в левом от удаляемой вершины

поддереве.

Для достижения этого звена необходимо перейти в следующую от

удаляемой вершину по левой ветви, а затем переходить в очередные вершины

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

равна Nil.

Пример 7.25.

Исключение из дерева, созданного в примере 7.21, звена с ключом 50 (см.

рисунок 7.21), используя для замещения самый правый элемент левого

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

7.26.

Рисунок 7.26 – Результат исключения звена

с ключом 50 (вариант 1)

б) самый левый элемент правого поддерева.

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

вершины поддереве.

Для достижения этого звена необходимо перейти в следующую от

удаляемой вершину по правой ветви, а затем переходить в очередные вершины

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

Nil.

Пример 7.26.

Исключение из дерева, созданного в примере 7.21, звена с ключом 50 (см.

рисунок 7.21), используя для замещения самый левый элемент правого

поддерева. Результат исключения представляет рисунок 7.27.

Рисунок 7.27 – Результат исключения звена

с ключом 50 (вариант 2)

Таким образом, при исключении из двоичного дерева вершины с

заданным ключом необходимо учесть три случая удаления:

1) звена с заданным ключом в дереве нет;

2) звено с заданным ключом имеет не более одной ветви;

3) звено с заданным ключом имеет две ветви.