Занимательные факты о представителях фауны (стр. 28 )

Пример 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;

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

Если соответствующая вершина является конечной (“лист” дерева) или из нее выходит только одна ветвь, то для удаления записи достаточно скорректировать соответствующую ссылку у вершины-предшественника (рисунок 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)

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

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

Пример 7.27.

Рекурсивная процедура Udder исключения вершины с заданным ключом из дерева. Процедура реализует вариант а) исключения в соответствии с примером 7.25. Параметры: K – искомый ключ, D – адрес корня дерева.

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

Procedure Udder (Var D: Adrzv; K: I nteger);

       Var

               Q: Adrzv;

       {Рекурсивная процедура Ud, реализующая третий случай удаления}

       Procedure Ud (Var R: Adrzv); {При первом вызове в качестве фактического параметра передается адрес левой после удаляемой вершины}

               Begin

                       If R^.Prav=Nil        Then {Анализируемая вершина является самой правой в левом поддереве}

                               Begin

{6}                                Q^.Kl := R^.Kl; {Занесение в поле КL удаляемого звена ключа из замещающего звена (в Q – адрес удаляемого звена)}

{7}                                Q^.Adr := R^.Adr; {Занесение в поле Adr удаляемого звена ссылки на текст записи из замещающего звена}

{8}                                Q := R; {Занесение в Q адреса замещающего звена}

{9}                                R := Q^.Lev {Занесение в поле Prav звена - предшественника замещающему содержимого поля Lev из замещающего звена}

                               End

                                                                       Else {Анализируемая вершина не является самой правой в левом поддереве}

{11}                        Ud (R^.Prav) {Рекурсивный вызов процедуры Ud для перехода к следующей правой вершине левого поддерева}

               End; {Конец процедуры Ud}

       Begin {Тело процедуры Udder}

               If D = Nil        Then {Первый случай удаления}

                       Writeln (‘Звена с заданным ключом в дереве нет’)

                                                       Else

                       If K < D^.Kl        Then {Ключ в анализируемой вершине больше заданного}

{2}                        Udder (D^.Lev, K) {Рекурсивный вызов процедуры Udder для перехода к вершине слева-внизу}

                                                               Else {Ключ в анализируемой вершине меньше или равен заданному}

                               If K > D^.Kl        Then {Ключ в анализируемой вершине меньше заданного}

{3}                                Udder (D^.Prav, K) {Рекурсивный вызов процедуры Udder для перехода к вершине справа-внизу}