Реализация АВЛ–деревьев через классы объектно–ориентированного программирования (стр. 4 из 6)

Малое правое вращение.

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

Рис. 10.

Большое левое вращение.

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

Рис. 11.

Большое правое вращение.

Большое правое вращение применяется, когда показатель сбалансированности вершины, в которой произошло нарушение баланса, равен 2, а показатель сбалансированности корня правого поддерева равен -1 или 0. Большое правое вращение симметрично большому левому и схематично изображено на рисунке 12:

Рис. 12.

Повороты необходимы, когда родительский узел P становится разбалансированным. Одинарный поворот вправо (single right rotation) происходит тогда, когда родительский узел P и его левый сын LC начинают перевешивать влево после вставки узла в позицию X. В результате такого поворота LC замещает своего родителя, который становится правым сыном. Бывшее правое поддерево узла LC (ST) присоединяется к P в качестве левого поддерева. Это сохраняет упорядоченность, так как узлы в ST больше или равны узлу LC, но меньше узла P. Поворот уравновешивает как родителя, так и его левого сына (рис. 13).

// выполнить поворот по часовой стрелке вокруг узла p

// сделать lc новой точкой вращения

template <class T>

void AVLTree<T>::SingleRotateRight (AVLTreeNode<T>* &p)

{

// левое, перевешивающее поддерево узла p

AVLTreeNode<T> *lc;

// назначить lc левым поддеревом

lc = p->Left();

// скорректировать показатель сбалансированности для родительского узла и его левого сына

p->balanceFactor = balanced;

lc->balanceFactor = balanced;

// правое поддерево узла lc в любом случае должно оставаться справа от lc, выполнить это условие, сделав st левым поддеревом узла p

p->Left() = lc->Right();

// переместить p в правое поддерево узла lc

// сделать lc новой точкой вращения

lc->Right() = p;

p = lc;

}

Рис. 13

Рис. 14.

Попытка вставить узел 5 в изображенное на рисунке 14 АВЛ - дерево нарушает АВЛ - условие для узла 30. Одновременно левое поддерево узла 15 (LC) становится перегруженным.

Для переупорядочения узлов вызывается процедура SingleRotateRight. В результате родительский узел (30) становится сбалансированным, а узел 10 перевешивающим влево. Двойной поворот вправо (double right rotation) нужен тогда, когда родительский узел (P) становится перевешивающим влево, а его левый сын (LC) перевешивающим вправо. NP – корень правого перевешивающего поддерева узла LC. Тогда в результате поворота узел NP замещает родительский узел. На рисунках 15 и 16 показаны случаи вставки нового узла в качестве сына узла NP. В обоих случаях NP становится родительским узлом, а бывший родитель P становится правым сыном NP.

На рисунке 15 мы видим сдвиг узла X1, после того как он был вставлен в левое поддерево узла NP. На рисунке 16 изображено перемещение узла X2 после его вставки в правое поддерево NP.

Рис. 15.

Рис. 16

// двойной поворот вправо вокруг узла p

template <class T>

void AVLTree<T>::DoubleRotateRight (AVLTreeNode<T>* &p)

{

// два поддерева, подлежащих повороту

AVLTreeNode<T> *lc, *np;

// узел lc <= узел np < узел p

lc = p->Left(); // левый сын узла p

np = lc->Right(); // правый сын узла lc

// обновить показатели сбалансированности в узлах p, lc и np

if (np->balanceFactor == rightheavy)

{

p->balanceFactor = balanced;

lc->balanceFactor = rightheavy;

}

else

{

p->balanceFactor = rightheavy;

lc->balanceFactor = balanced;

}

np->balanceFactor = balanced;

// перед тем как заменить родительский узел p, следует отсоединить его от старых детей и присоединить к новым

lc->Right() = np->Left();

np->Left() = lc;

p->Left() = np->Right();

np->Right() = p;

p = np;

}

Двойной поворот иллюстрируется на дереве, изображенном на рисунке 17. Попытка вставить узел 25 разбалансирует корневой узел 50. В этом случае узел 20 (LC) приобретает слишком высокое правое поддерево и требуется двойной поворот.

Новым родительским узлом (NP) становится узел 40. Старый родительский узел становится его правым сыном и присоединяет к себе узел 45, который также переходит с левой стороны дерева.

Рис. 17.

Оценка сбалансированных АВЛ - деревьев.

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

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

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

Оценка производительности АВЛ – деревьев.

Эта программа сравнивает сбалансированное и обычное бинарные деревья поиска, каждое из которых содержит N случайных чисел. Исходные данные для этих деревьев берутся из единого массива. Для каждого элемента массива осуществляется его поиск в обоих деревьях. Длины поисковых путей суммируются, а затем подсчитывается средняя длина поиска по каждому дереву. Программа прогоняется на 1000- и на 10000-элементном массивах.

Обратите внимание, что на случайных данных поисковые характеристики АВЛ - дерева несколько лучше. В самом худшем случае вырожденное дерево поиска, содержащее 1000 элементов, имеет среднюю глубину 500, в то время как средняя глубина АВЛ - дерева всегда равна 9.

#include <iostream.h>

#include "bstree.h"

#include "avltree.h"

#include "random.h"

// загрузить из массива числа в бинарное поисковое дерево и АВЛ – дерево

void SetupLists(BinSTree<int> &Tree1, AVLTree<int> &Tree2, int A[], int n)

{

int i;

RandomNumber rnd;

// запомнить случайное число в массиве А, а также вставить его в бинарное дерево поиска и в АВЛ - дерево

for (i=0; i<n; i++)

{

A[i] = rnd.Random(1000);

Tree1.Insert(A[i]);

Tree2.Insert(A[i]);

}

// поиск элемента item в дереве t

// при этом накапливается суммарная длина поиска

template <class T>

void PathLength(TreeNode<T> *t, long &totallength, int item)

{

// возврат, если элемент найден или отсутствует в списке

if (t == NULL || t->data == item)

return;

else

{

// перейти на следующий уровень, увеличить суммарную длину пути поиска

totallength++;

if (item < t->data)

PathLength(t->Left(), totallength, item);

else

PathLength(t->Right(), totallength, item);

}

void main(void);

{

// переменные для деревьев и массива

BinSTree<int> binTree;

AVLTree<int> avlTree;

int *A;

// суммарные длины поисковых путей элементов массива в бинарном дереве поиска и в АВЛ - дереве

long totalLengthBintree = 0, totalLengthAVLTree = 0;

int n, i;

cout << "Сколько узлов на дереве? ";

cin >> n;

// загрузить случайными числами массив и оба дерева

SetupLists(binTree, avlTree, A, n);

for (i=0; i<n; i++)

{

PathLength(binTree.GetRoot(), totalLengthBintree, A[i]);

PathLength((TreeNode<int> *)avlTree.getRoot(),

totalLengthAVLTree, A[i]);

}

cout << "Средняя длина поиска для бинарного дерева = "

<< float(totalLengthBintree)/n << endl;

cout << "Средняя длина поиска для сбалансированного дерева = "

<< float(totalLengthAVLTree)/n << endl;

}

Прогон 1:Сколько узлов на дереве? 1000

Средняя длина поиска для бинарного дерева = 10.256.

Средняя длина поиска для сбалансированного дерева = 7.901.

Прогон 2:Сколько узлов на дереве? 10000

Средняя длина поиска для бинарного дерева = 12.2822.

Средняя длина поиска для сбалансированного дерева = 8.5632.

Итераторы АВЛ - деревьев.

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

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