Сбалансированное двоичное дерево поиска - C++ - Ответ 1107673

#include <iostream> 
#include <cassert> 
using namespace std; 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Файл avl.h. 
// Шаблон класса avl_tree. Реализует двоичное дерево поиска с 
// балансировкой по высоте. Локальная балансировка выполняется add(T) и 
// remove(T), поддерживая сбалансированность. Повторения недопустимы. 
// Тип T должен поддерживать копирование и следующие операции: 
//
//      operator=( ); 
//      operator<<( ); 
//      operator==( ); 
//      operator!=( ); 
//      operator<( ); 
//
//  Открытые функции-элементы: 
//      Avl_tree ( ) ;                                                      Создать пустое дерево. 
//      Avl_tree(T root_val );                                      Создать дерево с одним эл-том. 
//      ~Avl_tree( );                                                       Освободить память всех узлов. 
//      bool add( T insert_value );                                     Добавить элемент. 
//      void remove( T value );                                         Удалить элемент. 
//      T get_nth(const int element_num) const;                 Значение n-ro эл-та 
//
//
//      int size( ) const;                                              Число элементов. 
//      bool find( T find_value );                                      True если find_value  
//                                                                              имеется в дереве.
//
//      void print ( int level = 0 ) const;                             Напечатать "на боку". 
//
//      void print_pre_order( ) const;                          Напечатать как список. 
//      void print_in_order( ) const;                               Напечатать как список.
//      void print_post_order( ) const;                             Напечатать как список. 
//
//  Замечания по реализации: 
//      Узлы имеют поле nodecount для упрощения реализации 
//      get_nth. Имеются также связки с родительским узлом. 
//      Рекурсивные функции отмечаются особо. 
//
//
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
 
template <class T> 
class Avl_tree { 
 
private: 
 
    struct Tree_node { 
 
        friend class Avl_tree; 
        
        T val;                                  // Данные, хранящиеся в узле. 
        Tree_node *left_child; 
        Tree_node *right_child; 
        Tree_node *parent; 
        int bal;                                // Фактор баланса = 
                                                    // (высота правого поддерева) 
                                                    // - (высота левого поддерева) 
        int nodecount;                  // Число уэлов поддерева с корнем 
                                                    // в данном узле, включая его 
                                                    // самого. 
        Tree_node ( ) ; 
        Tree_node( const T node_val ) : val(node_val) { } 
        ~Tree_node( ) { } 
 
        // Isa_right_child( ) и isa_left_child( ) возврашают true, если 
        // вызывающий узел является правым/левым потомком родительского 
        // узла, и false в противном случае. Возвращает false для корня. 
 
        bool isa_right__child( ) const { 
            if ( (parent == 0) || ( parent->right_child != this) ) 
                return false; 
            else 
                return true; 
        }
        
        bool isa_left_child( ) const { 
            if ( (parent = 0) || ( parent->left_child != this) ) 
                return false; 
            else 
                return true; 
        }
        
        bool isa_leaf( ) const { 
            return ( (right_child == 0) && (left_child == 0) ); 
        }
        
        // Print( ) печатает дерево "на боку", корнем влево. 
        // "Обратный" рекурсивный порядковый обход (т.е. справа налево) 
        // — иначе был бы напечатан зеркальный образ. Nodecount/bal 
        // показаны в скобках. Нулевые потомки показаны как "@". 
 
        void print ( const int level = 0 ) const { 
 
            // Инициализация значением this вместо корня делает возможной 
            // печать поддеревьев, 
            const Tree_node *tn = this; 
 
            if ( tn != 0 ) tn->right_child->print( level + 1 ); 
 
            for (int spaces = 0; spaces < level; ++spaces) 
                cout << "       ";
                
            if ( tn != 0 ) 
                cout << tn->val << '(' << tn->nodecount     << '/' << bal <<  ')'<< endl;
            else 
                cout << "@" << endl; 
            if ( tn != 0 ) tn->left_child->print( level + 1 ); 
        }
        
    }; // Конец объявления Tree_node. 
    
private: 
// Закрытые данные Avl_tree: 
    
    Tree_node *root; 
    Tree_node *zero_node; // По сути константа, служит для возврата 
                    // нулевого значения иэ find_node(T). 
                    
// Закрытые функции Avl_tree: 
 
    // Запретить копирование и присваивание. 
    
    Avl_tree(const Avl_tree &); 
    Avl_tree & operator = ( const Avl_tree & ) ; 
    
    // Создать коневой узел, инициализировать val значением root_val, 
    // дочерние узлы нулем, bal нулем, nodecount единицей, 
    void make_new_root( const T root_val ) { 
        root = new Tree_node(root_val); 
        root->left_child = 0; 
        root->right_child = 0; 
        root->parent = 0; 
        root->bal = 0; 
        root->nodecount = 1;
    }
    
    
    // Find__node(T find_value) возвращает ссылку на указатель, 
    // чтобы упростить реализацию remove(T). 
    
