Распределение памяти для AVLTree. 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Распределение памяти для AVLTree.



Класс AVLTree образован от класса BinSTree и наследует большинство его операций. Для создания расширенных объектов типа AVLTreeNode мы разработали отдельные методы выделения памяти и копирования.

 

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

 

template <class T>

 

AVLTreeNode<T> *AVLTree<T>::GetAVLTreeNode(const T& item,

 AVLTreeNode<T> *lptr, AVLTreeNode<T> *rptr)

{

 AVLTreeNode<T> *p;

 

 p = new AVLTreeNode<T> (item, lptr, rptr);

 if (p == NULL)

 {

 cerr << "Ошибка выделения памяти!" << endl;

 exit(1);

 }

 

 return p;

}

 

Для удаления узлов АВЛ - дерева достаточно методов базового класса. Метод DeleteTree из класса BinSTree задействует виртуальный деструктор класса TreeNode.


Метод Insert класса AVLTree.

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

 

template <class T>

 

void AVLTree<T>::Insert(const T& item)

{

 // объявить указатель АВЛ - дерева, используя метод базового класса GetRoot

 

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

 AVLTreeNode<T> *treeRoot = (AVLTreeNode<T> *)GetRoot(),

 *newNode;

 

 // флаг, используемый функцией AVLInsert для перебалансировки узлов

 int reviseBalanceFactor = 0;

 

 // создать новый узел АВЛ - дерева с нулевыми полями указателей

 newNode = GetAVLTreeNode(item, NULL, NULL);

 

 // вызвать рекурсивную процедуру для фактической вставки элемента

 AVLInsert(treeRoot, newNode, reviseBalancefactor);

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

 root = treeRoot;

 current = newNode;

 size++;

}

 

Ядром алгоритма вставки является рекурсивный метод AVLInsert. Как и его аналог в классе BinSTree, этот метод осуществляет прохождение левого поддерева, если item меньше данного узла, и правого поддерева, если item больше или равен данному узлу. При сканировании левого или правого поддерева некоторого узла анализируется флаг revisebalanceFactor, который является признаком изменения любого параметра balanceFactor в поддереве. Если он установлен, то нужно проверить, сохранилась ли АВЛ - сбалансированность всего дерева.

Если в результате вставки нового узла она оказалась нарушенной, то мы обязаны восстановить равновесие.

Алгоритм АВЛ – вставки

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

Случай 1. Узел на поисковом маршруте изначально является сбалансированным (balanceFactor = 0). После вставки в поддерево нового элемента узел стал перевешивать влево или вправо в зависимости от того, в какое поддерево была произведена вставка.

Если элемент вставлен в левое поддерево, показателю сбалансированности присваивается -1, а если в правое, то 1. Например, на пути 40 - 50 - 60 каждый узел сбалансирован. После вставки узла 55 показатели сбалансированности изменяются (рис. 6).

 

Рис. 6.

Случай 2. Одно из поддеревьев узла перевешивает, и новый узел вставляется в более легкое поддерево. Узел становится сбалансированным. Сравните, например, состояния дерева до и после вставки узла 55 (рис. 7).

Случай 3. Одно из поддеревьев узла перевешивает, и новый узел помещается в более тяжелое поддерево. Тем самым нарушается условие сбалансированности, так как balanceFactor выходит за пределы -1..1. Чтобы восстановить равновесие, нужно выполнить поворот.

 


Рис. 7.

Рассмотрим пример:

Предположим, что дерево разбалансировалось слева и мы восстанавливаем равновесие, вызывая одну из функций поворота вправо. Разбалансировка справа влечет за собой симметричные действия. Сказанное иллюстрируется рисунком 8.

Метод AVLInsert.

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

 

template <class T>

 

void AVLTree<T>::AVLInsert(AVLTreeNode<T>* &tree,

 AVLTreeNode<T>* newNode, int &reviseBalanceFactor)

{

 // флаг "Показатель сбалансированности был изменен"

 int rebalanceCurrNode;

 

 // встретилось пустое поддерево, пора вставлять новый узел

 if (tree == NULL)

 {

 // вставить новый узел

 tree = newNode;

 

 // объявить новый узел сбалансированным

 tree->balanceFactor = balanced;

 

 // сообщить об изменении показателя сбалансированности

 reviseBalanceFactor = 1;

 }

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

 else if (newNode->data < tree->data)

 {

 AVLInsert(tree->Left(), newNode, rebalanceCurrNode);

 

 // проверить, нужно ли корректировать balanceFactor

 if (rebalanceCurrNode)

 {

 // вставка слева от узла, перевешивающего влево. будет нарушено

 // условие сбалансированности; выполнить поворот (случай 3)

 if (tree->balanceFactor == leftheavy)

 UpdateLeftTree(tree, reviseBalanceFactor);

 

 // вставка слева от сбалансированного узла.

 // узел станет перевешивать влево (случай 1)

 else if (tree->balanceFactor == balanced)

 {

 tree->balanceFactor = leftheavy;

 reviseBalanceFactor = 1;

 }

 

 // вставка слева от узла, перевешивающего вправо

 // узел станет сбалансированным (случай 2)

 else

 {

 tree->balanceFactor = balanced;

 reviseBalanceFactor = 0;

 }

 }

 Else

 

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

 reviseBalanceFactor = 0;

 }

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

 else if (newNode->data < tree->data)

 {

 AVLInsert(tree->Right(), newNode, rebalanceCurrNode);

 // проверить, нужно ли корректировать balanceFactor

 if (rebalanceCurrNode)

 {

 // вставка справа от узла, перевешивающего вправо. будет нарушено

 // условие сбалансированности; выполнить поворот (случай 3)

 if (tree->balanceFactor == rightheavy)

 UpdateRightTree(tree, reviseBalanceFactor);

 

 // вставка справа от сбалансированного узла

 // узел станет перевешивать вправо (случай 1)

 else if (tree->balanceFactor == balanced)

 {

 tree->balanceFactor = rightheavy;

 reviseBalanceFactor = 1;

 }

 // вставка справа от узла, перевешивающего влево

 // узел станет сбалансированным (случай 2)

 else

 {

 tree->balanceFactor = balanced;

 reviseBalanceFactor = 0;

 }

 }

 else

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

 reviseBalanceFactor = 0;

 }

 


Рис. 8.

 

Метод AVLInsert распознает случай 3, когда нарушается АВЛ - условие. Для выполнения перебалансировки используются методы UpdateLeftTree и UpdateRightTree. Они выполняют одинарный или двойной поворот для уравновешивания узла, а затем сбрасывают флаг reviseBalanceFactor. Перед тем, как обсудить специфические детали поворотов, приведем код функции UpdateLeftTree.

 

template <class T>

void AVLTree<T>::UpdateLeftTree(AVLTreeNode<T>* &p,

 int reviseBalanceFactor)

{

 AVLTreeNode<T> *lc;

 

 lc = p->Left();

 // перевешивает левое поддерево?

 if (lc->balanceFactor == leftheavy)

 {

 SingleRotateRight(p); // однократный поворот

 reviseBalanceFactor = 0;

 }

 // перевешивает правое поддерево?

 else if (lc->balanceFactor == rightheavy)

 {

 // выполнить двойной поворот

 DoubleRotateRight(p);

 // теперь корень уравновешен

 reviseBalanceFactor = 0;

}

 



Поделиться:


Последнее изменение этой страницы: 2020-03-14; просмотров: 118; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.210.85.205 (0.018 с.)