Ads
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111
#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);
}
C
INFO