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

node *poprzednik(node *T)
{
    if (!T)
        cout << "BRAK ELEMENTU"<<endl;
    if (T->left)
        return max(T->left);
    node *p = T->parent;
    while ((p) && (T == p->left))
    {
        T = p;
        p = p->parent;
    }
    return p;
}

node *nastepnik(node *T)
{
    if (!T)
        cout << "BRAK ELEMENTU"<<endl;
    if (T->right)
        return min(T->right);
    node* p = T->parent;
    while ((p) && (T = p->right))
    {
        T = p;
        p = p->parent;
    }
    return p;
}

void delete(node*&root, int k) {
    node*usuwacz = nastepnik(w);
    if (usuwacz)
    {
        if ((usuwacz->left) && (usuwacz->right))
        {
            node*pre = poprzednik(usuwacz);
            usuwacz->val = pre->val;
            if (pre->up->left == pre)
                pre->up->left = pre->left;
            else
                pre->up->right = pre->left;
            delete pre;
        }
        else
        {
            node* poddrzewo = usuwacz->left ? usuwacz->left : usuwacz->right;

            if (usuwacz->up)
            {
                if (usuwacz->up->left == usuwacz)
                    usuwacz->up->left = poddrzewo;
                else
                    usuwacz->up->right = poddrzewo;

                if (poddrzewo)
                    poddrzewo->up = usuwacz->up;
            }
            else
            {
                poddrzewo->up = NULL;
                root = poddrzewo;
            }
            delete usuwacz;
        }
    }
    }