Final_task_2

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

class Exception
{
private:
    string content;
public:
    Exception(string message) : content(message) {}

    string Message()
    {
        return content;
    }
};

template<class T> class BinaryTree
{
private:
    class Node
    {
    private:
        Node* left;
        Node* right;
        unsigned char height;
        T val;
    public:
        Node(T val) : val(val), left(0), right(0), height(1) {}

        Node(T val, Node* left, Node* right) : val(val), left(left), right(right)
        {
            height = left->Height() > right->Height() ? left->Height() : right->Height();
        }

        Node* Left()
        {
            return left;
        }

        void Left(Node* left)
        {
            this->left = left;
        }

        Node* Right()
        {
            return right;
        }

        void Right(Node* right)
        {
            this->right = right;
        }

        T Value()
        {
            return val;
        }

        unsigned char Height()
        {
            return height;
        }

        void Height(unsigned char h)
        {
            height = h;
        }
    };

    Node* head;
    int cnt;

    bool is_less(const T& a, const T& b) const
    {
        return a < b;
    }

    bool is_more(const T& a, const T& b) const
    {
        return b < a;
    }

    bool is_equally(const T& a, const T& b) const
    {
        return !(a < b) && !(b < a);
    }

    unsigned char node_height(Node* p)
    {
        return p ? p->Height() : 0;
    }

    int balanse_factor(Node* p)
    {
        return node_height(p->Right()) - node_height(p->Left());
    }

    void update_height(Node* p)
    {
        unsigned char height_left = node_height(p->Left());
        unsigned char height_right = node_height(p->Right());
        p->Height((height_left > height_right ? height_left : height_right) + 1);
    }

    Node* rotate_node_to_right(Node* p)
    {
        Node* q = p->Left();
        p->Left(q->Right());
        q->Right(p);

        update_height(p);
        update_height(q);
        return q;
    }

    Node* rotate_node_to_left(Node* q)
    {
        Node* p = q->Right();
        q->Right(p->Left());
        p->Left(q);

        update_height(q);
        update_height(p);
        return p;
    }

    Node* balance_node(Node* p)
    {
        update_height(p);

        if(balanse_factor(p) == 2)
        {
            if(balanse_factor(p->Right()) < 0 )
            {
                if(p->Left()->Right())
                {
                    p->Right(rotate_node_to_right(p->Right()));
                }
            }
            return rotate_node_to_left(p);
        }

        if(balanse_factor(p) == -2)
        {
            if(balanse_factor(p->Left()) > 0)
            {
                if(p->Right()->Left())
                {
                    p->Left(rotate_node_to_left(p->Left()));
                }
            }
            return rotate_node_to_right(p);
        }

        return p;
    }

    Node* find_min(Node* p)
    {
        Node* t = p;

        while(t->Left())
        {
            t = t->Left();
        }

        return t;
    }

    Node* remove_min(Node* p) // удаление узла с минимальным ключом из дерева p
    {
/*
        class tStack
        {
        private:
            class Element
            {
            public:
                Node* val;
                Element* next;

                Element(Node* val, Element* next) : val(val), next(next) {}
            };

            Element* head;
        public:
            tStack() : head() {}

            bool Empty() { return !head; }

            void Add(Node* val)
            {
                head = new Element(val, head);
            }

            void Get()
            {
                if(!head) throw Exception("empty stack");

                Element* t = head;
                head = head->next;
                Node* res = t->val;
                delete t;
                return res;
            }
        };
*/
        if(!p->Left()) return p->Right();
        p->Left(remove_min(p->Left()));
        return balance_node(p);
    }

public:
    BinaryTree() : head(), cnt(0) {}

    bool Insert(T val)
    {
        if (!head)
        {
            head = new Node(val);
            cnt = 1;
            return true;
        }

        Node* tnode = head;

        while (true)
        {
            if (is_equally(val, tnode->Value())) return false;

            if (is_less(val, tnode->Value()))
            {
                if (!tnode->Left())
                {
                    tnode->Left(new Node(val));
                    cnt++;
                    balance_node(head);
                    return true;
                }

                tnode = tnode->Left();
                continue;
            }

            if (is_more(val, tnode->Value()))
            {
                if (!tnode->Right())
                {
                    tnode->Right(new Node(val));
                    cnt++;
                    balance_node(head);
                    return true;
                }

                tnode = tnode->Right();
                continue;
            }
        }
    }

    bool Remove(T val)
    {
        if(!cnt || !head) return false;
    }

    bool Remove(int k)
    {
        if(!head) return false;
        Node* t = head;

        while(!is_equally(k, t->Value()))
        {
            if(is_less(k, t->Value()))
            {
                if(!t->Left()) return false;
                t = t->Left();
            }
            else
            {
                if(!t->Right()) return false;
                t = t->Right();
            }
        }

        // wtf?
        // Heresy?

        Node* q = t->Left();
        Node* r = t->Right();

        delete t;

        if(!r) return q;

        Node* min = find_min(r);
        min->Right(remove_min(r));
        min->Left(q);
        return balance_node(min);
    }
};

int main()
{
    //freopen("output.txt", "w", stdout);
    cout << "start. \n";

    BinaryTree<int> t;

    t.Insert(1);
    t.Insert(2);
    t.Insert(3);
    t.Insert(4);
    t.Insert(5);

    cout << "\nend.\n";
    return 0;
}