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

if (current->Right() != NULL)

current = GoFarLeft(current->Right());

// правого поддерева нет, но в стеке есть другие узлы, подлежащие обработке.

// Вытолкнуть из стека новый текущий адрес, продвинуться вверх по дереву

else if (!S.StackEmpty())

current = S.Pop();

// нет ни правого поддерева, ни узлов в стеке. Сканирование завершено

else

iterationComplete = 1;

}

Алгоритм TreeSort.

Когда объект типа InorderIterator осуществляет прохождение дерева поиска, узлы проходятся в сортированном порядке и, следовательно, можно построить еще один алгоритм сортировки, называемый TreeSort. Этот алгоритм предполагает, что элементы изначально хранятся в массиве. Поисковое дерево служит фильтром, куда элементы массива копируются в соответствии с алгоритмом вставки в бинарное дерево поиска. Осуществляя симметричное прохождение этого дерева и записывая элементы снова в массив, мы получаем в результате отсортированный список. На рисунке 20 показана сортировка 8 - элементного массива.

#include "bstree.h"

#include "treeiter.h"

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

template <class T>

void TreeSort(T arr[], int n)

{

// бинарное дерево поиска, в которое копируется массив

BinSTree<T> sortTree;

int i;

// вставить каждый элемент массива в поисковое дерево

for (i=0; i<n; i++)

sortTree.Insert(arr[i]);

// объявить итератор симметричного прохождения для sortTree

InorderIterator<T> treeSortIter(sortTree.GetRoot());

// выполнить симметричное прохождение дерева

// скопировать каждый элемент снова в массив

i = 0;

while (!treeSortIter.EndOfList())

{

arr[i++] = treeSortIter.Data();

treeSortIter.Next();

}

}

Рис. 20.

3. Алгоритм реализации АВЛ - деревьев через классы объектно - ориентированного программирования.

Программа создана на объектно - ориентированном языке программирования C++ в среде быстрой разработки (RAD) Bolrand C++ Builder 6.0, имеет графический интерфейс.

Текст программы.

#pragma once

template <typename KEY,typename VALUE> class AvlTree