    Tree_node * & find_node( T find_value ) { 
        Tree_node *tn = root; 
        while ( (tn != 0) && (tn->val != find_value) ) { 
            if ( find_value < tn->val ) 
                tn = tn->left_child; 
            else 
                tn = tn->right_child; 
        }
        
        // Вместо того, чтобы просто возвратить tn, мы несколько 
        // усложняем процедуру, гарантируя, что возвращаем *ссылку* 
        // в пределах дерева на узел, который ищем. 
        
        if ( tn == 0 ) 
            // Find_value нет в дереве. 
            return zero_node; 
        else if ( tn->isa_left_child( ) ) 
            // Tn - левый потомок своего родителя. 
            return tn->parent->left_child; 
        else if ( tn->isa_right_child( ) ) 
            // Tn - правый потомок своего родителя. 
            return tn->parent->right_child; 
        else if ( tn == root ) 
            // Специальный случай - родитель отсутствует. 
            return root; 
 
        // Управление не достигает этой точки. Возвратить фиктивное 
        // значение, чтобы предотвратить предупреждение компилятора, 
        assert(false); 
        return zero_node; 
    }
    
    
    // Insert_node( const T, Tree_node * ) присоединяет новое значение 
    // к соответствующему листу, если значения еще нет в дереве. 
    // Возвращает указатель на новый узел, если он создан, иначе 0. 
    // Нерекурсивна. Увеличивает nodecount каждого пройденного узла. 
    // Это делается *после* вставки узла, чтобы не получить неверных 
    // nodecount в случае уже имеющегося в дереве значения. 
    
    Tree_node * insert_node 
    ( const T insert_value, Tree_node * start_node = 0 ) 
    {
    
        if ( root == 0 ) { 
            // Специальный случай пустого дерева.
            make_new_root( insert_value ); 
            return root; 
        }
        
        
        if ( start_node == 0 ) start_node = root; 
        
        Tree_node *tn = start_node; 
 
        while ( (tn != 0) && (tn->val != insert_value) ) { 
 
            if ( insert_value < tn->val ) { 
                // Проверить левого потомка, 
                if ( tn->left_child == 0 ) { 
                
                    // Присоединить новый узел в качестве левого потомка tn. 
                    attach_node( tn, tn->left_child, insert_value ); 
                    
                    // Модифицировать nodecounts и факторы баланса для всех 
                    // предков. Если найден предок с новым фактором баланса +2 
                    // или -2, дерево в данной точке нуждается в балансировке 
                    // путем соответствующих ротаций. Заметьте, что это нужно 
                    // сделать всего один раз. После того, как такой узел 
                    // сбалансирован, его предки автоматически окажутся 
                    // также сбалансированными. 
                    
                    adjust_for_add( tn->left_child ); 
                    return tn->left_child; 
                }
                else {
                    tn = tn->left_child; 
                }
            }
            else {
                // Проверить правого потомка, 
                if ( tn->right_child == 0 ) { 
                
                    // Присоединить новый узел в качестве правого потомка tn. 
                    attach_node( tn, tn->right_child, insert_value ); 
                    
                    adjust_for_add( tn->right_child ); 
                    return tn->right_child; 
                }
                else {
                    tn = tn->right_child; 
                }
            }
        }
        
        // Insert_value уже имеется в дереве, 
        assert ( tn != 0 ); 
        return 0; 
    }
    
    
    // Attach_node( Tree_node *, Tree_node * &, T ) - вспомогательная 
    // функция для insert_node( const T insert_value, Tree_node * ). 
    
    void attach_node( Tree_node * new_parent, Tree_node * & new_child, T insert_value ) {
    
        // Присоединить новое значение в качестве левого потомка tn. 
        new_child = new Tree_node( insert_value ); 
        new_child->left_child = 0; 
        new_child->right_child = 0; 
        new_child->parent = new_parent; 
        new_child->nodecount = 1; 
        new_child->bal = 0; 
    }
    
    // Adjust_nodecount_to_root( Tree_node *, int ) прибавляет incr 
    // к полю nodecount узла tn всех его предков включая корень. 
    // Заметьте, что родительская связка корня равна 0. 
    
    void adjust_nodecount_to_root( Tree_node * tn, int incr ) { 
        while ( tn != 0 ) { 
            tn->nodecount += incr; 
            tn = tn->parent; 
        }
    }
    // Adjust_for_add( Tree_node *, Tree_node * ) изменяет факторы 
    // баланса и nodecount для вновь созданного узла и его предков. 
    // При необходимости выполняются ротации. Если мы найдем 
    // несбалансированный узел (с фактором баланса 2 или -2) 
    // и сбалансируем его поддерево, то можем на этом закончить, 
    // поскольку методика балансировки сохраняет исходную высоту 
    // данного поддерева. 
    
