#define max(a, b) ( (a) > (b) ? (a) : (b) )
#define geth(n) ( n->h = 1 + max(n->l->h, n->r->h) )

struct node
{
    int key;
    int h; /// height
    node *l, *r; /// left, right
} *Root, *NIL;

void Initize_AVL()
{
    NIL = new node;
    NIL->key = NIL->h = 0,
        NIL->l = NIL->r = NULL;
    Root = NIL;
}

node* rotleft(node* n)
{
    node *t = n->r;

    n->r = t->l, t->l = n;
                      geth(n), geth(t);
    return t;
}

node* rotright(node* n)
{
    node* t = n->l;

    n->l = t->r, t->r = n,
                      geth(n), geth(t);
    return t;
}

node* balance(node* n)
{
    geth(n);

    if( n->l->h > n->r->h + 1 )
    {
        if( n->l->r->h > n->l->l->h ) /// rotatie dubla dreapta
            n->l = rotleft( n->l );

        n = rotright(n);
    }

    if( n->r->h > n->l->h + 1 )
    {
        if( n->r->l->h > n->r->r->h ) /// rotatie dubla stanga
            n->r = rotright( n->r );

        n = rotleft(n);
    }

    return n;
}

node* insert_node(node *n, int key)
{
    if( n == NIL )
    {
        n = new node;
        n->key = key, n->h = 1,
                 n->l = n->r = NIL;
        return n;
    }
    else
    {
        if( n->key == key )
            return n;
        else
        {
            if( n->key > key )
               n->l = insert_node(n->l, key);
            else
               n->r = insert_node(n->r, key);
        }
    }
    return balance(n);
}

node* delete_node(node* n, int key)
{
    node* t;

    if( n == NIL )
        return n;

    if( n->key == key )
    {
            if( n->l == NIL || n->r == NIL )
            {
                t = ( n->l != NIL )? n->l : n->r;
                delete n;
                return t;
            }
            else
            {
                for(t = n->r ; t->l != NIL; t = t->l);
                    n->key = t->key;
                n->r = delete_node(n->r, n->key);

                return balance(n);
            }
    }
    else
    {
        if( n->key > key )
            n->l = delete_node(n->l, key);
        else
            n->r = delete_node(n->r, key);
    }
    return balance(n);
}

bool search_node(node *n, int key)
{
    if( n == NIL )  return false;
    if( n->key == key )  return true;
    else
    {
        if( n->key > key )
            return search_node(n->l, key);
        else
            return search_node(n->r, key);
    }
}