Курсовая работа: Реализация АВЛ–деревьев через классы объектно–ориентированного программирования

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); // создать дерево В