А.Ю. Попов
6
в СП трассы позволяет существенно ускорить доступ к соседним ча-
стям дерева.
В каждой вершине
Каталога
хранится следующая информация:
•
параметры Low и High — нижняя и верхняя границы ключей в
поддереве. Эти параметры используются для определения вершины
Каталога
, в котором может находиться искомый ключ;
•
атрибуты А вершины
Каталога
: номер структуры; номера
предшествующей и последующей вершин; адрес дочернего набора
Каталога
в локальной памяти данных СП; флаг переполнения вер-
шины; некоторые дополнительные атрибуты, ускоряющие обработку.
Реализация основных команд.
Рассмотрим реализацию коман-
ды
Добавление
ADD(structure, key, data), где
structure
— номер струк-
туры,
key
— ключ,
data
— информационная часть. Команда состоит в
поиске вершины, соответствующей заданному значению ключа и
продвижению к нижнему уровню
Каталога
. Если ключ
key
выходит
за границы раздела
Каталога
[Low, High], выполняется подъем в де-
реве, после чего операция повторяется. Если же найдена вершина с
соответствующими
key
границами (Low ≤ key ≤ High), то происходит
модификация информации в
Каталоге
и начинается нисходящее
движение вплоть до уровня
n
–1. Для нижнего уровня
n
–1 выполняет-
ся вставка в блок данных в
Операционном буфере
. Алгоритм работы
операции
Добавление
представлен ниже:
НАЧАЛО:
Направление поиска — вверх:
d
= –1
ДОБАВЛЕНИЕ:
Поиск
вершины на текущем уровне
t
ЕСЛИ
(
Поиск
успешен) ИЛИ (
t
== 0) ИЛИ (
d
== +1)
Направление поиска — вниз:
d
= +1
Изменить
Каталог
ЕСЛИ
(
Каталог
переполнен)
ЕСЛИ
(
t
≠ 0)
Деление
вершины
ИНАЧЕ
Ошибка: Структура заполнена
КОНЕЦ
ВСЕ ЕСЛИ
ВСЕ ЕСЛИ
ЕСЛИ
(
t
==
n
–1)
Изменить
Операционный буфер
КОНЕЦ
ИНАЧЕ
t
=
t
+
d
