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

 

Программа создана на объектно – ориентированном языке программирования 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.