    void adjust_for_add( Tree_node * new_child ) { 
    
        // New_parent может быть корнем, но new_child - нет. 
        assert( new_child != root ); 
        bool rotate_flag = false; 
        bool bal_was_changed = false; 
        
        Tree_node * new_parent = new_child->parent; 
        Tree_node * new_grandparent = new_parent->parent; 
        
        // Родитель вновь созданного узла не может быть выведен из 
        // равновесия этой вставкой. Только его *прародитель* может 
        // быть первым узлом, где баланс нарушается. Поэтому мы делаем 
        // первую "итерацию" вне цикла и затем инициализируем 
        // трехуровневую структуру для собственно цикла. 
        
        ++(new_parent->nodecount); 
        
        if ( new_child->isa_right_child( ) ) { 
            // New_parent был сбалансирован и не имел правого потомка. 
            // Поэтому высота его левого поддерева должна быть 0 или 1. 
            ++(new_parent->bal) ; 
            bal_was_changed = true; 
        }
        else {
            // New_child должен быть левым потомком, так как он не корень. 
            -- (new_parent->bal) ; 
            bal_was_changed = true; 
        }
        
        assert ( (new_parent->bal > -2) && (new_parent->bal < 2) ); 
        
        while ( new_grandparent != 0 ) { 
        
            // В цикле мы полагаем, что new_child и new_parent обновлены. 
            // Мы обновляем new_grandparent. Сначала нужно обновить 
            // его nodecount и фактор баланса. 
            
            ++(new_grandparent->nodecount); 
            
            if ( new_parent->isa_right_child( ) ) { 
                // Если новый фактор баланса new_parent 1 или -1, и он 
                // изменился, то перед этим он был нулем. Следовательно, 
                // высота поддерева с корнем в new_parent увеличилась на 1. 
                // Соответственно высота правого поддерева new_grandparent 
                // также увеличилась на единицу. С другой стороны, если 
                // new_parent->bal стал теперь нулем, он должен был быть 
                // равен 1 или -1, так что новый уэел выровнял поддерево 
                // с корнем в new_parent, и его выысота и, следовательно, 
                // фактор баланса для new_grandparent не изменились, 
                if ( new_parent->bal ! = 0 && bal_was_changed ) 
                    // Незачем трогать bal_was_changed. Нам нужно, чтобы он 
                    // оставался равен true при следующей итерации, 
                    ++(new_grandparent->bal); 
                else 
                    // new_grandparent->bal не был изменен, так что мы хотим, 
                    // чтобы bal_was_changed был false при следующей итерации, 
                    bal_was_changed = false; 
            }
            else if ( new_parent->isa_left_child( ) ) { 
                // Предыдущие комментарии годятся и здесь, но теперь мы 
                // уменьшаем new_grandparent->bal, так как рассматриваем 
                // его левое поддерево, 
                if ( new_parent->bal != 0 && bal_was_changed ) 
                    -- (new_grandparent->bal) ; 
                else 
                    bal_was_changed = false; 
            }
            
            if ( (new_grandparent->bal < -1) || (new_grandparent->bal > 1) ) { 
                rotate_flag = true; 
                break; 
 
            }
            
            // Подняться по дереву на шаг. 
            new_child = new_parent; 
            new_parent = new_grandparent; 
            new_grandparent = new_grandparent->parent; 
        }
        
        if ( rotate_flag ) { 
            // New_grandparent несбалансирован, и мы должны сбалансировать 
            // его путем одной или двух ротаций. Хотя есть четыре случая, 
            // два иэ них - зеркальные отражения. Помните, мы только что 
            // обновили nodecount вплоть до узла, который несбалансирован. 
            // Когда мы завершим ротации, нужно будет обновить nodecount 
            // между данной точкой и корнем. 
            
            // Некоторые операции обновления баланса для new_child зависят 
            // от исходного фактора баланса, поэтому запишем их здесь, 
            // перед тем как начать ротацию, 
            int new_child_orig_bal = new_child->bal; 
            
            // Простой случай (всего одна ротация) и его отражение, 
            if ( new_parent->isa_left_child( ) && new_child->isa_left_child( ) ) { 
                // Ротация new_parent направо вокруг new_grandparent. 
                // new_grandparent передается по ссылке, 
                if ( new_grandparent->isa_left_child( ) ) 
                    rotate_right( new_grandparent->parent->left_child ); 
                else if ( new_grandparent->isa_right_child( ) ) 
                    rotate_right( new_grandparent->parent->right_child ); 
                else { 
                    assert( new_grandparent == root ); 
                    rotate_right( root ); 
                }
                
                
                // Обновить факторы баланса и nodecount начиная от 
                // new_parent->parent, который теперь не то же самое, чтобы
                // new_grandparent - это результат проведенной ротации. 
                new_parent->bal = 0; 
                new_parent->right_child->bal = 0; 
                adjust_nodecount_to_root( new_parent->parent, 1 ); 
            }
            else if ( new_parent->isa_right_child( ) && new_child->isa_right_child( ) ) { 
            
                // Ротация new_parent налево вокруг new_grandparent 
                
                // new_grandparent передается по ссылке, 
                if ( new_grandparent->isa_left_child( ) ) 
                    rotate_left( new_grandparent->parent->left_child ); 
                else if ( new_grandparent->isa_right_child( ) ) 
                    rotate_left( new_grandparent->parent->right_child ); 
                else { 
                    assert( new_grandparent == root ); 
                    rotate_left ( root ) ; 
                }
                
                // Обновить факторы баланса и nodecount. 
                new_parent->bal = 0; 
                new_parent->left_child->bal = 0; 
                adjust_nodecount_to_root( new_parent->parent, 1 ); 
            }
            
            // Теперь тяжелые случаи, требующие двух ротаций, 
            else if ( new_parent->isa_left_child( ) && new child->isa_right_child( ) ) 
            { 
                // Ротация new_child. new_parent передается по ссылке. 
                // Мы уже знаем, что new_parent - левый потомок, 
                // так что проверять не стоит.
                rotate_left( new_grandparent->left_child ); 
                
                // new_child передается по ссылке. Здесь нам уже нужно 
                // проверять, так как потомок был повернут, и прежние 
                // предположения не годятся. Так как new_child поднялся 
                // на шаг, нам нужно проверить new_grandparent, а не 
                // new_parent. 
                if ( new_grandparent->isa_left_child( ) ) 
                    rotate_right( new_grandparent->parent->left_child ); 
                else if ( new_grandparent->isa_right_child( ) ) 
                    rotate_right( new_grandparent->parent->right_child ); 
                else { 
                    assert ( new_grandparent == root ) ; 
                    rotate_right( root ); 
                }
                
                // New_grandparent теперь правый потомок вновь 
                // сбалансированного поддерева. Обновить факторы баланса и 
                // nodecount начиная с родителя этого поддерева, 
                new_grandparent->parent->bal = 0; 
                
                // Другие модификации зависят от исходного фактора баланса 
                // new_child. 
                if (new_child_orig_bal == 0) { 
                    new_grandparent->bal = 0; 
                    new_grandparent->parent->left_child->bal = 0; 
                } 
                else if (new_child_orig_bal == -1) { 
                    new_grandparent->bal = 1; 
                    new_grandparent->parent->left_child->bal = 0; 
                } 
                else if (new_child_orig_bal = 1) { 
                    new_grandparent->bal = 0; 
                    new_grandparent->parent->left_child->bal = -1; 
                }
                
                adjust_nodecount_to_root ( new_grandparent->parent->parent , 1 ); 
            }
            
            else if ( nev_parent->isa_right_child( ) && new_child->isa_left_child( ) ) { 
            
                // Ротация new_child. new_parent передается по ссылке. 
                // мы уже знаем, что new_parent - правый потомок, 
                // проверять нет нужды.
                rotate_right ( new_grandparent->right_child ); 
                
                // new_child передается по ссылке. На этот раз требуется 
                // проверка, поскольку потомок был повернут и прежние 
                // предположения не годятся. Так как new_child поднялся 
                // на шаг, нам нужно проверять new_grandparent, а не 
                // new_parent. 
                if ( new_grandparent->isa_left_child( ) )   
                    rotate_left( new_grandparent->parent->left_child ); 
                else if ( new_grandparent->isa_right_child( ) ) 
                    rotate_left( new_grandparent->parent->right_child ); 
                else { 
                    assert( new_grandparent == root ); 
                    rotate_left( root ); 
                }
                // New_grandparent теперь левый потомок вновь 
                // сбалансированного поддерева. Обновить факторы баланса и 
                // nodecounts начиная с родителя этого поддерева, 
                new_grandparent->parent->bal = 0;
                
                // Другие модификации зависят от исходного фактора баланса 
                // new_child. 
                if (new_child_orig_bal = 0) { 
                    new_grandparent->bal = 0; 
                    new_grandparent->parent->right_child->bal = 0; 
                }
                else if (new_child_orig_bal == -1) { 
                    new_grandparent->bal = 0; 
                    new_grandparent->parent->right_child->bal = 1; 
                }
                else if (new_child_orig_bal == 1) { 
                    new_grandparent->bal = -1; 
                    new_grandparent->parent->right_child->bal  = 0;
                }
                
                adjust_nodecount_to_root  ( new_grandparent->parent->parent , 1 ) ; 
            }
        }
        
    }
    
    
    // Get_nth_node( Tree_node *, const int ) возвращает узел, 
    // соответствующий n-му (в отсортированном дереве) значению. 
    // Рекурсивна. Требует, чтобы поле nodecount было корректным. 
    
