AVL TREE

#include<stdio.h>
#include<stdlib.h>
#define FALSE 0
#define TRUE 1

struct AVLNode{
int data;
int balfact;
struct AVLNode *left;
struct AVLNode *right;
};

struct AVLNode *buildtree(struct AVLNode *root,int data,int *h){
struct AVLNode *node1,*node2;
if(!root){
root=(struct AVLNode *)malloc(sizeof(struct AVLNode));
root->data=data;
root->left=NULL;
root->right=NULL;
root->balfact=0;
*h=TRUE;
return(root);
}
if(data<root->data){
root->left=buildtree(root->left,data,h);
if(*h){
switch(root->balfact){
case 1:
node1=root->left;
if(node1->balfact==1){
printf("\nRight rotation along %d\n",root->data);
root->left=node1->right;
node1->right=root;
root->balfact=0;
root=node1;
}
else{
printf("\nDouble rotation, left along %d\n",node1->data);
node2=node1->right;
node1->right=node2->left;
printf(" then right along %d\n",root->data);
node2->left=node1;
root->left=node2->right;
node2->right=root;
if(node2->balfact==1)
root->balfact=-1;
else
root->balfact=0;
if(node2->balfact==-1)
node1->balfact=1;
else
node1->balfact=0;
root=node2;
}
root->balfact=0;
*h=FALSE;
break;
case 0:
root->balfact=1;
break;
case -1:
root->balfact=0;
*h=FALSE;
}
}
}
if(data>root->data){
root->right=buildtree(root->right,data,h);
if(*h){
switch(root->balfact){
case 1:
root->balfact=0;
*h=FALSE;
break;
case 0:
root->balfact=-1;
break;
case -1:
node1=root->right;
if(node1->balfact==-1){
printf("\nLeft rotation along %d\n",root->data);
root->right=node1->left;
node1->left=root;
root->balfact=0;
root=node1;
}
else{
printf("\nDouble rotation, right along %d\n",node1->data);
node2=node1->left;
node1->left=node2->right;
node2->right=node1;
printf(" then left along %d\n",root->data);
root->right=node2->left;
node2->left=root;
if(node2->balfact==-1)
root->balfact=1;
else
root->balfact=0;
if(node2->balfact==1)
node1->balfact=-1;
else
node1->balfact=0;
root=node2;
}
root->balfact=0;
*h=FALSE;
}
}
}
return(root);
}

void display(struct AVLNode *root){
if(root!=NULL){
display(root->left);
printf("%d\t",root->data);
display(root->right);
}
}

int height(struct AVLNode *root){
int rheight,lheight;
if(root==NULL)
return -1;
else{
rheight=height(root->right);
lheight=height(root->left);
if(rheight>lheight)
return rheight+1;
else
return lheight+1;
}
}

int main(){
system("clear");
struct AVLNode *avl=NULL;
int h;
int i,count,temp;
printf("\n\t\t\t\tAVL TREE\n");
printf("\nEnter the number of nodes:");
scanf("%d",&count);
if(count<=0){
printf("\nValue Invalid\n");
exit(0);
}
for(i=0;i<count;i++){
printf("\nEnter the value of node %d: ",(i+1));
scanf("%d",&temp);
avl=buildtree(avl,temp,&h);
}
printf("\n....................................\n");
printf("\n\nAVL TREE:\n");
display(avl);
printf("\n....................................\n");
printf("\nAVL Tree Height: %d\n\n",height(avl));
printf("\n....................................\n");
return 0;
}

OUTPUT

AVL TREE
Enter the number of nodes : 5
Enter the value of node 1 : 2
Enter the value of node 2 : 1
Enter the value of node 3 : 15
Enter the value of node 4 : 13
Enter the value of node 5 : 14
Double rotation ,left along 13 then right along 15
………………………………………………….
AVL tree 
1 2 13 14 15
………………………………………………….
AVL Tree height : 2
…………………………………………………

 http://commando.co.nf/