#include<stdio.h>
#include<stdlib.h>
int kk;
typedef struct node{
int key;
int height;
struct node * left;
struct node * right;
}node;
node * create(node * n,int k)
{ n=(node *)malloc(sizeof(node));
kk=k;
n->key=k;
n->height=1;
n->left=NULL;
n->right=NULL;
return n;
}
int max(int a,int b){return (a<b)?b:a;}
node *updateheight(node *n )
{
if(n->left!=NULL&&n->right!=NULL)
{n->height=max(n->left->height,n->right->height)+1;printf("height updated\n");}
else if(n->left!=NULL)
{n->height=n->left->height;printf("height updated\n");}
else if(n->right!=NULL)
{n->height=n->right->height;printf("height updated\n");}
else
n->height=1;
return n;
}
node * rotateR(node * r)
{
node *n=r->left;
node *temp;
if(r->left->right!=NULL)
temp=r->left->right;
else temp=NULL;
n->right=r;
r->left=temp;
if(n->right!=NULL)
n->right=updateheight(n->right);
n=updateheight(n);
printf(".R.");
return n;
}
node * rotateL(node * r)
{ node *n=r->right;
node *temp;
if(r->right->left!=NULL)
temp=r->right->left;
else temp =NULL;
n->left=r;
r->right=temp;
updateheight(n->left);
updateheight(n);
printf(".L.");
return n;
}
node * balance(node *n,int k)
{ int balance,l=0,r=0;
if(n->left)
l=n->left->height;
if(n->right)
r=n->right->height;
balance=l-r;
if(balance>1&&k<=n->left->key)
{n=rotateR(n);printf("LL..");}
else if(balance>1&&k>n->left->key)
{printf("LR..");n=rotateL(n);n=rotateR(n);}
else if(balance<-1&&k>n->right->key)
{n=rotateL(n);printf("RR..");}
else if(balance<-1&&k<=n->left->key)
{n=rotateR(n);n=rotateL(n);printf("RL..");}
return n;
}
node * insert(node * r,int k)
{
if(r==NULL){node *n=create(n,k);r=n;}
else if(k<=r->key){r->left=insert(r->left,k);r->height=r->left->height+1;r=balance(r,kk);}
else if(k>r->key){r->right=insert(r->right,k);r->height=r->right->height+1;r=balance(r,kk);}
return r;
}
void printAVLIO(node *r)
{
if(!r)return;
if(r->left)printAVLIO(r->left);
printf("\n%d..",r->key);
printf(".height.%d..\n",r->height);
if(r->right)printAVLIO(r->right);
}
int main()
{
node *root=NULL;
int i,a[]={50,25,75,70,60},k=sizeof(a)/sizeof(int);
printf("Inseting sequence into the AVL tree\n");
for(i=0;i<k;i++)
printf("%d..",a[i]);printf("\n");
i=0;
while(i<k)
{root=insert(root,a[i]);i++;}
printAVLIO(root);
return 0;
}
#include<stdlib.h>
int kk;
typedef struct node{
int key;
int height;
struct node * left;
struct node * right;
}node;
node * create(node * n,int k)
{ n=(node *)malloc(sizeof(node));
kk=k;
n->key=k;
n->height=1;
n->left=NULL;
n->right=NULL;
return n;
}
int max(int a,int b){return (a<b)?b:a;}
node *updateheight(node *n )
{
if(n->left!=NULL&&n->right!=NULL)
{n->height=max(n->left->height,n->right->height)+1;printf("height updated\n");}
else if(n->left!=NULL)
{n->height=n->left->height;printf("height updated\n");}
else if(n->right!=NULL)
{n->height=n->right->height;printf("height updated\n");}
else
n->height=1;
return n;
}
node * rotateR(node * r)
{
node *n=r->left;
node *temp;
if(r->left->right!=NULL)
temp=r->left->right;
else temp=NULL;
n->right=r;
r->left=temp;
if(n->right!=NULL)
n->right=updateheight(n->right);
n=updateheight(n);
printf(".R.");
return n;
}
node * rotateL(node * r)
{ node *n=r->right;
node *temp;
if(r->right->left!=NULL)
temp=r->right->left;
else temp =NULL;
n->left=r;
r->right=temp;
updateheight(n->left);
updateheight(n);
printf(".L.");
return n;
}
node * balance(node *n,int k)
{ int balance,l=0,r=0;
if(n->left)
l=n->left->height;
if(n->right)
r=n->right->height;
balance=l-r;
if(balance>1&&k<=n->left->key)
{n=rotateR(n);printf("LL..");}
else if(balance>1&&k>n->left->key)
{printf("LR..");n=rotateL(n);n=rotateR(n);}
else if(balance<-1&&k>n->right->key)
{n=rotateL(n);printf("RR..");}
else if(balance<-1&&k<=n->left->key)
{n=rotateR(n);n=rotateL(n);printf("RL..");}
return n;
}
node * insert(node * r,int k)
{
if(r==NULL){node *n=create(n,k);r=n;}
else if(k<=r->key){r->left=insert(r->left,k);r->height=r->left->height+1;r=balance(r,kk);}
else if(k>r->key){r->right=insert(r->right,k);r->height=r->right->height+1;r=balance(r,kk);}
return r;
}
void printAVLIO(node *r)
{
if(!r)return;
if(r->left)printAVLIO(r->left);
printf("\n%d..",r->key);
printf(".height.%d..\n",r->height);
if(r->right)printAVLIO(r->right);
}
int main()
{
node *root=NULL;
int i,a[]={50,25,75,70,60},k=sizeof(a)/sizeof(int);
printf("Inseting sequence into the AVL tree\n");
for(i=0;i<k;i++)
printf("%d..",a[i]);printf("\n");
i=0;
while(i<k)
{root=insert(root,a[i]);i++;}
printAVLIO(root);
return 0;
}