    Tree_node * get_nth_node(Tree_node * tn, const int nth) const { 
    
        // Специальный случай пустого корня. 
        if ( tn == 0 ) return 0; 
        
        // Запомнить nodecount левого потомка tn. 
        int lc_count = (tn->left_child != 0) ? tn->left_child->nodecount : 0 ; 
        
        if ( (lc_count + 1) == nth ) { 
            // Готово, так как tn сам и является n-ым значением. 
            return tn; 
        }
        else if ( lc_count >= nth ) { 
            // Поиск nth в левом потомке. 
            return get_nth_node(tn->left_child, nth); 
        }
        else { 
            // Поиск (nth - lc_count - 1) в правом потомке. 
            return get_nth_node(tn->right_child, nth - lc_count -1); 
        }
    }
    // Функции ротации статические, поскольку им не нужен указатель 
    // this. Заметьте, что параметр является ссылкой на указатель 
    // Tree_node. 
 
    static void rotate_right(Tree_node * & node) { 
        Tree_node *tn = node->left_child; 
        
        node->left_child = tn->right_child; 
        if (tn->right_child) tn->right_child->parent = node; 
        
        tn->right_child = node; 
        tn->parent = node->parent; 
        node->parent = tn; 
        
        // Обновить nodecount перед обновлением узла. 
        // Это нужно сделать именно в таком порядке, т.е. начиная 
        // с нижнего узла. 
        
        int leftcount = node->left_child ? node->left_child->nodecount : 0; 
        int rightcount = node->right_child ? node->right_child->nodecount : 0; 
        
        node->nodecount = leftcount + rightcount + 1; 
        
        leftcount = tn->left_child ? tn->left_child->nodecount : 0; 
        rightcount = tn->right_child ? tn->right_child->nodecount : 0; 
        
        tn->nodecount = leftcount + rightcount + 1; 
        
        node = tn; 
    }
    
