5.3. Основные операции и возможная структура древовидной таблицы
 

Основными функциональными операциями над древовидными таблицами являются:

• инициализация таблицы;
• включение элемента в таблицу;
• поиск элемента по ключу;
• удаление элемента;
• сохранение таблицы в файле;
• восстановление таблицы из файла;
• обходы дерева в таблице.

Эти операции по выполняемым функциям схожи с аналогичными операциями над бинарными деревьями поиска, однако aлгоритмы реализации их существенно различны. Это вызвано тем, каждый узел бинарного дерева поиска размещается в динамической памяти, получаемой при включении узла и освобождаемой при его удалении. Узлы же бинарного дерева в древовидной таблице размещаются в массиве (в векторной памяти). Это вызывает необходимость ведения списков занятых и свободных элементов массива. Список занятых элементов определяется указателями в узлах, начиная с корня, для ведения списка свободных элементов можно использовать один из указателей в свободных элементах. Для каждого списка необходим указатель на его начало.

Так как число элементов в массиве фиксировано, то требуется вести счетчик занятых элементов массива, а для сохранения таблицы в файле и последующего ее чтения из файла нужна информация о размере таблицы. Следовательно, таблица должна содержать некоторую управляющую информацию, включающую: указатель на корень дерева; указатель на начало списка свободных элементов; счетчик числа занятых элементов; число элементов таблицы.

Исходя из этого можно предложить такую структуру таблицы, в которой первые две строки заняты управляющей информацией. Массив имеет n элементов, первые два из которых содержат управляющую информацию, остальные m=n-2 предназначены для элементов двоичного дерева поиска.
Таблица.

Указатель на корень	Пусто	Указатель списка свободных элементов
Счетчик занятых	Пусто	Размер таблицы m
Левый указатель	Ключ + данные	Правый указатель/ Указатель свободного элемента
...	...	...
...	...	...

Инициализация таблицы. При инициализации таблицы обнуляются все левые указатели, включая указатель на корень и счетчик занятых элементов, очищаются поля ключей и данных. В указатель списка свободных элементов заносится индекс первой свободной строки, т.е. 2. Размер таблицы m устанавливается равным либо m = n (число строк массива), либо m = n - 2 (максимальное число узлов дерева). Правые указатели, начиная с третьей строки массива (с индексом i = 2), должны показывать на последующие строки (3, 4, ..., n). Правый указатель в последней строке можно обнулять, так как возможность включения нового элемента определяется не концом списка свободных элементов, а счетчиком занятых элементов. В качестве примера рассмотрим табл., в которой поле «Ключ+данные» представлено только ключом, имеющим положительные целочисленные значения, n= 15, m = 13. Таблица 6.2

0	0	2
0	0	13
0	0	3
0	0	4
...	...	...
0	0	i+1
...	...	...
0	0	14
0	0	15

Пусть элементы таблицы имеют структуру
struct KR
{ int L;     /* Левый указатель */
int key;    /* Поле ключа */
int R;       /* Правый указатель */
} Т[15];     /* Массив под таблицу */

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

Исходные данные для включения — таблица Т и ключ key >0.
Состояние таблицы в момент включения:

а) полная;
б) пустая;
в) заполнена частично.

1. Выбираем индекс j первой свободной строки из указателя списка свободных j = T[0].R и заносим его в указатель корня дерева T[0].L=j.
2. Корректируем указатель списка свободных элементов, заненеся в него указатель на следующий свободный элемент T[0].R=T[j].R
3. В свободной строке j формируем узел дерева R[j].key=key; T[j].L=T[j].R=0
4. Корректируем счетчик занятых элементов, увеличив его на единицу T[l].L=T[l].L+l.

1. Начиная с вершины дерева i=T[0].L, ищем ключ или место включения нового элемента. Исходы поиска: ключ найден или не найден.
2. Ключ найден, возврат — 1.
3. Ключ не найден: выбираем свободную строку j из списка свободных и переносим индекс j в указатель предыдущей строки.
4. Выполняем пункты 2), 3), 4) состояния б).

а) Таблица пустая, т.е. T[1].L = = 0, возврат — 2.
б) Таблица не пустая.

