ПОИСКОВАЯ СИСТЕМА ДЛИТЕЛЬНОГО ПОЛЬЗОВАНИЯ НА БАЗЕ АВЛ-ДЕРЕВА

В.С. Зубов, В.В. Шевченко

(Москва, Московский энергетический институт (ТУ), Российская Федерация)

Акт поиска в АВЛ-дереве имеет среднюю и максимальную сложность O(log n), а построение АВЛ-дерева – O(n log n), где n – число узлов дерева [1]. Эти «идеальные» характеристики – причина широкого использования АВЛ-деревьев в памяти компьютера как динамических поисковых структур. С ростом объемов памяти растет и актуальность АВЛ-деревьев, ибо поисковые задачи, прежде требовавшие использования винчестера, теперь удовлетворяются поиском данных в памяти, т.е. решаются гораздо быстрее.

Дерево, использующее указатели для связи узлов, не может быть сохранено на винчестере без сложного преобразования. В [2] рассмотрена идея построения АВЛ-дерева с помощью курсоров (целочисленных ссылок) и приведены два блока из 7 необходимых: блоки вставки и удаления узла из АВЛ-дерева. Такое АВЛ-дерево, представленное массивом записей, может быть сохранено на винчестере как файл записей и восстановлено без преобразований, однако отказ от указателей порождает проблемы расширения дерева при неконтролируемом его росте и «уборки мусора».

Первая решается использованием динамического массива, увеличиваемого при нехватке узлов (автоматическая реорганизация). Естественно, приращение массива должно выполняться не на одну или несколько записей, а сразу для множества узлов, иначе в работе поисковых систем с большой динамикой данных возникнут частые задержки. Достоверный прогноз, учитываемый при задании исходного размера массива, также снизит затраты времени на его реорганизации.

В простейшем варианте проблема «уборки мусора» решается переносом записи из последней занятой позиции массива в освободившуюся, т.е. локальной перестройкой, производимой при каждом удалении узла. Представление АВЛ-дерева массивом и поиск в таком дереве выполняются на 10% быстрее построения традиционного АВЛ-дерева и поиска в нем. Код используемых подпрограмм не увеличился, а напротив, сократился. Рекурсия в них не используется из соображений снижения затрат времени. Использован Object Pascal.

Узел АВЛ-дерева представлен записью, в которой ссылки на сыновей узла

представлены полями son[true] (левый сын) и son[false] (правый сын). Необычный индекс позволяет сократить число ветвлений в коде подпрограмм. Пустая ссылка обозначается нулем.

Первым изучим блок поиска по совпадению аргумента arg и ключа (q = 0), по близости снизу (q =-1) и по близости сверху (q =1). Эта функция возвращает 0 при неудачном поиске, либо номер найденной записи в массиве z. Запись с номером 0 является служебной. В ней поле z[0].p является счетчиком узлов, поэтому для порождения АВЛ-дерева достаточно задать размер массива z и выполнить оператор z[0].p:= 0.

Function PoiskAVL (Var z: Array of zap; arg: tipkey; q: integer = 0): integer;

Var t: integer; b: Boolean; r: Array [Boolean] of integer;

begin

Result:= 0; If z[0].p = 0 then Exit; // Выход, если дерево пусто

t:= z[0].son[true]; r[false]:= 0; r[true]:= 0; // t – ссылка на текущий узел трассы поиска

While t > 0 do With z[t] do

begin If key = arg then begin Result:= t; Break end;

b:= arg < key; r[b]:= t; t:= son[b] // Продвижение по трассе

end;

If q = 0 then Exit; // Окончание поиска по совпадению

If Result = 0 then Result:= r[q > 0] // Окончание поиска по близости

end;

Блок учитывает особые случаи через значения элементов r[true] (ссылка на ближайший к arg больший ключ) и r[false] (ссылка на ближайший к arg меньший ключ). Если в дереве нет ключа, большего arg, то в трассе поиска нет ни одного звена, направленного влево. Тогда r[true] сохраняет исходное значение и присваивание Result:= r [q > 0] задаст значение 0 результату поиска по близости сверху. Конечно, если ключ, равный arg, найден, результатом будет номер соответствующей записи.

Следующим рассмотрим блок обхода дерева слева, обеспечивающий обработку (чтение) записей в порядке возрастания их ключа key. Запись без рекурсии позволяет просто выполнять частичный обход при поиске записей по интервалу значений ключа.

Procedure Obrab(t: integer); // Наш блок обработки попросту заносит в строку s

begin s:= s + IntToStr(z[t].key) + ' ' end; // значения целочисленных ключей записей

