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

               Poisk := B {Возвращаемое значение функции}

       End;

Недостаток способа 4 – он плохо приспособлен для реализации включения и исключения записей, так как необходимо сдвигать все последующие после вставляемого или исключаемого элементы массива в ту или другую сторону для поддержания упорядоченности элементов. Поэтому способ 4 удобно использовать, если таблица изменяется редко.

Двоичное дерево.

Реализация таблицы в виде двоичного дерева позволяет эффективно выполнять все три операции над таблицей. Работа с двоичными деревьями описана в следующем подразделе.

7.5. Двоичные деревья

7.5.1. Структура двоичного дерева

Схематично двоичное дерево можно представить как набор вершин, соединенных стрелками (ветвями, рисунок 7.19).

Из каждой вершины выходит не более двух ветвей, направленных влево-вниз или вправо-вниз. В каждую вершину, помимо одной, входит одна стрелка. Вершина, в которую не входит ни одна стрелка, называется корнем дерева. Вершины, из которых не выходит ни одна стрелка, называются листьями. 

Рисунок 7.19 – Схематическое представление
двоичного дерева

При представлении таблицы в виде дерева тексты записей хранятся отдельно. Каждая вершина дерева (звено) является записью, состоящей из четырех полей: ключа записи (Kl), ссылки на вершину влево-вниз (Lev), ссылки на вершину вправо-вниз (Prav) и ссылки на текст записи (*). Данную структуру звена представляет рисунок 7.20.

Рисунок 7.20 – Структура звена двоичного дерева

7.5.2. Построение дерева

Принцип построения дерева заключается в следующем.

Первая запись делается корнем дерева. Если ключ следующей записи меньше ключа корня, то этой записи ставится в соответствие левая вершина, в противном случае – правая. Ключ К каждой последующей записи сравнивается последовательно с ключом корня, а затем с ключами тех записей, которые находятся на соответствующей ветви дерева. В зависимости от сравнения ключа К с ключом в очередной вершине осуществляется переход влево или вправо от нее до тех пор, пока не будет найдена подходящая вершина, к которой можно присоединить новую вершину с ключом К. В зависимости от результата сравнения ключа в этой вершине с поступившим ключом К вновь сформированная вершина становится левой или правой для найденной вершины.

Пример 7.21.

Построение дерева. В первоначально пустую таблицу заносятся последовательно поступающие записи с ключами 100, 20, 120, 50, 15, 130, 55, 30, 35, 60, 33, 28.

Построенное в соответствии с вышеприведенным принципом построения дерево имеет вид, который представляет рисунок 7.21.

Рисунок 7.21 – Результирующее дерево

С учетом структуры каждого звена дерева последовательность построения дерева по данному примеру выглядит следующим образом.

После поступления первой записи с ключом К1 = 100 дерево имеет вид, который иллюстрирует рисунок 7.22.

Рисунок 7.22 – Вид дерева после поступления первой записи

Так как у этой вершины пока нет вершин справа-внизу и слева-внизу, то в соответствующие поля (ссылки на левые и правые вершины) необходимо установить пустую ссылку (Nil).

После поступления второй записи с ключом К2 = 20 дерево имеет вид, который представляет рисунок 7.23.

Рисунок 7.23 – Вид дерева после поступления второй записи

Так как К2 < К1, то вновь созданная вершина дерева становится левой по отношению к первой. Для этого в поле Lev (адрес левой вершины) вершины 1 заносится адрес созданной вершины 2.

После поступления третьей записи с ключом К3 = 120 дерево приобретает вид, который изображает рисунок 7.24.

Так как К3 > К1, то вновь созданная вершина дерева становится правой по отношению к первой вершине, то есть в поле Prav вершины 1 заносится адрес вершины 3.

Аналогичные действия производятся для подключения всех последующих вершин дерева.

Рисунок 7.24 – Вид дерева после поступления третьей записи

Таким образом, подходящей вершиной, к которой можно подсоединить новую вершину, является вершина соответствующей ветви дерева, у которой поле Lev или Prav (в зависимости от соотношения ключей ее и новой вершины) равно Nil.

Двоичное дерево может быть введено в употребление с помощью описания, приведенного в примере 7.22.

Пример 7.22.

Описание двоичного дерева.

Type

       Tekst = <Тип_значения_записи>;

       Adrt = ^Tekst;

       Adrzv = ^Zveno;

       Zveno =        Record

               Kl:I nteger;

               Lev, Prav: Adrzv;

               Adr: Adrt

               End;

Var

       Dvder: Adrzv;

Над двоичными деревьями определены те же операции, что и над таблицами в целом:

поиск  записи с заданным ключом; включение записи с заданным ключом (если уже есть запись с таким ключом, то старая запись заменяется на новую); исключение записи с заданным ключом.

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

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

Пусть имеется объявление по примеру 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.5.4. Включение записи в дерево

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

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

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

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