48754 (Реализация АВЛ–деревьев через классы объектно–ориентированного программирования), страница 3
Описание файла
Документ из архива "Реализация АВЛ–деревьев через классы объектно–ориентированного программирования", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "48754"
Текст 3 страницы из документа "48754"
}
// вставка справа от узла, перевешивающего влево
// узел станет сбалансированным (случай 2)
else
{
tree->balanceFactor = balanced;
reviseBalanceFactor = 0;
}
}
else
// перебалансировка не требуется. не опрашивать предыдущие узлы
reviseBalanceFactor = 0;
}
Рис. 8.
Метод AVLInsert распознает случай 3, когда нарушается АВЛ - условие. Для выполнения перебалансировки используются методы UpdateLeftTree и UpdateRightTree. Они выполняют одинарный или двойной поворот для уравновешивания узла, а затем сбрасывают флаг reviseBalanceFactor. Перед тем, как обсудить специфические детали поворотов, приведем код функции UpdateLeftTree.
template
void AVLTree::UpdateLeftTree(AVLTreeNode* &p,
int reviseBalanceFactor)
{
AVLTreeNode *lc;
lc = p->Left();
// перевешивает левое поддерево?
if (lc->balanceFactor == leftheavy)
{
SingleRotateRight(p); // однократный поворот
reviseBalanceFactor = 0;
}
// перевешивает правое поддерево?
else if (lc->balanceFactor == rightheavy)
{
// выполнить двойной поворот
DoubleRotateRight(p);
// теперь корень уравновешен
reviseBalanceFactor = 0;
}
Вращения (Повороты) АВЛ - деревьев.
При операциях добавления и удаления может произойти нарушение сбалансированности дерева. В этом случае потребуются некоторые преобразования, не нарушающие упорядоченности дерева и способствующие лучшей сбалансированности.
Рассмотрим такие преобразования.
В каждой вершине дерева помимо значения элемента будем хранить показатель сбалансированности в данной вершине. Показатель сбалансированности - разница между высотами правого и левого поддеревьев.
PTree = ^TTree;
TTree = record
Item: T; {элемент дерева}
Left, Right: PTree; {указатели на поддеревья}
Balance: ShortInt; {показатель сбалансированности}
end;
В сбалансированном дереве показатели сбалансированности всех вершин лежат в пределах от -1 до 1. При операциях добавления/удаления могут появляться вершины с показателями сбалансированности -2 и 2.
Малое левое вращение.
Пусть показатель сбалансированности вершины, в которой произошло нарушение баланса, равен -2, а показатель сбалансированности корня левого поддерева равен -1. Тогда восстановить сбалансированность такого поддерева можно следующим преобразованием, называемым малым левым вращением (рис. 9.):
Рис. 9.
На приведенном рисунке прямоугольниками обозначены поддеревья. Рядом с поддеревьями указана их высота. Поддеревья помечены арабскими цифрами. Кружочками обозначены вершины. Цифра рядом с вершиной - показатель сбалансированности в данной вершине. Буква внутри кружка - условное обозначение вершины. Как видно из рисунка после малого левого вращения показатель сбалансированности вершины, в которой было нарушение баланса, становится равным нулю.
Малое правое вращение.
В случае, когда показатель сбалансированности вершины, в которой произошло нарушение баланса, равен 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
void AVLTree::SingleRotateRight (AVLTreeNode* &p)
{
// левое, перевешивающее поддерево узла p
AVLTreeNode *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
void AVLTree::DoubleRotateRight (AVLTreeNode* &p)
{
// два поддерева, подлежащих повороту
AVLTreeNode *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
#include "bstree.h"
#include "avltree.h"
#include "random.h"
// загрузить из массива числа в бинарное поисковое дерево и АВЛ – дерево
void SetupLists(BinSTree &Tree1, AVLTree &Tree2, int A[], int n)
{
int i;
RandomNumber rnd;
// запомнить случайное число в массиве А, а также вставить его в бинарное дерево поиска и в АВЛ - дерево
for (i=0; i { A[i] = rnd.Random(1000); Tree1.Insert(A[i]); Tree2.Insert(A[i]); } // поиск элемента item в дереве t // при этом накапливается суммарная длина поиска template void PathLength(TreeNode *t, long &totallength, int item) { // возврат, если элемент найден или отсутствует в списке if (t == NULL || t->data == item) return; else { // перейти на следующий уровень, увеличить суммарную длину пути поиска totallength++; if (item data) PathLength(t->Left(), totallength, item); else PathLength(t->Right(), totallength, item); } void main(void); { // переменные для деревьев и массива BinSTree binTree; AVLTree avlTree; int *A; // суммарные длины поисковых путей элементов массива в бинарном дереве поиска и в АВЛ - дереве long totalLengthBintree = 0, totalLengthAVLTree = 0; int n, i; cout << "Сколько узлов на дереве? "; cin >> n; // загрузить случайными числами массив и оба дерева