Skip to main content

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

Comments

  1. Daily Cumilla NewsJuly 26, 2020 at 1:41 AM

    Best description ever..if you want to know about bit coin and getnode you can come in this link Getnode

    ReplyDelete

Post a Comment

Popular posts from this blog

PPL 1

NEW Unit III STRUCTURING OF PROGRAM MULTIPLE CHOICE QUESTIONS 1. Which of the following is the functionality of ‘Data Abstraction’? (a) Reduce Complexity (b) Binds together code and data (c) Parallelism (d) None of the mentioned Answer : a Explanation : An essential element of Object Oriented Programming is ‘Data Abstraction’ which means hiding things. Complexity is managed through abstraction. 2. Which of the following mechanisms is/are provided by Object Oriented Language to implement Object Oriented Model? (a) Encapsulation (b) Inheritance (c) Polymorphism (d) All of the mentioned Answer : d Explanation : None. 3. Which of these is the functionality of ‘Encapsulation’? (a) Binds together code and data (b) Using single interface for general class of actions. (c) Reduce Complexity (d) All of the mentioned Answer : a Explanation : ‘Encapsulation’ acts as protective wrapper that prevents code and data from being accessed by other code defined outside the...
Post a Comment
Read more

EEE

EEE Unit-1 DC Machines MCQ's MULTIPLE CHOICE QUESTIONS ON UNIT 1: DC MACHINES Edit 1.The sole purpose of a Commutator in a dc generator is to------- ((A))increase output voltage ((B)) reduce sparking at brushes ((C)) provide smoother output ((D)) convert the induced ac into dc Hide ! Answer : D 2.In a dc generator, the generated emf is directly proportional to the------ ((A)) field current ((B)) pole flux ((C)) number of armature parallel paths ((D)) number of dummy coils Hide ! Answer:B 3.An ideal dc generator has .......... voltage regulation. ((A))low ((B))zero ((C))positive ((D))negative Hide ! Answer:B 4.Which generator may have poorest voltage regulation? ((A))series ((B))shunt((C))compound ((D))high Hide ! Answer:A 5.Voltage equation of a dc motor is----- ((A)) V = Eb + IaRa ((B)) Eb = V + IaRa ((C))V = Eb /IaRa ((D))V = Eb + Ia2Ra Hide ! Answer: A 6.Which of the following motor has the constant speed? ((A))Series motor ((B))Shunt motor ((C))Cumulatively compound motor ((D)...
Post a Comment
Read more

replacing strings without using inbuild functions

 Q:replacing strings without using inbuild functions. We are using gcc compiler and terminal to compile the code and ubuntu OS. PROGRAM: #include<stdio.h> int strln1(char s1[]); int strln2(char s2[]); void strcpy1(char s1[],char s2[]); int main() {     char s1[30],s2[30];     int result1,result2;     printf("Enter the string s1");     scanf("%s",s1);     printf("Enter the string s2");     scanf("%s",s2);     printf("Your string s1 is %s",s1);     printf("\nYour string s2 is %s",s2);     result1=strln1(s1);     result2=strln2(s2);     printf("\nlength of string s1 is %d\n",result1);     printf("\nlength of string s2 is %d\n",result2);     strcpy1(s1,s2); } int strln1(char s1[]) {     int i,ln;   ...
1 comment
Read more