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

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

= 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. rsdn/article/alg/bintree/avl.xml.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: