#include<stdio.h> #include<stdlib.h> struct node { int key; struct node *left; struct node *right; int h; }; struct node *root=NULL; int l,r; int max(int a,int b) { int c; c= a>b? a:b; return c; } int height(struct node *n) { if(n==NULL) return -1; l=height(n->left); r=height(n->right); return 1+max(l,r); } struct node*leftrotate(struct node *x) { struct node *y=x->right; struct node *t=y->left; y->left=x; x->right=t; x->h=height(x); y->h=height(y); return y; } struct node*rightrotate(struct node *y) { struct node *x=y->left; struct node *t=x->right; x->right=y; y->left=t; x->h=height(x); y->h=height(y); return x; } struct node *insert(struct node *n,int k) { int b; if(n==NULL) { n=(struct node*)malloc(sizeof(struct node)); n->left=NULL; n->right=NULL; n->key=k; n->h=0; return n; } if(k < n->key) n->left=insert(n->left,k); else if(k>n->key) n->right=insert(n->right,k); n->h=height(n); b=height(n->left)-height(n->right); if(b>1 && k<n->left->key) return rightrotate(n); if(b>1 && k>n->left->key) { n->left=leftrotate(n->left); return rightrotate(n); } if(b<-1 && k>n->right->key) return leftrotate(n); if(b<-1 && k<n->right->key) { n->right=rightrotate(n->right); return leftrotate(n); } return n; } void preorder(struct node *t) { if(t!=NULL) { printf("%d-->%d ",t->key,t->h); preorder(t->left); preorder(t->right); } } int main() { int n,i,k; printf("enter n value"); scanf("%d",&n); printf("enter %d values",n); for(i=0;i<n;i++) { scanf("%d",&k); root=insert(root,k); } preorder(root); }