//EX: 1
C Program to insert and delete elements in an AVL Tree 1
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#define FALSE 0
#define TRUE 1
struct AVLNode
{
int data;
int balfact;
struct AVLNode *left;
struct AVLNode *right;
};
struct AVLNode * insert(struct AVLNode *,int,int *);
struct AVLNode * deldata(struct AVLNode *,int,int *);
struct AVLNode * del(struct AVLNode *,struct AVLNode *,int *);
struct AVLNode * balr(struct AVLNode *,int *);
struct AVLNode * ball(struct AVLNode *,int *);
void display(struct AVLNode *);
void deltree(struct AVLNode *);
void main()
{
struct AVLNode *avl=NULL;
int h;
clrscr();
avl=insert(avl,20,&h);
avl=insert(avl,6,&h);
avl=insert(avl,29,&h);
avl=insert(avl,5,&h);
avl=insert(avl,12,&h);
avl=insert(avl,25,&h);
avl=insert(avl,32,&h);
avl=insert(avl,10,&h);
avl=insert(avl,15,&h);
avl=insert(avl,27,&h);
// avl=insert(avl,13,&h);
printf("\n AVL Tree : \n");
display(avl);
avl=deldata(avl,5,&h);
avl=deldata(avl,12,&h);
printf("\n AVL tree after deletion of a node : \n");
display(avl);
deltree(avl);
getch();
}
/* Inserts an element intp tree */
struct AVLNode * insert(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=insert(root->left,data,h);
/* If left subtree is higher */
if(*h)
{
switch(root->balfact)
{
case 1:
node1=root->left;
if(node1->balfact==1)
{
printf("\n Right Rotation alond %d. ",root->data);
root->left=node1->right;
node1->right=root;
root->balfact=0;
root=node1;
}
else
{
printf("\n Double rotation , left along %d",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=insert(root->right,data,h);
/* If the right subtree is higher */
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("\n Left rotation along %d. ",root->data);
root->right=node1->left;
node1->left=root;
root->balfact=0;
root=node1;
}
else
{
printf("\n Double rotation , right along %d",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);
}
/* Deletes an item from the tree */
struct AVLNode * deldata(struct AVLNode *root,int data,int *h)
{
struct AVLNode *node;
if(!root)
{
printf("\n No such data. ");
return (root);
}
else
{
if(data < root->data)
{
root->left=deldata(root->left,data,h);
if(*h)
root=balr(root,h);
}
else
{
if(data > root->data)
{
root->right=deldata(root->right,data,h);
if(*h)
root=ball(root,h);
}
else
{
node=root;
if(node->right==NULL)
{
root=node->left;
*h=TRUE;
free(node);
}
else
{
node->right=del(node->right,node,h);
if(*h)
root=ball(root,h);
}
}
}
}
return(root);
}
struct AVLNode * del(struct AVLNode *succ,struct AVLNode *node,int *h)
{
struct AVLNode *temp=succ;
if(succ->left!=NULL)
{
succ->left=del(succ->left,node,h);
if(*h)
succ=balr(succ,h);
}
else
{
temp=succ;
node->data=succ->data;
succ=succ->right;
free(temp);
*h=TRUE;
}
return(succ);
}
/* Balance the tree , if right subtree is higher */
struct AVLNode * balr(struct AVLNode *root,int *h)
{
struct AVLNode *node1,*node2;
switch(root->balfact)
{
case 1:
root->balfact=0;
break;
case 0:
root->balfact=-1;
*h=FALSE;
break;
case -1:
node1=root->right;
if(node1->balfact <= 0)
{
printf("\n Left rotation along %d. ",root->data);
root->right=node1->left;
node1->left=root;
if(node1->balfact==0)
{
root->balfact=-1;
node1->balfact=1;
*h=FALSE;
}
else
{
root->balfact=node1->balfact=0;
}
root=node1;
}
else
{
printf("\n Double rotation , right along %d ",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;
node2->balfact=0;
}
}
return (root);
}
/* Balances the tree , if the left subtree is higher */
struct AVLNode * ball(struct AVLNode * root,int *h)
{
struct AVLNode *node1,*node2;
switch(root->balfact)
{
case -1:
root->balfact=0;
break;
case 0:
root->balfact=1;
*h=FALSE;
break;
case 1:
node1=root->left;
if(node1->balfact >= 0)
{
printf("]n Right rotation along %d. ",root->data);
root->left=node1->right;
node1->right=root;
if(node1->balfact==0)
{
root->balfact=1;
node1->balfact=-1;
*h=FALSE;
}
else
{
root->balfact=node1->balfact=0;
}
root=node1;
}
else
{
printf("\n Double rotation , left along %d ",node1->data);
node2=node1->right;
node1->right=node2->left;
node2->left=node1;
printf(" then right along %d .\n",root->data);
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;
node2->balfact=0;
}
}
return (root);
}
/*n Displays the tree in-order */
void display(struct AVLNode *root)
{
if(root!=NULL)
{
display(root->left);
printf("%d\t",root->data);
display(root->right);
}
}
/* Deletes the tree */
void deltree(struct AVLNode * root)
{
if(root!=NULL)
{
deltree(root->left);
deltree(root->right);
}
free(root);
}
//: CLICK HERE
AVL
TREES IN CPP
