Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ:  Археология Биология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия ЭкологияТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву 
Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Алгоритм реализации АВЛ – деревьев через классы объектно – ориентированного программирования.Содержание книги
Поиск на нашем сайте
Программа создана на объектно – ориентированном языке программирования 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.
|
||
|
|
Последнее изменение этой страницы: 2020-03-14; просмотров: 179; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 216.73.216.236 (0.007 с.) |
