48754 (608770), страница 2
Текст из файла (страница 2)
В АВЛ - дереве показатель сбалансированности должен быть в диапазоне [-1, 1]. На рисунке 3 изображены АВЛ - деревья с пометками -1, 0 и +1 на каждом узле, показывающими относительный размер левого и правого поддеревьев.
-1: Высота левого поддерева на 1 больше высоты правого поддерева.
0: Высоты обоих поддеревьев одинаковы.
+1: Высота правого поддерева на 1 больше высоты левого поддерева.
Рис. 1.
Рис. 2.
Используя свойства наследования, можно образовать класс AVLTreeNode на базе класса TreeNode. Объект типа AVLTreeNode наследует поля из класса TreeNode и добавляет к ним поле balanceFactor. Данные - члены left и right класса TreeNode являются защищенными, поэтому AVLTreeNode или другие производные классы имеют к ним доступ.
Рис. 3.
Спецификация класса AVLTreeNode.
Объявление:
// наследник класса TreeNode
template
class AVLTreeNode: public TreeNode
{
private:
// дополнительный член класса balanceFactor используется методами класса AVLTree и позволяет избегать "перевешивания" узлов
int balanceFactor;
AVLTreeNode* & Left(void);
AVLTreeNode* & Right(void);
public:
// конструктор
AVLTreeNode(const T& item, AVLTreeNode *lptr = NULL,
AVLTreeNode *rptr = NULL, int balfac = 0);
// возвратить левый/правый указатель узла типа TreeNode преобразовав его к типу AVLTreeNode
AVLTreeNode *Left(void) const;
AVLTreeNode *Right(void) const;
// метод для доступа к новому полю данных
int GetBalanceFactor(void);
// методы класса AVLTree должны иметь доступ к Left и Right
friend class AVLTree;
};
Описание:
Элемент данных balanceFactor является скрытым, так как обновлять его должны только выравнивающие баланс операции вставки и удаления. Доступ к полям - указателям осуществляется с помощью методов Left и Right. Новые определения для этих методов обязательны, поскольку они возвращают указатель на структуру AVLTreeNode.
Поскольку класс AVLTree образован на базе класса BinSTree, будем использовать деструктор базового класса и метод ClearList. Эти методы удаляют узлы с помощью оператора delete. В каждом случае указатель ссылается на объект типа AVLTreeNode, а не TreeNode. Так как деструктор базового класса TreeNode виртуальный, при вызове delete используется динамическое связывание и удаляется объект типа AVLTreeNode.
Пример:
Эта функция создает АВЛ - дерево, изображенное на рисунке 4. Каждому узлу присваивается показатель сбалансированности.
Рис. 4.
AVLTreeNode
void MakeAVLCharTree(AVLTreeNode* &root)
{
AVLTreeNode *a, *b, *c, *d, *e;
e = new AVLTreeNode('E', NULL, NULL, 0);
d = new AVLTreeNode('D', NULL, NULL, 0);
c = new AVLTreeNode('C', e, NULL, -1);
b = new AVLTreeNode('B', NULL, d, 1);
a = new AVLTreeNode('A', b, c, 0);
root = a;
}
Реализация класса AVLTreeNode.
Конструктор класса AVLTreeNode вызывает конструктор базового класса и инициализирует balanceFactor.
// Конструктор инициализирует balanceFactor и базовый класс
// Начальные значения полей указателей по умолчанию, равные NULL
// инициализируют узел как лист
template
AVLTreeNode::AVLTreeNode (const T& item,
AVLTreeNode *lptr, AVLTreeNode *rptr, int balfac):
TreeNode(item, lptr, rptr), balanceFactor(balfac)
{}
Методы Left и Right в классе AVLTreeNode упрощают доступ к полям данных. При попытке обратиться к левому сыну с помощью метода Left базового класса возвращается указатель на объект типа TreeNode. Чтобы получить указатель на узел АВЛ - дерева, требуется преобразование типов.
Например:
AVLTreeNode *p, *q;
q = p->Left(); // недопустимая операция
q = (AVLTreeNode *)p->Left(); // необходимое приведение типа
Во избежание постоянного преобразования типа указателей мы определяем методы Left и Right для класса AVLTreeNode, возвращающие указатели на объекты типа AVLTreeNode.
template .
AVLTreeNode* AVLTreeNode::Left(void)
{
return ((AVLTreeNode *)left;
}
Класс AVLTree.
АВЛ - дерево представляет собой списковую структуру, похожую на бинарное дерево поиска, с одним дополнительным условием: дерево должно оставаться сбалансированным по высоте после каждой операции вставки или удаления. Поскольку АВЛ - дерево является расширенным бинарным деревом поиска, класс AVLTree строится на базе класса BinSTree и является его наследником.
Для выполнения АВЛ - условий следует изменить методы Insert и Delete. Кроме того, в производном классе определяются конструктор копирования и перегруженный оператор присвоения, так как мы строим дерево с большей узловой структурой.
Спецификация класса AVLTree.
Объявление:
// Значения показателя сбалансированности узла
const int leftheavy = - 1;
const int balanced = 0;
const int rightheavy = 1;
template
class AVLTree: public BinSTree
{
private:
// выделение памяти
AVLTreeNode *GetAVLTreeNode(const T& item,
AVLTreeNode *lptr, AVLTreeNode *rptr);
// используется конструктором копирования и оператором присваивания
AVLTreeNode *CopyTree(AVLTreeNode *t);
// используется методами Insert и Delete для восстановления АВЛ - условий после операций вставки/удаления
void SingleRotateLeft (AVLTreeNode* &p);
void SingleRotateRight (AVLTreeNode* &p);
void DoubleRotateLeft (AVLTreeNode* &p);
void DoubleRotateRight (AVLTreeNode* &p);
void UpdateLeftTree (AVLTreeNode* &tree,
int &reviseBalanceFactor);
void UpdateRightTree (AVLTreeNode* &tree,
int &reviseBalanceFactor);
// специальные версии методов Insert и Delete
void AVLInsert(AVLTreeNode* &tree,
AVLTreeNode* newNode, int &reviseBalanceFactor);
void AVLDelete(AVLTreeNode* &tree,
AVLTreeNode* newNode, int &reviseBalanceFactor);
public:
// конструкторы
AVLTree(void);
AVLTree(const AVLTree& tree);
// оператор присваивания
AVLTree& operator= (const AVLTree& tree);
// стандартные методы обработки списков
virtual void Insert(const T& item);
virtual void Delete(const T& item);
};
Описание:
Константы leftheavy, balanced и rightheavy используются в операциях вставки/удаления для описания показателя сбалансированности узла. Метод GetAVLTreeNode управляет выделением памяти для экземпляра класса. По умолчанию balanceFactor нового узла равен нулю.
Рис. 5.
В этом классе заново определяется функция CopyTree для использования с конструктором копирования и перегруженным оператором присвоения. Несмотря на то, что алгоритм идентичен алгоритму для функции CopyTree класса BinSTree, новая версия корректно создает расширенные объекты типа AVLTreeNode при построении нового дерева.
Функции AVLInsert и AVLDelete реализуют методы Insert и Delete, соответственно. Они используют скрытые методы наподобие SingleRotateLeft. Открытые методы Insert и Delete объявлены виртуальными и подменяют соответствующие функции базового класса. Остальные операции наследуются от класса BinSTree.
Пример:
Код, приведенный ниже, создает деревья, приведенные на рисунке 5. После удаления из АВЛ - дерева (В) элемента 3 АВЛ - дерево принимает вид, изображенный на рисунке 5 (С). Цифра после двоеточия означает фактор сбалансированности.
AVLTree
BinSTree bintree; // BinSTree - список целых чисел
for (int i=1; i<=5; i++)
{
bintree.Insert(i); // создать дерево А
avltree.Insert(i); // создать дерево В
}
avltree.Delete(3); // удалить 3 из АВЛ - дерева
// дерево (С) есть дерево (В) без удаленного узла 3.
Распределение памяти для AVLTree.
Класс AVLTree образован от класса BinSTree и наследует большинство его операций. Для создания расширенных объектов типа AVLTreeNode мы разработали отдельные методы выделения памяти и копирования.
// разместить в памяти объект типа AVLTreeNode, прервать программу если во время выделения памяти произошла ошибка
template
AVLTreeNode *AVLTree::GetAVLTreeNode(const T& item,
AVLTreeNode *lptr, AVLTreeNode *rptr)
{
AVLTreeNode *p;
p = new AVLTreeNode (item, lptr, rptr);
if (p == NULL)
{
cerr << "Ошибка выделения памяти!" << endl;
exit(1);
}
return p;
}
Для удаления узлов АВЛ - дерева достаточно методов базового класса. Метод DeleteTree из класса BinSTree задействует виртуальный деструктор класса TreeNode.
Метод Insert класса AVLTree.
Преимущество АВЛ - деревьев состоит в их сбалансированности, которая поддерживается соответствующими алгоритмами вставки/удаления. Опишем метод Insert для класса AVLTree. При реализации метода Insert для запоминания элемента используется рекурсивная функция AVLInsert. Сначала приведем код метода Insert на С++, а затем сосредоточим внимание на рекурсивном методе AVLInsert, реализующем алгоритм Адельсона - Вельского и Ландиса.
template
void AVLTree::Insert(const T& item)
{
// объявить указатель АВЛ - дерева, используя метод базового класса GetRoot
// произвести приведение типов для указателей
AVLTreeNode
*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
void AVLTree::AVLInsert(AVLTreeNode* &tree,
AVLTreeNode* newNode, int &reviseBalanceFactor)
{
// флаг "Показатель сбалансированности был изменен"
int rebalanceCurrNode;
// встретилось пустое поддерево, пора вставлять новый узел
if (tree == NULL)
{
// вставить новый узел
tree = newNode;
// объявить новый узел сбалансированным
tree->balanceFactor = balanced;
// сообщить об изменении показателя сбалансированности
reviseBalanceFactor = 1;
}
// рекурсивно спускаться по левому поддереву, если новый узел меньше текущего
else if (newNode->data 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 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;
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