1. Начиная с вершины дерева j=Т[О].L, ищем ключ. Исход: найден или нет.
2. Найден — возврат индекса j найденной записи, не найден — возврат — 1.

а) Узел не имеет потомков.
б) Узел дерева с двумя потомками.
в) Узел дерева с одним потомком,

а) Узел не имеет потомков.
Если узел является корнем дерева, то:

1. Обнуляем указатель на корень дерева (указатель списка занятых элементов) T[0].L=0.
2. Счетчик занятых T[1].L уменьшаем на 1.
3. Корректируем список свободных элементов, включив освобожденную строку в начало списка свободных: T[j].R=T[0].R; T[0].R=j. Чистим левый указатель и ключ строки j: T[j].L=0; T[/].key=O.
5. Возврат j.

б) Узел дерева с двумя потомками.

1. Шаг по дереву влево вниз на один уровень, затем вправо вниз до конца. При каждом движении запоминаем адрес предыдущего указателя.
2. Данные+ключ (здесь только ключ) конечного элемента пересылаем в поле данные+ключ удаляемого элемента.
3. Левый указатель конечного элемента пересылаем в предыдущий указатель.
4. Выполняем пункты а) 2—5.

в) Узел дерева с одним потомком.
Если удаляемый узел является корнем дерева, то в указатель списка занятых заносим индекс следующего элемента (правого или левого) по дереву, затем выполняем пункты а) 2—5.

Если же удаляемый элемент является промежуточным узлом дерева, то в указатель предыдущего элемента заносим индекс следующего элемента, затем опять-таки выполняем пункты а) 2-

Отметим, что при удалении любого узла выполняются пункты а) 2—5.
Сохранение таблицы в файле . Исходными данными являю таблица Т и имя файла. Естественно, сохраняются только не пустые таблицы.

1. Получение имени файла.
2. Открытие файла для записи (как выходного), если это существующий файл, то старые записи затираются. Если файл не удастся открыть, то возврат -1.
3. Извлечение из таблицы размера таблицы m = T[l].L n = m + 2.
4. Форматированный вывод в файл n записей из таблицы.
5. Закрытие файла. Возврат 0.

Восстановление таблицы из файла . Исходные данные файла. Возвращаемое значение — указатель на динамическую таблицу либо NULL в случае неудачи.

1. Получение имени файла.
3. Открытие файла, в случае неудачи возврат NULL. Ввод из файла двух первых записей с управляющей информацией таблицы в переменные типа KR.
4. Извлечение размера таблицы из второй записи и определение общего числа элементов n=m + 2.
5. Получение динамической памяти для таблицы с n элементами.
6. Занесение в таблицу первых двух элементов, считанных из файла раньше.
7. В цикле ввод из файла последующих (n - 2) записей в строки i = 2, 3, ..., n - 1.
8. Возврат указателя на таблицу. По этому указателю теперь можно выполнять все операции, рассмотренные выше (кроме инициализации таблицы).

Обходы дерева в таблице . При рассмотрении деревьев в списковой памяти мы отмечали, что для управления деревом создается дескриптор, содержащий такие данные, как имя дерева, дата создания, информация об узлах дерева и обязательно указатель на корень дерева. Обращение к дереву осуществляется через дескриптор по схеме:
Указатель на дескриптор -> Дескриптор —> Корень дерева.

В простейшем случае дескриптор содержит только указатель на корень дерева, тогда обращение к дереву предельно упрощается:
Указатель на корень дерева —> Корень дерева.

Для управления деревом в древовидной таблице мы создали управляющую информацию в первых двух строках таблицы, корень дерева первоначально находится в третьей строке, а по мере удаления элементов может переместиться в любую строку таблицы, кроме первых двух. Указатель на корень дерева всегда находится в левом указателе первой строки T[0].L.

Для обхода дерева в списковой памяти мы применяли рекурсивные функции. Функция обхода содержала только один параметр: указатель на корень дерева. Применение аналогичной функции обхода в древовидной таблице потребует наличия двух параметров: указателя на таблицу (массив) и указателя на корень, содержащего индекс строки таблицы с корнем, то есть целого числа ≥2. Если таблица находится в массиве Table, то обращение к функции нисходящего обхода имеет вид: Preorder(Table, Table[0].L).

[Оглавление]

[<<страница]

[>>страница]

[В начало ]