0
2.7kviews
Write a menu-driven C program for the AVL Tree operations.
• The Create operation creates the AVL Tree.

• The Insert operation adds the new element to the constructed AVL Tree.

• The Delete operation deletes the element from the constructed AVL Tree.

• The Print operation prints the Pre-order and In-order sequence of constructed AVL Tree along with the Balance Factor (BF) for each node in the AVL Tree.

Test the Program for the following scenarios:

1] Construct the AVL Tree for the data = 10 15 9 12 13 79 45 36 22

2] Insert the new element 17 to the constructed AVL Tree.

3] Delete element 45 from the constructed AVL Tree.

4] Delete the Root element 13 from the constructed AVL Tree.

1
69views

## Menu-driven Program for the AVL Tree

#include<conio.h>
#include<stdio.h>
#include<stdlib.h>

typedef struct node
{  int data;
struct node *left,*right;
int ht;
}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 *);

void main()
{
node *root=NULL;
int x,n,i,op;
do
{
printf("\n");
printf("\n1) Create the AVL Tree");
printf("\n2) Insert Element into the AVL Tree");
printf("\n3) Delete Element from the AVL Tree ");
printf("\n4) Print the AVL Tree");
printf("\n5) Quit");
scanf("%d",&op);
switch(op)
{
case 1:printf("\nEnter Total Number of Elements in the AVL Tree: ");
scanf("%d",&n);
printf("\n Enter AVL Tree Elements: ");
root=NULL;
for(i=0;i<n;i++)
{
scanf("%d",&x);
root=insert(root,x);
}
break;
case 2:printf("\nEnter a Element to Insert in the AVL Tree: ");
scanf("%d",&x);
root=insert(root,x);
break;
case 3:printf("\nEnter a Element to Delete from the AVL Tree: ");
scanf("%d",&x);
root=Delete(root,x);
break;
case 4:    printf("\nPreorder Sequence of the AVL Tree:\n");
preorder(root);
printf("\nInorder sequence of the AVL Tree:\n");
inorder(root);
break;
}
}while(op!=5);
}

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
{
// Element to be deleted is found
if(T->right !=NULL)
{  // Delete its inorder succesor
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)
{
int lh,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)
{
int lh,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);
}
}

void inorder(node *T)
{
if(T!=NULL)
{
inorder(T->left);
printf(" %d(Bf=%d)",T->data,BF(T));
inorder(T->right);
}
}


OUTPUT -

1] Construction of the AVL Tree for the data = 10 15 9 12 13 79 45 36 22

The AVL Tree for the above data looks as follows:

The program shows the output of AVL Tree creation as follows:

2] Insert the new element 17 to the constructed AVL Tree.

Insertion of the new element 17 to the constructed AVL Tree is done as follows;

The program shows the output of AVL Tree insertion as follows:

3] Delete element 45 from the constructed AVL Tree.

Deletion of element 45 from the constructed AVL Tree is done as follows;

The program shows the output of AVL Tree Deletion as follows:

4] Delete the Root element 13 from the constructed AVL Tree.

Deletion of Root element 13 from the constructed AVL Tree is done as follows;

The program shows the output of AVL Tree Deletion as follows: