ОБ ОПТИМИЗАЦИИ ПРОЦЕДУР ПОИСКА НА ОСНОВЕ ПОИСКОВЫХ ДЕРЕВЬЕВ

ABOUT OPTIMIZATION OF PROCEDURES OF SEARCH ON BASIS OF SEARCHING TREES

Gulzada Sartayeva

master of Saint Petersburg National Research University of Information Technologies, Mechanics and Optics,

Russia, Saint Petersburg

Igor Bessmertny

doctor of Engineering Sciences, associate professor of the computing engineering department of Saint Petersburg national research university of information technologies, mechanics and optics,

Russia, Saint Petersburg

АННОТАЦИЯ

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

ABSTRACT

In hired the problem to define the structures of data is set, that allows to synthesize the effective algorithm of construction of AVL- of tree. In spite of general chart of pencil description of algorithm, during realization description of algorithm depends on the structure of data, in this connection the synthesis of effective algorithm the “research programs” present undoubted scientific interest.

Ключевые слова: АВЛ-деревья, алгоритмы поиска, синтез алгоритма, построение и оптимизация АВЛ-деревьев.

Keywords: AVL-trees, algorithms of search, synthesis of algorithm, construction and optimization of AVL-trees.

В данной статье рассматривается оптимизация эффективного алгоритма построения AVL-дерева с учетом выбранной структуры данных. Были исследованы информационно-поисковые деревья алгоритма поиска, структуры данных и поисковые алгоритмы. Методы исследования включают: метод поиска информации и комбинаторные алгоритмы поиска.

AVL-деревья относятся к классическим деревьям поисковых структур данных. Оптимизация процедур поиска на таких деревьях представляет несомненный интерес.

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

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

Требования к вспомогательной памяти не очень высоки. Например, для баланса AVL-дерева можно использовать лишь 2 бита на каждую вершину, плюс 1 бит для всех вершин дерева.

Актуальностью исследования представляется то, что построение поисковых процедур для информационно-поисковых деревьев относится к фундаментальному управлению Computer Science, среди этих деревьев особый интерес представляют классы деревьев, обладающие экстремальными свойствами. К таким типам и относится AVL-дерево.

В нашем случае поддержка баланса для этого класса деревьев осуществляется с помощью процедур левого и правого поворотов, а сама процедура включает несколько, слабо зависимых процедур:

1. Первая процедура – это вставка вершины в дерево. Эти процедуры представляют собой части эффективной процедуры построения AVL-дерева. Как известно, в случае одного поворота происходит переключение максимально трех ссылок, а в случае двух поворотов как в AVL-дереве, как и в красно-черном дереве не более шести ссылок.
2. В случае AVL-дерева вторая процедура будет пересчет балансов вершин выделенного пути.
3. Третья процедура – это определение количества поворотов необходимых на балансировку (bal tree) и ее выходом является уже сбалансированное дерево.
4. Четвертая процедура – это корректировка балансов в окрестности критической вершины.

Отсюда следует, что процедуры представляют собой части эффективной процедуры построения AVL-дерева.

Выделенный путь – это путь из корня дерева во вновь вставленную вершину. Критическая вершина выделенного пути – самый дальний разбалансированный потомок корня.

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

Во-первых, несмотря на то, что деревья этого типа могут выглядеть довольно несимметричными, но у них как выясняется, нет лишних ветвей, о чем, в принципе, можно догадаться внимательно прочитав приводимое ниже определение. Максимальная длина ветви, исходящая из корня такого дерева не превосходит величины  (оценка высоты дерева).

Во-вторых, добавление или изъятие элемента (вершины) не потребует перестройки всего дерева, при этом, как это ни странно на первый взгляд, алгоритм построения такого дерева, невзирая на определенные сложности в обосновании, не является трудоёмким.

Часто вместо названия длина используют и другое название – высота. Балансом вершины дерева называется разность длин левой и правой ветвей исходящих из данных вершины.

Дерево называется сбалансированным (AVL) деревом, если каждой его вершины абсолютное значение баланса не превосходит 1.

Оценка длины самой длинной ветви в AVL дереве, построенном по массиву, содержащему n элементов. Для этого зафиксируем число -1 и первоначально рассмотрим множество AVL-деревьев с максимальной длиной ветви, равной -1 (число сравнений необходимых для поиска элемента находящегося в конце пути исходящего из корня дерева и имееющего длину ). Здесь можно вспомнить функции Шеннона, правда аналогия не вполне корректна, так как функция Шеннона это функция вида max min, а не min max, как в нашем случае (функция минимальное число вершин в AVL-дереве) [1].

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

Рисунок 1. Схема поворота дерева

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

Рассмотрим рисунок 2, не опуская важных деталей случай, когда баланс критической вершины А до вставки был равен – 1.

Рисунок 2. Критическая вершиная А

Обычно именно этот случай, когда баланс вершины А равен +1с разной степенью детализаци, причем не всегда достаточной и разбирается в литературе. Так как баланс вершины А (до вставки) равен, по предположеию – 1, то его правое поддерево непустое. Пусть С – правый непосредственно потомок узла А [1–2].

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

Список литературы:

1. Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1989. – 360 с.
2. Дюсембаев А.Е. Информатика: структуры данных, сортировка, поиск: учеб. пособие по Computer Science. Образов. прогр. Европ. Союза TEMPUS-TACIS (Contract # CD JEP-22077-2001) / Дюсембаев Ануар Е.; Каз. нац. ун-т им. аль-Фараби, НИИ математики и механики, мех.-мат. фак., каф. информатики. – Алматы: Дайыр Баспа, 2012. – 154 с.
3. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. – М., «Мир», 1978 г.