    static void rotate_left(Tree_node * & node) { 
        Tree_node *tn = node->right_child; 
        
        node->right_child = tn->left_child; 
        if (tn->left_child) tn->left_child->parent = node; 
        
        tn->left_child = node; 
        tn->parent = node->parent; 
        node->parent = tn; 
        
        // Обновить nodecount перед обновлением узла. 
        // Это нужно сделать именно в таком порядке, т.е. начиная 
        // с нижнего узла. 
        
        int leftcount = node->left_child ? node->left_child->nodecount : 0; 
        int rightcount = node->right_child ? node->right_child->nodecount : 0; 
        node->nodecount = leftcount + rightcount + 1; 
        
        leftcount = tn->left_child ? tn->left_child->nodecount : 0; 
        rightcount = tn->right_child ? tn->right_child->nodecount : 0; 
        
        tn->nodecount = leftcount + rightcount + 1; 
        
        node = tn;
    }
    
    
    // Cleanup ( Tree_node * ) удаляет все Tree_nodes в обходе с 
    // отложенной выборкой. Делает реальную работу для ~Avl_tree( ) 
    
    void cleanup (Tree_node *tn) { 
    
        // Специальный случай пустого корня, 
        if ( tn == 0 ) return; 
        
        if ( tn->left_child != 0 ) { 
            cleanup(tn->left_child); 
            tn->left_child = 0; 
        }
        if ( tn->right_child != 0 ) { 
            cleanup(tn->right_child) ; 
            tn->right_child = 0; 
        }
        delete tn; 
    }
    
    
    // Print_pre( const Tree_node * ) рекурсивно печатает значения 
    // поддерева с корнем в tn с предварительной выборкой. 
    
    void print_pre(const Tree_node * tn) const { 
    
        // Специальный случай пустого корня, 
        if ( tn == 0 ) return; 
        
        cout << tn->val << " "; 
        if ( tn->left_child != 0 ) { 
            print_pre( tn->left_child ); 
        }
        if ( tn->right_child != 0 ) { 
            print_pre( tn->right_child ); 
        }
    }
    
    // Print_in( const Tree_node * ) рекурсивно печатает значения 
    // поддерева с корнем в tn с порядковой выборкой (сортированные). 
    
    void print_in(const Tree_node * tn) const { 
        // Специальный случай пустого корня, 
        if ( tn == 0 ) return; 
        
        if ( tn->left_child != 0 ) { 
            print_in( tn->left_child ); 
        }
        cout << tn->val << "    "; 
        if ( tn->right_child != 0 ) { 
            print_in( tn->right_child ); 
        }
    }
    
    // Print_post( const Tree_node * ) рекурсивно печатает значения 
    // поддерева скорнем в tn с отложенной выборкой. 
    
    void print_post(const Tree_node * tn) const { 
    
        // Специальный случай пустого корня, 
        if ( tn == 0 ) return; 
        
        if ( tn->left_child != 0 ) { 
            print_post( tn->left_child ); 
        } 
        if ( tn->right_child != 0 ) { 
            print_post( tn->right_child ); 
        } 
        cout << tn->val << "    "; 
    }
    
// Конец закрытых функций Avl_tree. 
 
 
 
public: 
 
// Открытые функции-элементы Avl_tree: 
 
    Avl_tree( ) : zero_node(0) { root = 0; } 
    
    Avl_tree(const T root_val ) : zero_node(0) { 
        make_new_root( root_val ); 
    }
    
    
    // Освободить память, обойдя все Tree_node с отложенной выборкой. 
    // Всю работу делает закрытая cleanup( Tree_node * ). 
    
    ~Avl_tree( ) { 
        cleanup( root ); 
    }
    
    // Add( const T ) вставляет в дерево значение, если его еще там 
    // нет. Возвращает true, если insert_value было действительно 
    // добавлено. Всю реальную работу делает insert_node(T). 
    bool add( const T insert_value ) { 
        Tree_node *ret = insert_node(insert_yalue); 
        if (ret) return true; 
        else return false; 
    }
    
    
    // Remove( T ) удаляет из дерева узел со значением value. 
    // Эту функцию реализовать труднее всего, так как удаляемый 
    // уэел может иметь два дочерних узла. Эти его потомки должны 
    // быть вновь прикреплены к дереву, но удаляемый уэел имеет всего 
    // одного родителя, так что требуется некоторая "хирургия". Эта 
    // операция выполняется таким образом, что сохраняется критерий 
    // двоичного дерева поиска и высота дерева *не* увеличивается. 
    // Объявление node_to_remove как ссылки на указатель позволяет 
    // сделать remove( T ) менее сложной, чем это могло бы быть. 
    
