Thursday, February 12, 2015
C Program for AVL Tree Implementation
An AVL (Adelson-Velskii and Landis) tree is a height balance tree. These trees are binary search trees in which the height of two siblings are not permitted to differ by more than one.
i.e. [Height of the left subtree – Height of right subtree] <= 1.
A C program is given below which performs various operations like creation, insertion, deletion and printing for an AVL tree.
Also Read: C Program to Create a Binary Tree Using Recursion [Linked Representation]
Also Read: What is Quick Sort? Algorithm and C Program to Implement Quick Sort
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
typedefstruct node
{ int data;
struct node *left,*right;
intht;
}node;
node *insert(node *,int);
node *Delete(node *,int);
void preorder(node *);
void inorder(node *);
int height( node *);
node *rotateright(node *);
node *rotateleft(node *);
node *RR(node *);
node *LL(node *);
node *LR(node *);
node *RL(node *);
int BF(node *);
int main()
{
node *root=NULL;
intx,n,i,op;
do
{
printf("
1)Create:");
1)Create:");
printf("
2)Insert:");
2)Insert:");
printf("
3)Delete:");
3)Delete:");
printf("
4)Print:");
4)Print:");
printf("
5)Quit:");
5)Quit:");
printf("
Enter Your Choice:");
Enter Your Choice:");
scanf("%d",&op);
switch(op)
{
case 1:printf("
Enter no. of elements:");
Enter no. of elements:");
scanf("%d",&n);
printf("
Enter tree data:");
Enter tree data:");
root=NULL;
for(i=0;i<n;i++)
{
scanf("%d",&x);
root=insert(root,x);
}
break;
case 2:printf("
Enter a data:");
Enter a data:");
scanf("%d",&x);
root=insert(root,x);
break;
case 3:printf("
Enter a data:");
Enter a data:");
scanf("%d",&x);
root=Delete(root,x);
break;
case 4: printf("
Preorder sequence:
");
Preorder sequence:
");
preorder(root);
printf("
Inorder sequence:
");
Inorder sequence:
");
inorder(root);
printf("
");
");
break;
}
}while(op!=5);
return 0;
}
node * insert(node *T,int x)
{
if(T==NULL)
{
T=(node*)malloc(sizeof(node));
T->data=x;
T->left=NULL;
T->right=NULL;
}
else
if(x > T->data) // insert in right subtree
{
T->right=insert(T->right,x);
if(BF(T)==-2)
if(x>T->right->data)
T=RR(T);
else
T=RL(T);
}
else
if(x<T->data)
{
T->left=insert(T->left,x);
if(BF(T)==2)
if(x < T->left->data)
T=LL(T);
else
T=LR(T);
}
T->ht=height(T);
return(T);
}
node * Delete(node *T,int x)
{ node *p;
if(T==NULL)
{
return NULL;
}
else
if(x > T->data) // insert in right subtree
{
T->right=Delete(T->right,x);
if(BF(T)==2)
if(BF(T->left)>=0)
T=LL(T);
else
T=LR(T);
}
else
if(x<T->data)
{
T->left=Delete(T->left,x);
if(BF(T)==-2)//Rebalance during windup
if(BF(T->right)<=0)
T=RR(T);
else
T=RL(T);
}
else
{
//data to be deleted is found
if(T->right !=NULL)
{ //delete its inordersuccesor
p=T->right;
while(p->left != NULL)
p=p->left;
T->data=p->data;
T->right=Delete(T->right,p->data);
if(BF(T)==2)//Rebalance during windup
if(BF(T->left)>=0)
T=LL(T);
else
T=LR(T);
}
else
return(T->left);
}
T->ht=height(T);
return(T);
}
int height(node *T)
{
intlh,rh;
if(T==NULL)
return(0);
if(T->left==NULL)
lh=0;
else
lh=1+T->left->ht;
if(T->right==NULL)
rh=0;
else
rh=1+T->right->ht;
if(lh>rh)
return(lh);
return(rh);
}
node * rotateright(node *x)
{
node *y;
y=x->left;
x->left=y->right;
y->right=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}
node * rotateleft(node *x)
{
node *y;
y=x->right;
x->right=y->left;
y->left=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}
node * RR(node *T)
{
T=rotateleft(T);
return(T);
}
node * LL(node *T)
{
T=rotateright(T);
return(T);
}
node * LR(node *T)
{
T->left=rotateleft(T->left);
T=rotateright(T);
return(T);
}
node * RL(node *T)
{
T->right=rotateright(T->right);
T=rotateleft(T);
return(T);
}
int BF(node *T)
{
intlh,rh;
if(T==NULL)
return(0);
if(T->left==NULL)
lh=0;
else
lh=1+T->left->ht;
if(T->right==NULL)
rh=0;
else
rh=1+T->right->ht;
return(lh-rh);
}
void preorder(node *T)
{
if(T!=NULL)
{
printf("%d(Bf=%d) ",T->data,BF(T));
preorder(T->left);
preorder(T->right);
}
}
voidinorder(node *T)
{
if(T!=NULL)
{
inorder(T->left);
printf("%d(Bf=%d) ",T->data,BF(T));
inorder(T->right);
}
}
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.