Реализация АВЛ–деревьев через классы объектно–ориентированного программирования
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. rsdn/article/alg/bintree/avl.xml.