{

public:

KEY key;

VALUE value;

int balance;

AvlTree<KEY, VALUE>* left;

AvlTree<KEY, VALUE>* right;

bool empty;//заполнены ключ и значение или нет

AvlTree()

{

empty=true;

left = NULL;

right = NULL;

balance = 0;

}

AvlTree(KEY Key,VALUE Value)

{

empty=false;

key = Key;

value = Value;

left = NULL;

right = NULL;

balance = 0;

}

int add(KEY Key, VALUE Value)//добавление узла, возвращает изменился баланс(1) или нет (0)

{ //при добавлении в правую ветку баланс узла увеличиваю на результат добавления

if (empty) //в левую уменьшаю

{ //после каждого вызова add(...) вызываю TurnAround();

key = Key; //дерево перестраивается пока потомок текущего узла в нужном направлении не будет NULL

value = Value; //потом в этого потомка записываем новые значения

empty=false;

return 0;

}

if (Key == key)

throw CString(L"Уже есть");

int a = balance;

if (Key > key)

{

if (right != NULL)

{

balance += right->add(Key, Value);

TurnAround();

}

else

{

right = new AvlTree<KEY, VALUE>(Key, Value);

balance++;

}

}

else

{

if (left != NULL)

{

balance -= left->add(Key, Value);

TurnAround();

}

else

{

left = new AvlTree<KEY, VALUE>(Key, Value);

balance--;

}

}

if (balance != a)

{

return 1;

}

else

{

return 0;

}

}

void TurnAround() //нормализация дерева, если баланс не равномерный смещаю(поворачиваю) узел так,

{ //чтобы количество потомков справа и слева не отличалось больше , чем на 1

if (balance == 2)

{

if (right->balance >= 0)

{

KEY tKey = key;

VALUE tValue = value;

key = right->key;

value = right->value;

right->key = tKey;

right->value = tValue;

AvlTree<KEY, VALUE>*tNode=right->right;

right->right = right->left;

right->left = left;

left = right;

right = tNode;

balance = left->balance - 1;

left->balance = 1 - left->balance;

}

else

{

KEY tKey = key;

VALUE tValue = value;

key = right->left->key;

value = right->left->value;

right->left->key = tKey;

right->left->value = tValue;

AvlTree<KEY, VALUE>* tNode = right->left->right;

right->left->right = right->left->left;

right->left->left = left;

left = right->left;

right->left = tNode;

balance = 0;

right->balance = (left->balance == -1) ? (1) : (0);

left->balance = (left->balance == 1) ? (-1) : (0);

}

}

else

{

if (balance == -2)

{

if (left->balance <= 0)

{

KEY tKey = key;

VALUE tValue = value;

key = left->key;

value = left->value;

left->key = tKey;

left->value = tValue;

AvlTree<KEY, VALUE>* tNode = left->left;

left->left = left->right;

left->right = right;

right = left;

left = tNode;

balance = 1 + right->balance;

right->balance = -1 - right->balance;

}

else

{

KEY tKey = key;

VALUE tValue = value;

key = left->right->key;

value = left->right->value;

left->right->key = tKey;

left->right->value = tValue;

AvlTree<KEY, VALUE>* tNode = left->right->left;

left->right->left = left->right->right;

left->right->right = right;

right = left->right;

left->right = tNode;

balance = 0;

left->balance = (right->balance == 1) ? (-1) : (0);

right->balance = (right->balance == -1) ? (1) : (0);

}

}

}

}

typename AvlTree<KEY, VALUE>* getNode(KEY Key)//поиск узла по ключу

{

AvlTree<KEY, VALUE>* node=this;

while (true)

{

if (node == NULL)

throw CString(L"Не найдено");

if (node->key == Key)

return node;

if (node->key < Key)

{

node = node->right;

}

else

{

node = node->left;

}

}

}

int remove(KEY Key,AvlTree<KEY, VALUE>*parent=NULL) //удаление узла, перемещаюсь по дереву, по ключу

{ //при прохождении узла опять меняю баланс в зависимости от направления и поворачиваю его TurnAround()

int a = balance; // как дошел до нужного узла перемещаю его , пока оба его потомка не будут NULL

if (key == Key) // и удаляю

{

if (right == NULL && left == NULL)

{

if(parent->left->key==this->key)

{

parent->left=NULL;

}

else

{

parent->right=NULL;

}

return 1;

}

else

{

if (balance >= 0)

{

if (right != NULL)

{

AvlTree<KEY, VALUE>* tNode = right;

while (tNode->left != NULL)

{

tNode = tNode->left;

}

KEY tKey = key;

VALUE tValue = value;

key = tNode->key;

value = tNode->value;

tNode->key = tKey;

tNode->value = tValue;

balance -= right->remove(Key,this);

}

}

else

{

if (left != NULL)

{

AvlTree<KEY, VALUE>* tNode = left;

while (tNode->right != NULL)

{

tNode = tNode->right;

}

KEY tKey = key;

VALUE tValue = value;

key = tNode->key;

value = tNode->value;

tNode->key = tKey;

tNode->value = tValue;

balance += left->remove(Key,this);

}

}

}

}

else

{

if (Key > key)

{

if (right!=NULL)

{

balance -= right->remove(Key,this);

TurnAround();

}

else

{

throw CString("Не найдено");

}

}

else

{

if (left!=NULL)

{

balance += left->remove(Key,this);

TurnAround();

}

else

{

throw CString("Не найдено");

}

}

}

if (balance != a)

{

return (balance == 0) ? (1) : (0);

}

else

{

return 0;

}

}

~AvlTree()

{

}

};

СПИСОК ЛИТЕРАТУРЫ

1. Каррано Ф.М., Причард Дж.Дж. К26 Абстракция данных и решение задач на С++ - I -. Стены и зеркала, 3-е издание.: Пер.с англ. - М.: Издательский дом «Вильяме», 2003. - 848 с: ил. - Парал. тит. англ.

2. Ж.-Л. Лорьер. Системы искусственного интеллекта. - М.: Мир, 1991.

3. Бабэ Б. Просто и ясно о Borland С++: пер. с англ. - СПб.: Питер, 1997. - 464 с.

4. Ирэ П. Объектно - ориентированное программирование с использованием С++: пер. с англ. К.: НИПФ ДиаСофтЛтд, 1995. - 480 с.

5. Программирование. Учебник под ред. Свердлика А.Н., МО СССР, 1992. - 608 с.

6. Сван Т. Программирование для Windows в Borland С++: пер. с англ. - М.: БИНОМ. - 480 с.

7. Шамис В.А. Borland С++ Builder. Программирование на С++ без проблем. - М.: Нолидж, 1997. - 266 с.

8. Шилдт Г. Теория и практика С++: пер. с англ. - СПб.: BHV - Санкт - Петербург, 1996. - 416 с.

9. http://www.rsdn.ru/article/alg/bintree/avl.xml.