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

Класс AVLTree.

АВЛ - дерево представляет собой списковую структуру, похожую на бинарное дерево поиска, с одним дополнительным условием: дерево должно оставаться сбалансированным по высоте после каждой операции вставки или удаления. Поскольку АВЛ - дерево является расширенным бинарным деревом поиска, класс AVLTree строится на базе класса BinSTree и является его наследником.

Для выполнения АВЛ - условий следует изменить методы Insert и Delete. Кроме того, в производном классе определяются конструктор копирования и перегруженный оператор присвоения, так как мы строим дерево с большей узловой структурой.

Спецификация класса 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);