8.AVL

File: /home/saiesh/ADS/Assignment No 8/ads8.cpp
#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;
typedef struct node
{
char word[30];
char meaning[50];
node *left, *right;
}avlnode;
avlnode *root;
class avltree
{
public:
avltree()
{
root=NULL;
}
avlnode* getnode();
int height(avlnode*);
int diff(avlnode *T);
avlnode *rr(avlnode *T);
avlnode *ll(avlnode *T);
avlnode *lr(avlnode *T);
avlnode *rl(avlnode *T);
avlnode *balance(avlnode *T);
avlnode *insert(avlnode *root,avlnode *T);
void display(avlnode*, int);
void comparison(avlnode *root);
void update(avlnode *root);
};
avlnode*avltree::getnode()
{
avlnode *temp;
temp=new avlnode;
cout<<"\nEnter the word:\t\t";
cin>>temp->word;
cout<<"Enter the meaning:\t";
cin>>temp->meaning;
temp->left=temp->right=NULL;
return temp;
}
int avltree::height(avlnode *temp)
{
int h=0,l,r,maxh;
if(temp!=NULL)
{
l=height(temp->left);
r=height(temp->right);
maxh=max(l,r);
h=maxh + 1;
}
return h;
}
int avltree::diff(avlnode *temp)
{
int l,r,bf;
l=height(temp->left);
r=height(temp->right);
bf=l-r;
Page 1 of 7File: /home/saiesh/ADS/Assignment No 8/ads8.cpp
return bf;
}
avlnode *avltree::rr(avlnode *T)
{
avlnode *temp;
temp=T->right;
T->right=temp->left;
temp->left=T;
return temp;
}
avlnode *avltree::ll(avlnode *T)
{
avlnode *temp;
temp=T->left;
T->left=temp->right;
temp->right=T;
return temp;
}
avlnode *avltree::lr(avlnode *T)
{
avlnode *temp;
temp=T->left;
T->left=rr(temp);
return ll(T);
}
avlnode *avltree::rl(avlnode *T)
{
avlnode *temp;
temp=T->right;
T->right=ll(temp);
return rr(T);
}
avlnode *avltree::balance(avlnode *temp)
{
int bf;
bf=diff(temp);
if(bf>1)
{
if(diff(temp->left)>0)
temp=ll(temp);
else
temp=ll(temp);
}
else if(bf<-1)
{
if(diff(temp->left)>0)
temp=rl(temp);
else
temp=rr(temp);
}
return temp;
}
avlnode *avltree::insert(avlnode *root,avlnode *T)
{
if(root==NULL)
{
root=new avlnode;
root=T;
root->left=NULL;
root->right=NULL;
Page 2 of 7File: /home/saiesh/ADS/Assignment No 8/ads8.cpp
return root;
}
else if(strcmp(T->word,root->word)<0)
{
root->left=insert(root->left,T);
root=balance(root);
}
else if(strcmp(T->word,root->word)>=0)
{
root->right=insert(root->right,T);
root=balance(root);
}
return root;
}
void avltree::display(avlnode *T,int level)
{
if(T!=NULL)
{
display(T->right,level+1);
cout<<"\n";
if(T==root)
cout<<"Root -> ";
for(int i=0;i<level && T!=root;i++)
cout<<"\t";
cout<<T->word<<"("<<T->meaning<<")";
display(T->left,level+1);
}
}
void avltree::comparison(avlnode *root)
{
avlnode *ptr;
ptr=root;
int i=0;
char word[30];
cout<<"\nEnter the word you need to compare: ";
cin>>word;
while(ptr!=NULL)
{
if(strcmp(word,ptr->word)==0)
{
cout<<"\nWord:\t\t"<<word;
cout<<"\nMeaning:\t"<<ptr->meaning<<"\n";
i++;
break;
}
else
i++;
if(strcmp(word,ptr->word)<0)
ptr=ptr->left;
else
ptr=ptr->right;
}
cout<<"Total number of comparisons: "<<i;
}
void avltree::update(avlnode *root)
{
avlnode *ptr;
ptr=root;
char word[30];
cout<<"\nEnter the word you need to update: ";
cin>>word;
while(ptr!=NULL)
{
Page 3 of 7File: /home/saiesh/ADS/Assignment No 8/ads8.cpp
if(strcmp(word,ptr->word)==0)
{
cout<<"\nWord:\t\t"<<word;
cout<<"\nNew Meaning:\t";
cin>>ptr->meaning;
return ;
}
else if(strcmp(word,ptr->word)<0)
ptr=ptr->left;
else
ptr=ptr->right;
}
cout<<"The word you want to update is not found.";
}
int main()
{
avltree obj;
avlnode *t;
char ans,word[30];
int ch;
do
{
cout<<"\n\t\t
MENU";
cout<<"\n1.Insert new node";
cout<<"\n2.Display nodes";
cout<<"\n3.Compare node";
cout<<"\n4.Update node";
cout<<"\n5.Exit";
cout<<"\nEnter your choice:\t";
cin>>ch;
switch(ch)
{
case 1: t=obj.getnode();
root=obj.insert(root,t);
break;
case 2: if(root==NULL)
{
cout<<"AVL Tree is empty";
continue;
}
cout<<"Balanced AVL Tree:\n";
obj.display(root,1);
break;
case 3: obj.comparison(root);
break;
case 4: obj.update(root);
obj.display(root,1);
break;
case 5: exit(0);
}
cout<<"\nDo you want to continue? ";
cin>>ans;
} while(ans=='y'||ans=='Y');
return 0;
}
/*
OUTPUT
saiesh@saiesh :~$ g++ ads8.cpp
saiesh@saiesh :~$ ./a.out
MENU
1.Insert new node
2.Display nodes
Page 4 of 7File: /home/saiesh/ADS/Assignment No 8/ads8.cpp
3.Compare node
4.Update node
5.Exit
Enter your choice:
1
Enter the word:
honey
Enter the meaning:
sweet
Do you want to continue? y
MENU
1.Insert new node
2.Display nodes
3.Compare node
4.Update node
5.Exit
Enter your choice:
1
Enter the word:
dome
Enter the meaning:
igloo
Do you want to continue? y
MENU
1.Insert new node
2.Display nodes
3.Compare node
4.Update node
5.Exit
Enter your choice:
1
Enter the word:
stop
Enter the meaning:
terminate
Do you want to continue? y
MENU
1.Insert new node
2.Display nodes
3.Compare node
4.Update node
5.Exit
Enter your choice:
1
Enter the word:
back
Enter the meaning:
reverse
Do you want to continue? y
MENU
1.Insert new node
2.Display nodes
3.Compare node
4.Update node
5.Exit
Enter your choice:
1
Enter the word:
ear
Enter the meaning:
organ
Do you want to continue? y
MENU
1.Insert new node
2.Display nodes
3.Compare node
4.Update node
5.Exit
Enter your choice: 1
Enter the word: apple
Page 5 of 7File: /home/saiesh/ADS/Assignment No 8/ads8.cpp
Enter the meaning:
fruit
Do you want to continue? y
MENU
1.Insert new node
2.Display nodes
3.Compare node
4.Update node
5.Exit
Enter your choice:
1
Enter the word:
father
Enter the meaning:
dad
Do you want to continue? y
MENU
1.Insert new node
2.Display nodes
3.Compare node
4.Update node
5.Exit
Enter your choice:
Balanced AVL Tree:
2
stop(terminate)
honey(sweet)
father(dad)
ear(organ)
Root -> dome(igloo)
back(reverse)
apple(fruit)
Do you want to continue? y
MENU
1.Insert new node
2.Display nodes
3.Compare node
4.Update node
5.Exit
Enter your choice:
3
Enter the word you need to compare: apple
Word:
apple
Meaning:
fruit
Total number of comparisons: 3
Do you want to continue? y
MENU
1.Insert new node
2.Display nodes
3.Compare node
4.Update node
5.Exit
Enter your choice:
3
Enter the word you need to compare: window
Total number of comparisons: 3
Do you want to continue? y
MENU
1.Insert new node
2.Display nodes
3.Compare node
4.Update node
5.Exit
Page 6 of 7File: /home/saiesh/ADS/Assignment No 8/ads8.cpp
Enter your choice:
4
Enter the word you need to update: back
Word:
New Meaning:
back
rewind
stop(terminate)
honey(sweet)
father(dad)
ear(organ)
Root -> dome(igloo)
back(rewind)
apple(fruit)
Do you want to continue? y
MENU
1.Insert new node
2.Display nodes
3.Compare node
4.Update node
5.Exit
Enter your choice:
saiesh@saiesh :~$ */
5
Page 7 of 7