Procedure ObhodBD (Var z: Array of zap); // Блок обхода двоичного дерева слева

Var j, t: integer; b: Boolean; st: Array[1..33] of integer;

begin

If z[0].p = 0 then Exit; // Выход, если дерево пусто

b:= true; j:= 0; t:= z[0].son[true]; // t – ссылка на текущий узел при обходе

Repeat

If j > 0 then begin t:= st[j]; Dec(j); b:= false end; // Взятие очередного узла из стека st

Repeat If b then While z[t].son[true] > 0 do // Проход «до упора» влево без обработки узлов,

begin Inc(j); st[j]:= t; t:= z[t].son[true] end; //но с занесением узлов в стек st

b:= true; Obrab (t); t:= z[t].son[false] // Обработка узла с продвижением в правую ветвь

Until t = 0 // Очередная правая ветвь исчерпана; переход к взятию узла из стека

Until j = 0 // В стеке не осталось узлов; окончание обхода слева

end;

Блок ObhodBD пригоден для обхода любого бинарного дерева. Специфика имеется лишь при частичном обходе АВЛ-дерева, требуемом при поиске по интервалу, когда определяется отправная точка обхода. Проблема возникает, если записи с равным значением ключа допускаются. Поясним ее. Пусть выполняется поиск по интервалу [A, B] значений ключа. Если записи с ключом A есть, мы найдем одну из них; начиная от нее обход части дерева слева, можем упустить записи с ключом A, находящиеся «левее».

Лемма 1. Перестройки в АВЛ-дереве, поддерживающие его сбалансированность, не изменяют характер упорядоченности данных за одним исключением: и в левом, и в правом поддереве некоторого узла U могут иметься узлы с таким же значением ключа, тогда как в обычном бинарном дереве они группируются в одном из поддеревьев.

Представим, что записи с равным значением A ключа поступают в дерево непрерывно. Они направляются в правое поддерево включенного первым узла с ключом A, но быстро возникает дисбаланс этого узла и после перестройки он оказывается в левом поддереве другого узла с ключом A.

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

Лемма 2. Если узлы с равным ключом A имеются и в левом, и в правом поддереве некоторого узла U, то и узел U содержит ключ A. Ключ узла U не должен превосходить ни одного ключа правого поддерева в силу упорядоченности дерева, поэтому он не больше A, но он не может быть меньше A, ибо тогда окажется меньше ключа из левого поддерева, что также противоречит упорядоченности дерева.

Лемма 3. Равные ключи двух поддеревьев одного узла должны быть большими в левом поддереве и меньшими в правом. Это утверждение непосредственно следует из леммы 2.

Лемма 4. При поиске ключа A, начиная от корня дерева, первым будет найден узел U с ключом A, в поддеревьях которого сосредоточены все записи с ключом A (ссли повторы ключа A имеют место). Как указано выше, в узлах на пути от корня к узлу U ключей A нет. Если бы найден был не узел U, это означало бы, что к узлу из его поддерева имеется путь от корня в обход U. Дублирование пути возможно в решетке, но не в дереве.

На основе данных лемм построим алгоритм нахождения самой «левой» из равных записей в АВЛ-дереве. Первым этапом явится нахождение узла U с заданным ключом A. Его заносим в стек. Правое его поддерево не рассматриваем. На пути влево от узла U (рис.1) может быть ряд узлов с ключом A. Их заносим в стек и пропускаем, ибо в правых их поддеревьях все ключи равны A. Рассматриваем левое поддерево самого левого из этих узлов V (в этой роли может оказаться узел U). Если в поддереве есть хотя бы один ключ A, то ключ A имеется в узле, ближайшем по значению к ключу узла V, т.е. в конце пути направо от корня поддерева. На этом пути могут быть и другие узлы с ключом A. Как и раньше, нас интересует самый левый из них, от которого мы вновь направляемся влево, как вначале от узла U, и т.д. Рассматриваемая трасса поиска «зигзагообразна». Она заканчивается пустой ссылкой. Все узлы трассы с ключом A заносим в стек и самый «левый» из них остается в верхушке стека. Точное описание процесса дано ниже:

j:= 0; t:= z[0].son[true]; // t – текущая ссылка; начинаем от корня дерева

While t > 0 do With z[t] do // Главный цикл поиска

begin If key = A then

begin

Repeat Inc(j); st[j]:= t; b:=false; // Найден первый узел с ключом A

While z[t].son[true] > 0 do

begin t:=z[t].son[true]; // Движение влево, пока ключи равны A

If z[t].key = A then begin Inc(j); st[j]:= t end

