#include <iostream>


using namespace std;

int cond = 4;

struct node
{
    int val;
    node* left;
    node* right;
    node* up;
}*root_1=NULL,*root_2=NULL;

node *min(node *root)
{
    while (root->left)
        root = root->left;
    return root;
}

node *max(node *root)
{
    if (!root)
        cout << "Drzewo jest puste!";
    while (root->right)
        root = root->right;
    return root;
}



node *look(node *root, int x)
{
    if (!root)
        cout << "Drzewo jest puste!";
    else
    {
        while ((root) && (root->val != x))
        {
            if (x < root->val)
                root = root->left;
            else
                root = root->right;
        }
        if (!root)
            cout << "Brak takiego elementu!";
    }
    return root;
}

node *next(node *w)
{
    if (w->right)
        return min(w->right);
    node *p = w->up;
    while ((p) && (w == p->right))
    {
        w = p;
        p = p->up;
    }
    return p;
}

node *prev(node *w)
{
    if (!w)
        cout << "Drzewo jest puste!";
    if (w->left)
        return max(w->left);
    node *p = w->up;
    while ((p) && (w == p->left))
    {
        w = p;
        p = p->up;
    }
    return p;
}

void add(node *&root, int x)
{
    node *nowy = new node;
    nowy->right = nowy->left = NULL;
    nowy->val = x;
    node* p = root;
    if (!p)
        root = nowy;
    else
        while (true)
            if (x < p->val)
                if (!p->left)
                {
                    p->left = nowy;
                    break;
                }
                else
                    p = p->left;
            else
            {
                if (!p->right)
                {
                    p->right = nowy;
                    break;
                }
                else
                    p = p->right;
            }
    nowy->up = p;
}

int del(node *&root, node* x)
{
    node *p, *w;
    int k = x->val;
    if ((!x->left) || (!x->right))
        p = x;
        else
            p = next(x);
        if (p->left)
            w = p->left;
        else
            w = p->right;
        if (w)
            w->up = p->up;

        if (!p->up) root = w;
        else if (p == p->up->left) p->up->left = w;
        else p->up->right = w;
        if (p != x) x->val = p->val;

        delete p;
        return k;
}


void modify(node*& root_1, node*& root_2, node *x_2, int cond)
{
    if (x_2->val == cond)
    {
        add(root_1, del(root_2, next(x_2)));
    }
}

void inorder1(node*& root_1, node*& root_2, node* x_2, int cond)
{
    if (!x_2)return;
    if (x_2->left)
        inorder1(root_1,root_2,x_2->left, cond);
    modify(root_1, root_2, x_2, cond);
    if (x_2->right)
        inorder1(root_1, root_2, x_2->right, cond);
}

void inorder(node* root)
{
    if (!root)return;
    if (root->left)
        inorder(root->left);
    cout << root->val << " ";
    if (root->right)
        inorder(root->right);
}


void main()
{
    add(root_1, 3);
    add(root_1, 7);
    add(root_1, 5);
    add(root_2, 2);
    add(root_2, 6);
    add(root_2, 4);
    add(root_2, 1);
    add(root_2, 8);

    inorder(root_1);
    cout << endl;
    inorder(root_2);

    cout << endl;

    node*x = root_2;
    inorder1(root_1,root_2,x,cond);
    inorder(root_1);
    cout << endl;
    inorder(root_2);

    system("PAUSE");

}