Допилить балансировку

[avasyukov]

Сейчас она делает попытки работать, но работает не до конца.

Для отладки можете закинуть в maintree.cpp вот такое:

class DebugTree : public SimpleTree
{
    void print()
    {
        tree_element* cur_element = this->root;
        printSubTree(cur_element);
    }

    void printSubTree(tree_element* cur_element)
    {
        cerr << "Element: " << cur_element->value << " ";
        cerr << "Height: " << cur_element->height << " ";
        if(cur_element->parent != nullptr)
            cerr << "Parent: " << cur_element->parent->value << " ";
        else
            cerr << "Parent: -- ";

        if(cur_element->left != nullptr)
            cerr << "Left: " << cur_element->left->value << " ";
        else
            cerr << "Left: -- ";

        if(cur_element->right != nullptr)
            cerr << "Right: " << cur_element->right->value << " ";
        else
            cerr << "Right: -- ";

        cerr << endl;

        if (cur_element-> left != nullptr)
            printSubTree(cur_element->left);

        if (cur_element-> right != nullptr)
            printSubTree(cur_element->right);
    }
};

int main()
{
    Container* c = new DebugTree();

    for(int i = 1; i < 10; i++)
        c->insert(i*i);

    cerr << "Tree after creation:" << endl;
    c->print();

    c->remove(25);
    cerr << "Tree after deletion of the element:" << endl;
    c->print();

    delete c;
    return 0;
}

Оно выдаст полную картину, как устроено дерево:

Tree after creation:
Element: 25 Height: 6 Parent: -- Left: 16 Right: 36 
Element: 16 Height: 4 Parent: 25 Left: 9 Right: -- 
Element: 9 Height: 3 Parent: 16 Left: 4 Right: -- 
Element: 4 Height: 2 Parent: 9 Left: 1 Right: -- 
Element: 1 Height: 1 Parent: 4 Left: -- Right: -- 
Element: 36 Height: 5 Parent: 25 Left: -- Right: 49 
Element: 49 Height: 4 Parent: 36 Left: -- Right: 64 
Element: 64 Height: 2 Parent: 49 Left: -- Right: 81 
Element: 81 Height: 1 Parent: 64 Left: -- Right: -- 
Tree after deletion of the element:
Element: 16 Height: 4 Parent: -- Left: 9 Right: 36 
Element: 9 Height: 3 Parent: 16 Left: 4 Right: -- 
Element: 4 Height: 2 Parent: 9 Left: 1 Right: -- 
Element: 1 Height: 1 Parent: 4 Left: -- Right: -- 
Element: 36 Height: 5 Parent: 16 Left: -- Right: 49 
Element: 49 Height: 4 Parent: 36 Left: -- Right: 64 
Element: 64 Height: 2 Parent: 49 Left: -- Right: 81 
Element: 81 Height: 1 Parent: 64 Left: -- Right: --