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

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

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

Пример 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; {В Q будет храниться адрес

обработанной вершины}

If P^.Kl = K Then

B := True {Найдена нужная вершина}

Else

If K < P^.Kl Then

P := P^.Lev

Else

P := P^.Prav

Until B Or (P = Nil); {Поиск, пока не найден ключ (В=True)

или пока не закончилась

соответствующая ветвь}

Poisk := B; {Возвращаемое значение}

Rez := Q; {В Q – адрес звена с нужным ключом

или адрес конца ветви}

End;

Скорость поиска в двоичном дереве примерно равна скорости дихотомического поиска (см. пример 7.20).

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

Для включения записи в дерево нужно найти в нем вершину, к которой можно присоединить новую вершину, соответствующую включаемой записи. Алгоритм поиска нужной вершины аналогичен алгоритму поиска вершины с заданным ключом (см. пример 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; {Занесен ключ в поле Kl новой вершины}

S^.Adr := T; {Занесен адрес текста записи в поле Adr новой

вершины}

S^.Lev := Nil;

S^.Prav := Nil; {Созданная вершина сделана “листом” дерева}

If D = Nil Then

D := S {Если дерево еще пусто (создается), то

созданное звено делается корнем дерева}

Else

If K < Q^.Kl {В Q-адрес вершины, к которой

присоединяется новая вершина}

Then

Q^.Lev := S

Else

Q^.Prav := S

End

End;