    void remove( T value ) { 
    
        Tree_node * & node_to_remove = find_node ( value ) ; 
        
        Tree_node * predecessor = 0; 
        Tree_node * temp = 0; 
        int delta_balance = 0; 
        
        if ( node_to_remove == zero_node ) return; 
        assert( node_to_remove->val == value ) ; 
        
        // Сначала обработаем более простые случаи, где node_to_remove 
        // имеет не более одного потомка. 
        
        if ( node_to_remove->left_child == 0 ) { 
        
            // Node_to_remove не имеет левого потомка, 
            temp = node_to_remove; 
            
            // Обновить поля nodecount и bal родителя перед тем, 
            // как начать удаление. В противном случае функции "isa" 
            // не смогут правильно работать, 
            if (temp->parent) { 
                -- (temp->parent->nodecount); 
                if (temp->isa_left_child( )) { 
                    ++(temp->parent->bal); 
                    delta_balance = 1; 
                }
                else if (temp->isa_right_child( )) { 
                    --(temp->parent->bal); 
                    delta_balance = -1; 
                }
            }
            
            if ( node_to_remove->right_child != 0 ) { 
                // Node_to_remove имеет правого потомка. 
                node_to_remove->right_child->parent = node_to_remove->parent; 
            }
            
            // Заменить node_to_remove его правым потомком. Если он 
            // нулевой - неважно. После данного оператора переменная 
            // node_to_remove больше не ссылается на удаляемый узел. 
            // На него все еще ссылается temp. 
            node_to_remove = node_to_remove->right_child; 
            
            // Правый потомок node_to_remove теперь занимает его прежнюю 
            // позицию в дереве, nodecount потомка не изменился. 
            // Но nodecount его родителя и всех остальных предков 
            // нужно уменьшить на 1, чтобы учесть удаленный узел. Мы 
            // обновим поля nodecount and bal родителя прямо здесь, 
            // предоставив adjust_for_remove( ) сделать это для всех 
            // узлов от parent до корня. 
            
            // После обновления освободить память только что удаленного 
            // из дерева узла. 
            adjust_for_remove(temp->parent, delta_balance); 
            delete temp; 
            
            return; 
        }
        else if ( node_to_remove->right_child = 0 ) { 
        
            // Node_to_remove не имеет правого потомка, 
            temp = node_to_remove; 
            
            if (temp->parent) { 
                --(temp->parent->nodecount); 
                if (temp->isa_left_child( )) { 
                    ++(temp->parent->bal); 
                    delta_balance = 1; 
                }
                else if (temp->isa_right_child( )) { 
                    --(temp->parent->bal); 
                    delta_balance = -1; 
                }
            }
            
            // Мы знаем, что левый потомок ненулевой, поскольку находимся 
            // в "блоке else". Следовательно, нет нужды делать проверку 
            // перед тем, как выполнить следующий оператор, 
            node_to_remove->left_child->parent = node_to_remove->parent; 
            
            // См. выше замечание о "блоке else". 
            node_to_remove = node_to_remove->left_child; 
            adjust_for_remove(temp->parent, delta_balance); 
            delete temp; 
            
            return; 
        }
        // Если мы дошли до этой точки, мы энаем, то node_to_remove 
        // имеет два дочерних узла. Найти его непосредственного 
        // предшественника, т.е. самого правого потомка его левого 
        // дочернего уэла. 
        
        predecessor = node_to_remove->left_child; 
        while ( predecessor->right_child != 0 ) 
            predecessor = predecessor->right_child; 
            
        // Заменить значение node_to_remove значением его 
        // предшественника, 
        node_to_remove->val = predecessor->val; 
        
        // Теперь, когда предшествующее значение сдвинулось вверх по 
        // дереву, мы должны прикрепить левого потомка предшественника к 
        // его родителю. Он станет правым потомком родителя. 
        // Вспомните, что predecessor не имеет правого потомка, 
        // поскольку мы нашли его именно по этому признаку. 
        
        Tree_node * pp = predecessor->parent; 
        
        if ( pp == node_to_remove ) { 
            // Специальный случай, когда predecessor является левым 
            // потомком node_to_remove (т.е. у него нет правого потомка) . 
            pp->left_child = predecessor->left_child; 
            ++(pp->bal); 
            delta_balance = 1; 
            if ( predecessor->left_child != 0 ) 
                predecessor->left_child->parent = pp; 
        }
        else if ( predecessor->left_child != 0 ) { 
            // Predecessor имеет левого потомка, и мы не можем оставить 
            // его "висящим". Сделать его правым потомком родителя 
            // predecessor'a. 
            pp->right_child = predecessor->left_child; 
            predecessor->left_child->parent = pp; 
            --(pp->bal); 
            delta_balance = -1; 
        }
        else { 
            // Левый потомок предшественника нулевой, поэтому полю его 
            // родителя right_child не на что укаэыввать. 
            assert( pp->right_child == predecessor ) ; 
            pp->right_child = 0; 
            --(pp->bal) ; 
            delta_balance = -1; 
        }
        
        // Обновить nodecount для predecessor->parent и всех его 
        // предков. Родительская связка корня равна нулю. Второй 
        // аргумент adjust_for_remove равен 1, так как это - 
        // *абсолютное значение* изменения фактора баланса уэла pp 
        // для каждой проведенной выше модификации. 
        --(pp->nodecount); 
        adjust_for_remove(pp, delta_balance) ; 
        
        // Предшествующее удаленному значение переместилось в другой 
        // уэел, а потомки уэла predecessor, если они были, прикреплены 
        // к его родителю. Нам больше не нужна память, которую исходно 
        // эанимал predecessor, 
        delete predecessor; 
    }
    
    // Пройти обратно от start_node до корня, обновляя по пути 
    // поля nodecount и bal каждого уэла начиная с родителя 
    // start_node. Когда узел оказывается разбалансированным, 
    // произвести его ротацию. 
    // Delta_balance - это величина, на которую изменилось поле bal 
    // узла start_node непосредственно перед вызовом. Не забывайте, 
    // что родитель корня - нулевой. 
    
