/*This program is of creation of AVL Tree which includes following features:-
1.Create
2.In order
3.Pre order
4.Post order
5.Insert
6.Height of tree
7.Search element
8.Delete element
9.Find minimum
10.Find maximum
#this code is written in turboc++
*/
#include<iostream.h>
#include<conio.h>
#include<alloc.h>
#include<process.h>
struct node
{
int data;
struct node* right,*left;
}*root=NULL;
int height(struct node *ptr )
{
int l,r,h;
if(ptr==NULL)
return -1;
else
{
l=height(ptr->left);
r=height(ptr->right);
h= l>r?l+1:r+1;
}
return h;
}
int balance(struct node *ptr)
{
int l,r,b;
if(ptr==NULL)
return 0;
else
{
l=height(ptr->left);
r=height(ptr->right);
b=l-r;
}
return b;
}
struct node* llrotate(struct node *ptr)
{
struct node *temp;
temp=ptr->left;
ptr->left=temp->right;
temp->right=ptr;
return temp;
}
struct node* rrrotate(struct node *ptr)
{
struct node *temp;
temp=ptr->right;
ptr->right=temp->left;
temp->left=ptr;
return temp;
}
struct node* lrrotate(struct node *ptr)
{
struct node *temp;
temp=ptr->left->right;
ptr->left->right=temp->left;
temp->left=ptr->left;
ptr->left=temp->right;
temp->right=ptr;
return temp;
}
struct node* rlrotate(struct node *ptr)
{
struct node *temp;
temp=ptr->right->left;
ptr->right->left=temp->right;
temp->right=ptr->right;
ptr->right=temp->left;
temp->left=ptr;
return temp;
}
struct node* create(struct node *ptr,int a)
{
if(ptr==NULL)
{
struct node *nn;
nn=(struct node*)malloc(sizeof(struct node));
nn->data=a;
nn->right=NULL;
nn->left=NULL;
ptr=nn;
}
else
{
if((ptr->data)>a)
{
ptr->left=create(ptr->left,a);
if(balance(ptr)==2)
{
if(a<ptr->left->data)
{
ptr=llrotate(ptr);
}
else
{
ptr=lrrotate(ptr);
}
}
}
else if(ptr->data==a)
cout<<"element already exist!\n";
else
{
ptr->right=create(ptr->right,a);
if(balance(ptr)==-2)
{
if(a>ptr->right->data)
{
ptr=rrrotate(ptr);
}
else
{
ptr=rlrotate(ptr);
}
}
}
}
return ptr;
}
struct node* findmin(struct node *ptr)
{
if(ptr->left)
return findmin(ptr->left);
else
return ptr;
}
struct node* findmax(struct node *ptr)
{
if(ptr->right)
return findmax(ptr->right);
else
return ptr;
}
struct node* del(struct node *ptr,int a)
{
if(ptr==NULL)
{
cout<<"Element not present!!"<<endl;
}
else
{
if((ptr->data)>a)
{
ptr->left=del(ptr->left,a);
if(balance(ptr)==-2)
{
if(ptr->right->right)
{
ptr=rrrotate(ptr);
}
else
{
ptr=rlrotate(ptr);
}
}
}
else if(ptr->data==a)
{
struct node *temp;
if(ptr->left&&ptr->right)
{
temp=findmin(ptr->right);
ptr->data=temp->data;
ptr->right=del(ptr->right,ptr->data);
}
else
{
if(ptr->left)
{
temp=findmax(ptr->left);
ptr->data=temp->data;
ptr->left=del(ptr->left,ptr->data);
}
else if(ptr->right)
{
temp=findmin(ptr->right);
ptr->data=temp->data;
ptr->right=del(ptr->right,ptr->data);
}
else
{
temp=ptr;
ptr=NULL;
free(temp);
}
}
}
else
{
ptr->right=del(ptr->right,a);
if(balance(ptr)==2)
{
if(ptr->left->left)
{
ptr=llrotate(ptr);
}
else
{
ptr=lrrotate(ptr);
}
}
}
}
return ptr;
}
void indisplay(struct node *ptr)
{
if(ptr==NULL)
return;
indisplay(ptr->left);
cout<<ptr->data<<" ";
indisplay(ptr->right);
}
void predisplay(struct node *ptr)
{
if(ptr==NULL)
return;
cout<<ptr->data<<" ";
predisplay(ptr->left);
predisplay(ptr->right);
}
void postdisplay(struct node *ptr)
{
if(ptr==NULL)
return;
postdisplay(ptr->left);
postdisplay(ptr->right);
cout<<ptr->data<<" ";
}
struct node* search(struct node *ptr,int a)
{
if(ptr==NULL)
return ptr;
else if(ptr->data>a)
return search(ptr->left,a);
else if(ptr->data<a)
return search(ptr->right,a);
return ptr;
}
//ans:- In order : 5 10 12 15 17 19 20 25
void main()
{
int choice;
char ch='j';
int a;
clrscr();
cout<<"1.Create\t2.In order\t3.Pre order\t4.Post order\t5.Insert\t6.Height of tree\t7.Search element\t8.Delete element\t9.Find minimum\t10.Find maximum\t11.Exit"<<endl;
do{
cout<<"Choose a operation which you want to perform:";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter elements(enter -1 after last element):";
while(a!=-1)
{
cin>>a;
if(a!=-1)
root=create(root,a);
}
break;
case 2:
indisplay(root);
cout<<"\n";
break;
case 3:
predisplay(root);
cout<<"\n";
break;
case 4:
postdisplay(root);
cout<<"\n";
break;
case 5:
cout<<"Enter element which you want to insert:";
cin>>a;
root=create(root,a);
break;
case 6:cout<<"Height of tree = "<<height(root)<<endl;
break;
case 7:cout<<"Enter element:";
cin>>a;
if(search(root,a))
cout<<"Element found"<<endl;
else
cout<<"Element not found!!"<<endl;
break;
case 8:
cout<<"Enter element which you want to delete:";
cin>>a;
root=del(root,a);
cout<<"Deletion successful!!\n";
break;
case 9:
cout<<"minimum = "<<(findmin(root)->data)<<"\n";
break;
case 10:
cout<<"maximum = "<<(findmax(root)->data)<<"\n";
break;
case 11:exit(0);
break;
default:cout<<"Wrong entry\n";
}
}while(ch=='j');
}
| 
| 
