ДВОИЧНЫЙ ПОИСК, АВЛ-Дерево - Структуры и алгоритмы обработки данных

Алгоритм двоичного поиска в упорядоченном массиве сводится к следующему. Берем средний элемент отсортированного массива и сравниваем с ключом X. Возможны три варианта:

Выбранный элемент равен X. Поиск завершен.

Выбранный элемент меньше X. Продолжаем поиск в правой половине массива.

Выбранный элемент больше X. Продолжаем поиск в левой половине массива.

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

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

АВЛ-Дерево

Дерево поиска называется Сбалансированным по высоте, или АВЛ - деревом, если для каждой его вершины высоты левого и правого поддеревьев отличаются не более чем на 1.

АВЛ-дерево никогда не будет в среднем по высоте превышать ИСДП более, чем на 45% независимо от количества вершин:

Log(N+1) ? hАВЛ(N) < 1,44 log(N+2) - 0,328 при N.

Таким образом, лучший случай сбалансированного по высоте дерева - ИСДП, худший случай - плохое АВЛ - дерево. Плохое АВЛ - дерево это АВЛ-дерево, которое имеет наименьшее число вершин при фиксированной высоте. Рассмотрим процесс построения плохого АВЛ-дерева. Возьмем фиксированную высоту h и построим АВЛ - дерево с минимальным количеством вершин. Обозначим такое дерево через TH. Ясно, что Т0 - пустое дерево, Т1 - дерево с одной вершиной. Для построения ТH при h > 1 будем брать корень и два поддерева с минимальным количеством вершин.

Одно поддерево должно быть высотой H-1, а другое высотой H-2. Поскольку принцип их построения очень напоминает построение чисел Фибоначчи, то такие деревья называют Деревьями Фибоначчи: TH = < TH-1, x, TH-2 >. Число вершин в TH определяется следующим образом:

N0 = 0, N1 = 1, NH = NH-1 + 1 + NH-2

Повороты при балансировке

Рассмотрим, что может произойти при включении новой вершины в сбалансированное по высоте дерево. Пусть r - корень АВЛ-дерева, у которого имеется левое поддерево (ТL) и правое поддерево (TR). Если добавление новой вершины в левое поддерево приведет к увеличению его высоты на 1, то возможны три случая:

    1) если hL = hR, то ТL и TR станут разной высоты, но баланс не будет нарушен; 2) если hL < hr, то тl и tr станут равной высоты, т. е. баланс даже улучшится; 3) если hl > hR, то баланс нарушиться и дерево необходимо перестраивать.

Введем в каждую вершину дополнительный параметр Balance (показатель баланса), принимающий следующие значения:

    -1, если левое поддерево на единицу выше правого; 0, если высоты обоих поддеревьев одинаковы; 1, если правое поддерево на единицу выше левого.

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

Добавление вершины в дерево

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

Поиск элемента с заданным ключом, включения нового элемента, удаления элемента - каждое из этих действий в АВЛ-дереве можно произвести в худшем случае за О(log N) операций.

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

Похожие статьи




ДВОИЧНЫЙ ПОИСК, АВЛ-Дерево - Структуры и алгоритмы обработки данных

Предыдущая | Следующая