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

2016-07-30СтудИзба

Описание файла

Документ из архива "Реализация АВЛ–деревьев через классы объектно–ориентированного программирования", который расположен в категории "". Всё это находится в предмете "информатика" из 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;

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

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5076
Авторов
на СтудИзбе
455
Средний доход
с одного платного файла
Обучение Подробнее