#include <iostream>
#include <cmath>
#include <ctime>
using namespace std;
template <typename T> class Tree
{
public:
    struct Node
    {
        T Key;
        Node* Parent;
        Node* Left;
        Node* Right;
    }* root;
private:
    Node* SearchNext(Node* start, T Key)
    {
        Node* res = NULL;
        if(start != NULL){
            if(start->Key < Key)
            {
                res = start->Right;
            }
            if(start->Key >= Key)
            {
                res = start->Left;
            }
        }
        return res;
    }
    void Vis(Node* nd)
    {
       cout << nd->Key << " ";
       if(nd->Left != NULL)
       {
           Vis(nd->Left);
       }
       if(nd->Right != NULL)
       {
           Vis(nd->Right);
       }
    }
public:
    Tree(T Key)
    {
        root = new Node();
        root->Key = Key;
        root->Parent = NULL;
        root->Left = NULL;
        root->Right = NULL;
    }
    void Add(T Key)
    {
        Node* now = root;
        Node* tmp = SearchNext(now, Key);
        while(tmp != NULL)
        {
            now = tmp;
            tmp = SearchNext(now, Key);
        }
        tmp = new Node();
        tmp->Key = Key;
        tmp->Parent = now;
        if(now->Key < tmp->Key)
        {
            now->Right = tmp;
        }
        else
        {
            now->Left = tmp;
        }
    }
    Node* Min()
    {
        Node* now = root;
        Node* tmp = now->Left;
        while(tmp != NULL)
        {
            now = tmp;
            tmp = now->Left;
        }
        return now;
    }
    Node* Max()
    {
        Node* now = root;
        Node* tmp = now->Right;
        while(tmp != NULL)
        {
            now = tmp;
            tmp = now->Right;
        }
        return now;
    }
    Node* Search(T Key)
    {
        Node* now = root;
        Node* tmp = SearchNext(now, Key);
        while(tmp != NULL && now->Key != Key)
        {
            now = tmp;
            tmp = SearchNext(now, Key);
        }
        if(now->Key == Key)
        {
            return now;
        }
        return NULL;
    }
    void Remove(T Key)
    {
        Node* now = root;
        Node* tmp = SearchNext(now, Key);
        while(tmp != NULL && now->Key != Key)
        {
            now = tmp;
            tmp = SearchNext(now, Key);
        }
        if(now->Key != Key)
        {
            printf("Key is not found!\n");
            return;
        }
        Node* parent = now->Parent;
        if(now->Left == NULL && now->Right == NULL)
        {
            if(parent != NULL && parent->Left == now)
            {
                parent->Left = NULL;
            }
            if(parent != NULL && parent->Right == now)
            {
                parent->Right = NULL;
            }
            delete now;
            printf("Key is deleted!\n");
            return;
        }
        if(now->Left == NULL)
        {
            if(parent != NULL && parent->Left == now)
            {
                parent->Left = now->Right;
            }
            if(parent != NULL && parent->Right == now)
            {
                parent->Right = now->Right;
            }
            Node* next = now->Right;
            next->Parent = parent;
            delete now;
            printf("Key is deleted!\n");
            return;
        }
        if(now->Right == NULL)
        {
            if(parent != NULL && parent->Left == now)
            {
                parent->Left = now->Left;
            }
            if(parent != NULL && parent->Right == now)
            {
                parent->Right = now->Left;
            }
            Node* next = now->Left;
            next->Parent = parent;
            delete now;
            printf("Key is deleted!\n");
            return;
        }
        tmp = now->Right;
        while(tmp->Left != NULL)
        {
            tmp = tmp->Left;
        }
        Node* t = tmp->Parent;
        if(t->Right != tmp)
        {
            t->Left = tmp->Right;
        }
        if(parent != NULL && parent->Left == now)
        {
            parent->Left = tmp;
        }
        if(parent != NULL && parent->Right == now)
        {
            parent->Right = tmp;
        }
        tmp->Left = now->Left;
        t = tmp->Left;
        t->Parent = tmp;
        if(now->Right == tmp)
        {
            tmp->Right = NULL;
        }
        else
        {
            tmp->Right = now->Right;
        }
        if(root == now)
        {
            root = tmp;
            tmp->Parent = NULL;
        }
        delete now;
        printf("Key is deleted!\n");
    }
    Node* Earlier(int key)
    {
        Node* n = Search(key);
        if(n == NULL)
        {
            return ((typename Tree<T>::Node*)-1);
        }
        else
        {
            return n->Parent;
        }
    }
    void Visual()
    {
        Vis(root);
    }
};
void AutoStart()
{
    srand(time(NULL));
    int num = 1;
    int t = 0;
    t = - 25 + rand() % 50;
    cout << "Input 1 element>" << t << "\n";
    Tree<int>* tr = new Tree<int>(t);
    for(num; num < 10;)
    {
        t = - 25 + rand() % 50;
        cout << "Input " << ++num << " element>" << t << "\n";
        tr->Add(t);
    }
    tr->Visual();
    cin.get();
    cout << "Task 1. Search of element.\n";
    Tree<int>::Node* n;
    cout << "Input key of node>";
    cin >> t;
    n = tr->Search(t);
    if(n == NULL)
    {
        cout << "Node with key " << t << " was not found.\n";
    }
    else
    {
        cout << "Address of node with key " << t << " is " << n << "\n";
    }
    cout << "Task 2. Min and Max elements.\n";
    n = tr->Min();
    cout << "Min element on address " << n << " has key " << n->Key << "\n";
    cin.get();
    n = tr->Max();
    cout << "Max element on address " << n << " has key " << n->Key << "\n";
    cin.get();
    cout << "Task 3. Parent element.\n";
    cout << "Input key of node>";
    cin >> t;
    n = tr->Earlier(t);
    if(n == (Tree<int>::Node*)-1)
    {
        cout << "Node with key " << t << " was not found.\n";
    }
    if(n == NULL)
    {
        cout << "Node with key " << t << " has no parent. It is root.\n";
    }
    if(n != NULL && n != (Tree<int>::Node*)-1)
    {
        cout << "Address of parent node with key " << t << " is " << n << " it has key " << n->Key << "\n";
    }
    cout << "Task 4. Remove element.\n";
    cout << "Input key of node>";
    cin >> t;
    tr->Remove(t);
    tr->Visual();
    cin.get();
    cin.get();
}
int _tmain(int argc, char* argv[])
{
    AutoStart();
    return 0;
}