    void adjust_for_remove( Tree_node * start_node, int delta_balance ) { 
    
        Tree_node * tn = start_node; 
        int tn_bal_orig = tn->bal; 
        
        if ( (tn->bal == -2) || (tn->bal == 2) ) 
            tn = rotate_for_remove (tn, delta_balance); 
            
        delta_balance = tn_bal_orig - tn->bal; 
        int absdelta = (delta_balance > 0) ? delta_balance : -delta_balance; 
        Tree_node * tnp = tn->parent; 
        
        while ( tnp != 0 ) { 
            // Обновить поля bal и nodecount узла tnp. 
            // Если tnp раэбалансирован, выполнить соответствующие 
            // ротации. Функции ротации написаны так, что попутно 
            // выполняют и эти обновления. 
            
            // Обновить nodecount 
            --(tnp->nodecount); 
            
            // Обновить фактор баланса. Сам tn уже обновлен, и мы знаем, 
            // как изменился его фактор баланса. Если tn - правый потомок 
            // и его текущий фактор баланса нулевой, то мы уменьшим 
            // фактор баланса tnp на абсолютное значение изменения 
            // фактора баланса tn. 
            // Если tn - левый потомок и его текущий фактор баланса нуль, 
            // мы увеличим фактор баланса tnp на это значение. 
            // Заметьте, что если только фактор баланса tn не изменился 
            // на *нуль*, фактор баланса tnp остается неизменным. 
            // Если же фактор баланса tnp остался неизменным, 
            // то же можно сказать и о всех его предках. 
            // С этого момента мы можем больше не проверять факторы 
            // баланса и просто уменьшать nodecounts. 
            // Заметьте, что нам нужно помнить значение tnp->bal
            // в случае, если потребуются ротации, чтобы мы могли 
            // определить новое значение absdelta для следующей итерации. 
            
            assert(tn != root); 
            if ( tn->bal == 0 ) { 
                if ( tn->isa_right_child( )) { 
                    --(tnp->bal); 
                    delta_balance = -1; 
                }
                else { 
                    ++(tnp->bal); 
                    delta_balance = 1; 
                }
            }
            else { 
                adjust_nodecount_to_root( tnp->parent, -1 ) 
                return; 
            }
            
            
            // Переместиться на ступень вверх для следующей итерации, 
            if ( (tnp->bal > -2) && (tnp->bal < 2) ) { 
                tn = tnp; 
                tnp = tn->parent; 
                continue; 
            }
            
            // Самая тяжелая работа возложена на этотвызов. 
            tn = rotate_for_remove (tnp, delta_balance); 
            tnp = tn->parent; 
        }
        
    }
    
    Tree_node * rotate_for_remove( Tree_node * tn, int delta_balance ) { 
            // Теперь, наконец, самое трудное. Если tnp стал 
            // раэбалансированным, мы должны вновь сбалансировать дерево 
            // посредством ротаций. 
            
            Tree_node * resume_iteration = 0; 
            Tree_node * tnp = tn->parent; 
            
            //if ( tn->isa_left_child( ) )  {
            if ( delta_balance > 0 ) { 
                // Tn lost a left descendant. 
                
                // Запомнить, как выйти на текущего правого потомка tn, 
                // так как в первом случае, после ротации, он будет тем 
                // узлом, с которого продолжится восхождение. Во втором 
                // случае отправной точкой будет левый потомок этого узла.
                resume_iteration = tn->right_child; 
                
                if ( (tn->bal == 2) && ( (tn->right_child->bal == 1) || (tn->right_child->bal == 0) ) ) {
                
                    // Обновить факторы баланса значениями после ротации.
                    if (tn->right_child->bal == 1) { 
                        tn->bal = 0; 
                        tn->right_child->bal = 0; 
                    }
                    else { 
                        assert(tn->right_child->bal == 0); 
                        tn->bal = 1; 
                        tn->right_child->bal = -1; 
                    }
                    
                    // Одиночная ротация. 
                    // Хитрая передача tnp по ссылке. 
                    if ( tn->isa_left_child( ) ) 
                        rotate_left(tn->parent->left_child); 
                    else if ( tn->isa_right_child( ) ) 
                        rotate_left(tn->parent->right_child); 
                    else { 
                        assert(tn == root); 
                        rotate_left(root); 
                    }
                    
                    return resume_iteration; 
                }
                else if ( (tn->bal == 2) && (tn->right_child->bal == -1) ) {
                
                    // Обновить факторы баланса значениями после ротации, 
                    if (tn->right_child->left_child->bal == 1) { 
                        tn->bal = -1; 
                        tn->right_child->bal = 0; 
                        tn->right_child->left_child->bal = 0; 
                    }
                    else if (tn->right_child->left_child->bal == -1) { 
                        tn->bal = 0; 
                        tn->right_child->bal = 1; 
                        tn->right_child->left_child->bal = 0; 
                    }
                    else { 
                        assert (tn->right_child->left_child->bal == 0) ; 
                        tn->bal = 0; 
                        tn->right_child->bal = 0; 
                        tn->right_child->left_child->bal = 0; 
                    }
                    
                    // Двойная ротация. 
                    resume_iteration = resume_iteration->left_child; 
                    
                    // Первая ротация, 
                    rotate_right(tn->right_child) ; 
                    // Вторая ротация. 
                    if ( tn->isa_left_child( ) ) 
                        rotate_left(tn->parent->left_child); 
                    else if ( tn->isa_right_child( ) ) 
                        rotate_left(tn->parent->right_child)
                    else { 
                        assert(tn == root); 
                        rotate_left(root); 
                    }
                    
                    return resume_iteration; 
                }
            }
            // else if ( tn->isa_right_child( ) ) { 
            else { 
                assert ( delta_balance < 0 ); 
                // Отражение предыдущих. 
                // Tn потерял правого потомка. 
                
                // Запомнить, как выйти на текущего правого потомка tn, 
                // так как в первом случае, после ротации, он будет тем 
                // узлом, с которого'продолжится восхождение. Во втором 
                // случае отправной точкой будет правый потомок этого уэла. 
                resume_iteration = tn->left_child; 
                
                if ( (tn->bal == -2) && ( (tn->left_child->bal == -1) || (tn->left_child->bal == 0) ) ) { 
                
                    // Обновить факторы баланса значениями после ротации, 
                    if (tn->left_child->bal == -1) { 
                        tn->bal = 0; 
                        tn->left_child->bal = 0; 
                    }
                    else { 
                        assert(tn->right_child->bal == 0); 
                        tn->bal = -1; 
                        tn->left_child->bal = 1; 
                    }
                    
                    // Одиночная ротация. 
                    if ( tn->isa_left_child( ) ) 
                        rotate_right(tn->parent->left_child)
                    else if ( tn->isa_right_child( ) ) 
                        rotate_right(tn->parent->right_child); 
                    else { 
                        assert(tn == root); 
                        rotate_right(root); 
                    }
                    
                    return resume_iteration; 
                }
                else if ( (tn->bal == -2) && (tn->Ieft_child->bal ==1) ) { 
                    // Обновить факторы баланса значениями после ротации, 
                    if (tn->left_child->right_child->bal = -1) { 
                        tn->bal = 1; 
                        tn->left_child->bal = 0; 
                        tn->left_child->left_child->bal = 0; 
                    }
                    else if (tn->left_child->right_child->bal == 1) { 
                        tn->bal = 0; 
                        tn->left_child->bal = -1; 
                        tn->left_child->right_child->bal = 0; 
                    } 
                    else { 
                        assert(tn->left_child->right_child->bal == 0);
                        tn->bal = 0; 
                        tn->left_child->bal = 0; 
                        tn->left_child->right_child->bal = 0; 
                    }
                    
                    // Двойная ротация. 
                    resume_iteration = resume_iteration->right_child; 
                    
                    // Первая ротация, 
                    rotate_left(tn->left_child) ;
                    
                    // Вторая ротация. 
                    if ( tn->isa_left_child( ) ) 
                        rotate_right(tnp->parent->left_child); 
                    else if ( tn->isa_right_child( ) ) 
                        rotate_right(tn->parent->right_child); 
                    else { 
                        assert(tn == root); 
                        rotate_right(root); 
                    }
                    
                    return resume_iteration; 
                }
            }
            
            // Управление не должно сюда попадать. Возвратить фиктивное 
            // значение, чтобы подавить предупреждение компилятора, 
            assert(false); 
            return zero_node; 
    }
    
