#include <iostream>
using namespace std;
struct node{
int key;
struct node* left;
struct node* right;
int height;
};
int getheight(struct node* n){
if(n=NULL)
return 0;
return n->height;
}
struct node* createnode( int key){
struct node* newnode= new node;
newnode ->key = key;
newnode->left=NULL;
newnode->right=NULL;
newnode->height=1;
return newnode;
}
int max (int a,int b){
return (a>b)?a:b;
}
int getBalanceFactor(struct node* n){
if(n=NULL){
return 0;
}
return getheight(n->left) - getheight(n->right);
}
struct node* rightRotate(struct node* y){
struct node* x=y->left;
struct node* T2=x->right;
x->right=y;
y->left=T2;
x->height =max(getheight(x->right), getheight(x->left))+1;
y->height =max(getheight(y->right), getheight(y->left))+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;
x->height =max(getheight(x->right), getheight(x->left))+1;
y->height =max(getheight(y->right), getheight(y->left))+1;
return y;
}
struct node* insert(struct node* node , int key){
if(node==NULL)
return createnode(key);
if(key < node->key)
node->left = insert(node->left, key);
if(key > node->key)
node->right = insert(node->right, key);
node->height = 1 + max(getheight(node->left), getheight(node->right));
int bf =getBalanceFactor(node);
//left left case
if(bf>1 && key<node->left->key){
return rightRotate(node);
}
// right right case
if(bf<-1 && key>node->right->key){
return leftRotate(node);
}
// left right case
if(bf>1 && key>node->left->key){
node->left=leftRotate(node->left);
return rightRotate(node);
}
// right left case
if(bf<-1 && key>node->right->key){
node->right=rightRotate(node->right);
return leftRotate(node);
}
return node;
}
void inorder(struct node* root){
if(root!=NULL){
inorder(root->left);
cout<<" "<<root->key;
inorder(root->right);
}
}
int main(){
struct node* root = NULL;
root = insert(root, 60);
root = insert(root, 3);
root = insert(root, 77);
root = insert(root, 55);
root = insert(root, 1);
root = insert(root, 10);
inorder(root);
return 0;
}