Двоичное дерево.
Реализация таблицы в виде двоичного дерева позволяет эффективно выполнять все три операции над таблицей. Работа с двоичными деревьями описана в следующем подразделе.
Двоичные деревья Структура двоичного дерева
Схематично двоичное дерево можно представить как набор вершин, соединенных стрелками (ветвями, Рисунок 7 .74).
Из каждой вершины выходит не более двух ветвей, направленных влево-вниз или вправо-вниз. В каждую вершину, помимо одной, входит одна стрелка. Вершина, в которую не входит ни одна стрелка, называется корнем дерева. Вершины, из которых не выходит ни одна стрелка, называются листьями.
При представлении таблицы в виде дерева тексты записей хранятся отдельно. Каждая вершина дерева (звено) является записью, состоящей из четырех полей: ключа записи (Kl), ссылки на вершину влево-вниз (Lev), ссылки на вершину вправо-вниз (Prav) и ссылки на текст записи (*). Данную структуру звена представляет Рисунок 7 .75.
Рисунок 7.74 – Схематическое представление двоичного дерева
Рисунок 7.75 – Структура звена двоичного дерева
Построение дерева
Принцип построения дерева заключается в следующем.
Первая запись делается корнем дерева. Если ключ следующей записи меньше ключа корня, то этой записи ставится в соответствие левая вершина, в противном случае – правая. Ключ К каждой последующей записи сравнивается последовательно с ключом корня, а затем с ключами тех записей, которые находятся на соответствующей ветви дерева. В зависимости от сравнения ключа К с ключом в очередной вершине осуществляется переход влево или вправо от нее до тех пор, пока не будет найдена подходящая вершина, к которой можно присоединить новую вершину с ключом К. В зависимости от результата сравнения ключа в этой вершине с поступившим ключом К вновь сформированная вершина становится левой или правой для найденной вершины.
Пример 7.21.
Построение дерева. В первоначально пустую таблицу заносятся последовательно поступающие записи с ключами 100, 20, 120, 50, 15, 130, 55, 30, 35, 60, 33, 28.
Построенное в соответствии с вышеприведенным принципом построения дерево имеет вид, который представляет Рисунок 7 .76.
С учетом структуры каждого звена дерева последовательность построения дерева по данному примеру выглядит следующим образом.
После поступления первой записи с ключом К1 = 100 дерево имеет вид, который иллюстрирует Рисунок 7 .77.
Так как у этой вершины пока нет вершин справа-внизу и слева-внизу, то в соответствующие поля (ссылки на левые и правые вершины) необходимо установить пустую ссылку (Nil).
После поступления второй записи с ключом К2 = 20 дерево имеет вид, который представляет Рисунок 7 .78.
Так как К2 < К1, то вновь созданная вершина дерева становится левой по отношению к первой. Для этого в поле Lev (адрес левой вершины) вершины 1 заносится адрес созданной вершины 2.
После поступления третьей записи с ключом К3 = 120 дерево приобретает вид, который изображает Рисунок 7 .79.
Так как К3 > К1, то вновь созданная вершина дерева становится правой по отношению к первой вершине, то есть в поле Prav вершины 1 заносится адрес вершины 3.
Аналогичные действия производятся для подключения всех последующих вершин дерева.
Рисунок 7.76 – Результирующее дерево
Рисунок 7.77 – Вид дерева после поступления первой записи
Рисунок 7.78 – Вид дерева после поступления второй записи
Рисунок 7.79 - – Вид дерева после поступления третьей записи
Таким образом, подходящей вершиной, к которой можно подсоединить новую вершину, является вершина соответствующей ветви дерева, у которой поле 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;
Над двоичными деревьями определены те же операции, что и над таблицами в целом:
поиск записи с заданным ключом;
включение записи с заданным ключом (если уже есть запись с таким ключом, то старая запись заменяется на новую);
исключение записи с заданным ключом.