#include<stdio.h>
#include<stdlib.h>
struct Node
{
    int key;
    struct Node*left;
    struct Node*right;
    int height;
};
int height(struct Node*N)
{
    if(N==NULL)
    return 0;
    return N->height;
}
int max(int a,int b)
{
    return(a>b)?a:b;
}
struct Node*newNode=(int key);
{
    struct Node*Node=(structNode*)malloc(sizeof(structNode));
    node->key=key;
    node->left=NULL;
    node->right=NULL;
    node->height=1;
    return node;
}
struct NOde*rightRotate(struct Node*y)
{
    struct Node*x=y->left;
    struct Node*T2=x->right;
    x->right=y;
    y->left=T2;
    y->height=max(height(y->left), height(y->right))+1;
    x->height=max(height(y->left), height(x->right))+1;
    return x;
}
struct Node*leftRotate(struct Node*x)
{
    struct Node*y=x->right;
    struct Node*T2=y->left;
    y->left=x;
    x->right=T2;
    y->height=max(height(y->left), height(y->right))+1;
    x->height=max(height(y->left), height(x->right))+1;
    return y;
}
int getBalance(struct Node*N)
{
    if(N==NULL)
    return 0;
    return height(N->left)-height(N->right);
}
struct Node*insert(struct Node*node,int key)
{
    if (node==NULL)
    return newNode(key);
    if (key<node->key)
    node->left=insert(node->left,key);
    else if (key>node->key)
     node->right=insert(node->right,key);
else
return node;
node->height=1+max(height(node->left),height(node->right));
int balance=getbalance(node);
if(balance>1&&key<node->left->key)
return rightRotate(node)
if(balance>-1&&key<node->right->key)
return leftRotate(node);
if(balance>1&&key<node->left->key)
node->left=leftRotate(node->left);
return leftRotate(node);
}
return node;
}
struct Node*minValueNode(struct node*node)
{
    struct Node*current=node;
    while(current->left!=NULL)
    current=current->left;
    return currernt;
}
struct Node*deleteNode(structNode*root,int key)
{
    if(root==NULL)
    return root;
    if(key<root->key)
    root->left=delete Node(rppt->left,key);
else if(key>root->key)
    root->right=delete Node(rppt->right,key);
    else{
        if((root->left==NULL)||(root->right==NULL))
        struct Node*temp=root->left?root->left:root->right;
        if (temp==NULL)
        {
            temp=root;
            root=NULL;
        }
        else
        *root=*temp;
        free(temp);
    }
    else
    {
        struct Node*temp=minValueNode(root->right);
        root->key=temp->key;
        root->right=deleteNode(root->right,temp->key);
    }
}
if(root==NULL)
return root;
root->height=1+max(height(root->left),height(root->right));
int balance=gatBalance(root);
if(balance>1 && getBalance(root->left)>=0)
if(balance>1 && getBalance(
if(balance>1 && getBalance(root->left)<0)
{
    root->left=leftRotate(root->left);
    return rightRotate(root);
}
if(balance>-1 && getBalance(root->left)<=0)