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

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

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

Распределение памяти для 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;