    // Get_nth( const int ) возвращает n-oe порядковое значение 
    // дерева. 
    
    T get_nth(const int element_num) const { 
        Tree_node * tn = get_nth_node(root, element_num); 
        return tn->val; 
    }
    
    // Size( ) возвращает число узлов дерева. 
    int size( ) const { return root ? root->nodecount : 0; } 
    
    // Find( const T ) returns true if find_yalue is in the tree, 
    // false otherwise. 
    bool find( T find_value ) { 
        Tree_node *tn = find_node ( find_value ) ; 
        
        if ( tn != 0 ) 
            return true; 
        else 
            return false; 
    }
    
    
    // Print( ) производит обратную порядковую выборку и печатает 
    // дерево "на боку". 
    
    void print ( ) const { 
        cout << "\n" << "====================================== "<< "\n" << endl;
        
        // Это вызов Avl_tree::Tree_node::print( ), а 
        // *не* рекурсивный вызов Avl_tree::print( ). 
        root->print( ); 
    }
 
    // Следующие функции печатают дерево в линейной последовательности 
    // при обходе с предварительной, порядковой и отложенной выборкой. 
    // Print_inorder( ) эквивалентна сортировке. Эти функции не имеют 
    // параметров, но вызывают рекурсивные закрытые функции, принимающие 
    // параметры типа Tree_node *, чтобы те выполняли всю работу. 
    
    void print_pre_order( ) const { 
        print_pre (root) ; 
        cout << endl; 
    }
    
    void print_in_order( ) const { 
        print_in(root); 
        cout << endl; 
    }
    
    void print_post_order( ) const { 
        print_post(root); 
        cout << endl; 
    }
    
};

#include "avl.h" 
 
// Создать сбалансированное двоичное дерево поиска с целыми числами. 
// Изначально дерево пустое. 
Avl_tree <int> my_avlt; 
 
// Заполнить my_avlt целыми значениями. Ввести их 
// в восходящем порядке, что является наихудшей из возможных 
// последовательность для простого двоичного дерева поиска. 
void populate( ) { 
    my_avlt.add( 1 ); 
    my_avlt.add( 2 ); 
    my_avlt.add( 3 ); 
    my_avlt.add( 4 ); 
    my_avlt.add( 5 ) ; 
    my_avlt.add( 6 ) ; 
    my_avlt.add( 7 ) ; 
}
 
int main ()
{
    populate( ); 
    
    // Напечатать все дерево. Оно должно быть хорошо сбалансировано, 
    // несмотря на попытку populate( ) сделать его перекошенным, 
    my_avlt.print ( ) ; 
    
    // Уделить значения толко из левого поддерева - еще одна жалкая 
    // попытка перекосить дерево, 
    my_avlt.remove ( 1 ); 
    my_avlt.remove ( 2 ); 
    my_avlt.remove ( 3 ); 
    
    // Снова напечатать все дерево, 
    my_avlt.print ( ); 
    
    return 0; 
}