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

Объявление:

// наследник класса TreeNode

 

template <class T>

class AVLTreeNode: public TreeNode<T>

{

 private:

 

 // дополнительный член класса balanceFactor используется методами класса AVLTree и позволяет избегать "перевешивания" узлов

 

 int balanceFactor;

 AVLTreeNode<T>* & Left(void);

 AVLTreeNode<T>* & Right(void);

 public:

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

 AVLTreeNode(const T& item, AVLTreeNode<T> *lptr = NULL,

 AVLTreeNode<T> *rptr = NULL, int balfac = 0);

 

 // возвратить левый/правый указатель узла типа TreeNode преобразовав его к типу AVLTreeNode

 AVLTreeNode<T> *Left(void) const;

 AVLTreeNode<T> *Right(void) const;

 

 // метод для доступа к новому полю данных

 int GetBalanceFactor(void);

 // методы класса AVLTree должны иметь доступ к Left и Right

 friend class AVLTree<T>;

};

Описание:

Элемент данных balanceFactor является скрытым, так как обновлять его должны только выравнивающие баланс операции вставки и удаления. Доступ к полям - указателям осуществляется с помощью методов Left и Right. Новые определения для этих методов обязательны, поскольку они возвращают указатель на структуру AVLTreeNode.

Поскольку класс AVLTree образован на базе класса BinSTree, будем использовать деструктор базового класса и метод ClearList. Эти методы удаляют узлы с помощью оператора delete. В каждом случае указатель ссылается на объект типа AVLTreeNode, а не TreeNode. Так как деструктор базового класса TreeNode виртуальный, при вызове delete используется динамическое связывание и удаляется объект типа AVLTreeNode.

Пример:

Эта функция создает АВЛ - дерево, изображенное на рисунке 4. Каждому узлу присваивается показатель сбалансированности.

 

Рис. 4.

 

AVLTreeNode<char> *root; // корень АВЛ - дерева

 

void MakeAVLCharTree(AVLTreeNode<char>* &root)

{

 AVLTreeNode<char> *a, *b, *c, *d, *e;

 e = new AVLTreeNode<char>('E', NULL, NULL, 0);

 d = new AVLTreeNode<char>('D', NULL, NULL, 0);

 c = new AVLTreeNode<char>('C', e, NULL, -1);

 b = new AVLTreeNode<char>('B', NULL, d, 1);

 a = new AVLTreeNode<char>('A', b, c, 0);

 root = a;

}

 

Реализация класса AVLTreeNode.

Конструктор класса AVLTreeNode вызывает конструктор базового класса и инициализирует balanceFactor.

 

// Конструктор инициализирует balanceFactor и базовый класс

// Начальные значения полей указателей по умолчанию, равные NULL

// инициализируют узел как лист

 

template <class T>

 

AVLTreeNode<T>::AVLTreeNode (const T& item,

 AVLTreeNode<T> *lptr, AVLTreeNode<T> *rptr, int balfac):

 TreeNode<T>(item, lptr, rptr), balanceFactor(balfac)

{}

 

Методы Left и Right в классе AVLTreeNode упрощают доступ к полям данных. При попытке обратиться к левому сыну с помощью метода Left базового класса возвращается указатель на объект типа TreeNode. Чтобы получить указатель на узел АВЛ - дерева, требуется преобразование типов.

Например:

AVLTreeNode<T> *p, *q;

q = p->Left(); // недопустимая операция

q = (AVLTreeNode<T> *)p->Left(); // необходимое приведение типа

Во избежание постоянного преобразования типа указателей мы определяем методы Left и Right для класса AVLTreeNode, возвращающие указатели на объекты типа AVLTreeNode.

 

template <class T>.

AVLTreeNode<T>* AVLTreeNode::Left(void)

{

 return ((AVLTreeNode<T> *)left;

}

Класс AVLTree.

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

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