Else begin b:= true; Break end // Достигнут первый узел с ключом, который меньше A

end; If b then

While z[t].son[false] > 0 do

begin t:=z[t].son[false]; // Движение вправо до узла с ключом A или до пустой ссылки

If z[t].key = A then Break

end

Until not b or (z[t].key <> A); Break // Прерывание главного цикла, когда продолжение

end; // поиска уже не добавляет в стек узлов с ключом A

b:= A < z[t].key; // Пока ключ A не найден, идем по трассе поиска и заносим в стек

If b then begin Inc(j); st[j]:= t end; t:= z[t].son[b] // узлы, от которых трасса идет влево

end {главного цикла};

Сложность поиска равна O(log n), она невелика в сравнении с обычным временем обработки множества записей интервала. Поиск всех записей с заданным ключом – это частный случай поиска по интервалу. Рассмотренный цикл вместе с частичным обходом дерева слева включен в специальный блок поиска по интервалу. Предусмотрены случаи полуоткрытого интервала: поиск всех ключей, которые больше или меньше заданного ключа.

Кроме указанных блоков, предусмотрены процедуры сохранения на винчестере и восстановления АВЛ-дерева. Блок UdAVL (удаление узла) из [2] дополнен операторами

q:= 0; b2:= true; n:= z[0].p; // n – последняя используемая позиция массива z

While z[q].son[b2] <> n do // Цикл поиска номера q отца узла, занимающего

begin q:= z[q].son[b2]; b2:= z[n].key < z[q].key end; // позицию n

z[t]:= z[n]; z[q].son[b2]:= t; Dec(z[0].p) // Перенос узла в освободившуюся позицию t

end; // Закрывающая скобка процедуры UdAVL

Это расширение процедуры предназначено для случая уникальных ключей. Если значения ключа не уникальны, при поиске номера q используется частичный обход слева.

Локальность алгоритмов построения дерева и поиска в нем зависят от компактности его представления. Известно, что в бинарном дереве половина ссылок пустует. Эти «излишества» особо выделяются при небольшой длине записей. Изменив формат записей и отказавшись от одной ссылки в каждом узле, можно сэкономить память за счет некоторого усложнения действий в дереве. В таких АВЛ-деревьях с большим числом узлов даже снижаются затраты времени за счет уменьшения числа промахов мимо кэша.

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

Лишь дерево, реализованное с помощью курсоров (массива), позволяет исключить ссылки на записи, становясь еще компактнее. Располагая 240 Мб памяти, можем работать с 15 млн. записей, имеющих целый ключ, т.е. оперативно обрабатывать данные объемом в десятки Гбайт – при больших записях. Подобное АВЛ-дерево реализовано практически без усложнения подпрограмм.

Результатом последних исследований АВЛ-деревьев является новое их представление, обозначаемое нами как АВЛ⁺-дерево, в котором каждый узел содержит лишь одну ссылку (курсор). Сокращая затраты памяти, АВЛ⁺-дерево особенно актуально в тех применениях, когда обычное представление перестает умещаться в памяти. Увеличим в предыдущем примере число записей до 25 млн. АВЛ⁺-дерево займет приблизительно 230 Мб памяти.

Новое представление потребовало радикальной переработки подпрограмм и некоторого увеличения их кода. Эти затраты окупаются высоким быстродействием работы поисковых систем с большим объемом данных. Подобная модернизация красно-черных деревьев, широко рекламируемой разновидности перестраиваемых бинарных деревьев [3, 4], вряд ли осуществима, да и нецелесообразна, ибо и традиционная их реализация уступает АВЛ-деревьям в быстродействии.

Система подпрограмм для работы с АВЛ- и АВЛ⁺-деревьями хранится на кафедре математического моделирования МЭИ, доступна для внедрения в новые приложения.

Итак, при построении поисковой системы решены некоторые общие для бинарных деревьев и специфические – для АВЛ-деревьев – проблемы.

ЛИТЕРАТУРА

1. Кнут Д.Э. Искусство программирования, том 3. Сортировка и поиск, 2-е изд.: Пер. с англ. М.: Изд. дом «Вильямс», 2000. – 822 с.: ил.

2. Зубов В.С., Шевченко И.В. Структуры и методы обработки данных: Практикум в среде Delphi. – М.: Информационно-издательский дом «Филинъ», 2004. – 304 с.

3. Седжвик Р. Фундаментальные алгоритмы на C. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск. СПб: ООО «ДиаСофтЮП», 2003.

4. Бакнелл Дж. М. Фундаментальные алгоритмы и структуры данных в Delphi. СПб: ООО «ДиаСофтЮП», 2003. – 560 с.