Спецификация класса AVLTree.

Объявление:

// Значения показателя сбалансированности узла

 

const int leftheavy = - 1;

const int balanced = 0;

const int rightheavy = 1;

 

template <class T>

 

class AVLTree: public BinSTree<T>

{

 private:

 

 // выделение памяти

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

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

 

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

 AVLTreeNode<T> *CopyTree(AVLTreeNode<T> *t);

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

 void SingleRotateLeft (AVLTreeNode<T>* &p);

 void SingleRotateRight (AVLTreeNode<T>* &p);

 void DoubleRotateLeft (AVLTreeNode<T>* &p);

 void DoubleRotateRight (AVLTreeNode<T>* &p);

 void UpdateLeftTree (AVLTreeNode<T>* &tree,

 int &reviseBalanceFactor);

 void UpdateRightTree (AVLTreeNode<T>* &tree,

 int &reviseBalanceFactor);

 // специальные версии методов Insert и Delete

 void AVLInsert(AVLTreeNode<T>* &tree,

 AVLTreeNode<T>* newNode, int &reviseBalanceFactor);

 void AVLDelete(AVLTreeNode<T>* &tree,

 AVLTreeNode<T>* newNode, int &reviseBalanceFactor);

 

 public:

// конструкторы

 AVLTree(void);

 AVLTree(const AVLTree<T>& tree);

 

 // оператор присваивания

 AVLTree<T>& operator= (const AVLTree<T>& 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<int> avltree; // AVLTree - список целых чисел

BinSTree<int> bintree; // BinSTree - список целых чисел

 

for (int i=1; i<=5; i++)

{

 

 bintree.Insert(i); // создать дерево А

 avltree.Insert(i); // создать дерево В

}

avltree.Delete(3); // удалить 3 из АВЛ - дерева

// дерево (С) есть дерево (В) без удаленного узла 3.