node *create_node(int val)

{

    node *pNew = new node;

    pNew->val = val;

    pNew->ht  = ;

    pNew->left = pNew->right = nullptr;

    return pNew;

}

int height(node *p)

{

    if(!p) return -;

    return p->ht;

}

int get_height(node *p)

{

    if (!p) return ;

    return  + max(height(p->left), height(p->right));

}

node *right_rotate(node *p)

{

    node *pOrigRoot = p;

    node *root = p->left;

    pOrigRoot->left = root->right;

    root->right = pOrigRoot;

    pOrigRoot->ht = get_height(pOrigRoot);

    root->ht = get_height(root);

    return root;

}

node *left_rotate(node *p)

{

    node *pOrigRoot = p;

    node *root = p->right;

    pOrigRoot->right = root->left;

    root->left = pOrigRoot;

    pOrigRoot->ht = get_height(pOrigRoot);

    root->ht = get_height(root);

    return root;

}

int balance_factor(node *p)

{

    if (!p) return ;

    return height(p->left) - height(p->right);

}

node *balance(node *p)

{

    int w = balance_factor(p);

    if (!p || abs(w) < )

        return p;

    if (w > )

    {

        if(balance_factor(p->left) < )

        {

            p->left = left_rotate(p->left);

        }

        return right_rotate(p);

    }

    else

    {

        if(balance_factor(p->right) > )

        {

            p->right = right_rotate(p->right);

        }

        return left_rotate(p);

    }

    return p;

}

node * insert(node * root,int val)

{

    if (val < root->val)

    {

        if(!root->left)

        {

            root->left = create_node(val);

        }

        else

        {

            root->left = insert(root->left, val);

        }

    }

    else

    {

        if(!root->right)

        {

            root->right = create_node(val);

        }

        else

        {

            root->right = insert(root->right, val);

        }

    }

    root->ht = get_height(root);

    return balance(root);

}