DATA STRUCTURES-POINTER IMPLEMENTATION OF "AVL" TREES

PROGRAM CODING:-

typedef int elttype;
#include<stdio.h>
#include<stdlib.h>
struct avl
{
elttype data;
struct avl * left,*right;
int ht;
};
int height(struct avl *p)
{
if(p==NULL)
return -1;
else return p->ht;
}
int max(int a,int b)
{
if(a>b)
return a;
else return b;
}
struct avl * find(elttype x,struct avl *t)
{
if(t==NULL)
return NULL;
if(x<t->data)
return(find(x,t->left));
else if(x>t->data)
return(find(x,t->right));
else
return t;
}
struct avl * findmin(struct avl *t)
{
if(t!=NULL)
while(t->left!=NULL)
t=t->left;
return t;
}
struct avl * findmax(struct avl *t)
{
if(t->right==NULL)
return t;
else return findmax(t->right);
}


struct avl * makeempty(struct avl * t)
{
if(t!=NULL)
{
makeempty(t->left);
makeempty(t->right);
free(t);
}
return NULL;
}
void dispose(struct avl * t)
{
makeempty(t);
free(t);
}
struct avl * singlerotationwithleft(struct avl * k2)
{
struct avl *k1;
k1=k2->left;
k2->left=k1->right;
k1->right=k2;
k2->ht=max(height(k2->left),height(k2->right))+1;
k1->ht=max(height(k1->left),height(k1->right))+1;
return k1;
}
struct avl * singlerotationwithright(struct avl * k2)
{
struct avl *k1;
k1=k2->right;
k2->right=k1->left;
k1->left=k2;
k2->ht=max(height(k2->left),height(k2->right))+1;
k1->ht=max(height(k1->left),height(k1->right))+1;
return k1;
}
struct avl * doublerotationwithleft(struct avl * k3)
{
k3->left=singlerotationwithright(k3->left);
return singlerotationwithleft(k3);
}
struct avl * doublerotationwithright(struct avl * k3)
{
k3->right=singlerotationwithleft(k3->right);
return singlerotationwithright(k3);
}
struct avl * insert(elttype x, struct avl * t)
{
if(t==NULL)
{
t=(struct avl *)malloc(sizeof(struct avl));
t->data=x;
t->ht=0;
t->left=t->right=NULL;
}
else if(x<t->data)
{
t->left=insert(x,t->left);
if(height(t->left)-height(t->right)==2)
{
if(x<t->left->data)
t=singlerotationwithleft(t);
else
t=doublerotationwithleft(t);
}
}
else if(x>t->data)
{
t->right=insert(x,t->right);
if(height(t->right)-height(t->left)==2)
{
if(x>t->right->data)
t=singlerotationwithright(t);
else
t=doublerotationwithright(t);
}
}
else printf("Updated message:Element already present.No change made to tree!**!");
t->ht=max(height(t->left),height(t->right))+1;
return t;
}
struct avl * delet(elttype x,struct avl *t)
{
struct avl *temp;
if(t==NULL)
{
printf("Deletion failure:Value not found!**!");
return NULL;
}
else if(t->data > x)
{
t->left=delet(x,t->left);
if(height(t->right)-height(t->left)==2)
{
if(t->right->left!=NULL)
t=doublerotationwithright(t);
else
t=singlerotationwithright(t);
}
}
else if(t->data < x)
{
t->right=delet(x,t->right);
if(height(t->left)-height(t->right)==2)
{
if(t->left->right!=NULL)
t=doublerotationwithleft(t);
else
t=singlerotationwithleft(t);
}
}
else
{
if(t->left!=NULL && t->right!=NULL)
{
temp=findmax(t->left);
t->data=temp->data;
t->left=delet(t->data,t->left);
}
else if(t->right!=NULL)
{
temp=t->right;
free(t);
return temp;
}
else if(t->left!=NULL)
{
temp=t->left;
free(t);
return temp;
}
else
{
free(t);
printf("Deletion successful!**!");
return NULL;
}
}
return t;
}
void preorder(struct avl *root)
{
if(root!=NULL)
{
printf("%d\t",root->data);
preorder(root->left);
preorder(root->right);
}
}
void inorder(struct avl *root)
{
if(root!=NULL)
{
inorder(root->left);
printf("%d\t",root->data);
inorder(root->right);
}
}
void postorder(struct avl *root)
{
if(root!=NULL)
{
postorder(root->left);
postorder(root->right);
printf("%d\t",root->data);
}
}
int main()
{
struct avl *root,*tmp;
int ch,ch1;
elttype datum;
root=NULL;
while(1)
{
printf("\nAVL TREE MAIN MENU:\n\t1.Insert\n\t2.Delete\n\t3.Traversal menu\n\t4.Search\n\t5.Find min\n\t6.Find max\n\t7.Make empty\n\t8.Delete tree and exit\nChoice:");
scanf("%d",&ch);
if(ch==8)
break;
switch(ch)
{
case 1:
printf("Enter the data to inserted: ");
scanf("%d",&datum);
root=insert(datum,root);
printf("Insertion successful!**!");
break;
case 2:
if(root!=NULL)
{
printf("Enter the data to be deleted: ");
scanf("%d",&datum);
root=delet(datum,root);
}
else printf("Deletion failure:Search tree is empty!**!");
break;
case 3:
while(1)
{
if(root==NULL)
{
printf("Traversal Failure:Search Tree is empty=>No traversal possible!**!");
break;
}
printf("\nTRAVERSAL MENU:\n\t1.Preorder\n\t2.Inorder\n\t3.Postorder\n\t4.Back to main menu\nChoice: ");
scanf("%d",&ch1);
if(ch1==4)
break;
switch(ch1)
{
case 1:
printf("Preorder traversal:\n");
preorder(root);
break;
case 2:
printf("Inorder traversal:\n");
inorder(root);
break;
case 3:
printf("Postorder traversal:\n");
postorder(root);
break;
}
}
break;
case 4:
if(root!=NULL)
{
printf("Enter the data to be searched:");
scanf("%d",&datum);
tmp=find(datum,root);
if(tmp==NULL)
printf("Search failure:Value not found!**!");
else
printf("Value found");
}
else printf("Search Failure:Search tree is empty!**!");
break;
case 5:
tmp=findmin(root);
if(root!=NULL)
{
if(tmp==NULL)
printf("AVL tree is empty!**!");
else
printf("Minimum value: %d",tmp->data);
}
else printf("Search tree is empty!**!!");
break;
case 6:
tmp=findmax(root);
if(root!=NULL)
{
if(tmp==NULL)
printf("AVL tree is empty!**!");
else
printf("Maximum value: %d",tmp->data);
}
else printf("AVL tree is empty!**!");
break;
case 7:
if(root==NULL)
printf("AVL tree is already empty!**!");
else
{
root=makeempty(root);
printf("AVL tree made empty!**!");
}
break;
default:printf("Enter correct menu option!**!");
}
}
return 0;
}