AVL Tree

Wikipedia Link:-https://en.wikipedia.org/wiki/AVL_tree
An AVL tree is a self-balancing binary search tree.
Inventors:- Georgy Adelson-Velsky and Evgenii Landis

C++ Program for AVL tree

//============================================================================
// Copyright : Abhishek Munagekar and Programming Wonders,2015
//www.facebook.com/prgwonders
//============================================================================

#include <string>

#include <cstring>
#include <iostream>
using namespace std;
Visit
class Node{
friend class Dict;
public:
Node *left,*right;
string word,meaning;
int h;
Node(string word="word not set",string meaning="meaning not set"){
this->word=word;
this->meaning=meaning;
h=0;
this->left=this->right=NULL;
}
};
class Dict{
public:
Node *headnode;
Dict(){
headnode=NULL;
}
void display(Node *p){
if(headnode==NULL){
cout<<"The dictionary is empty"<<endl;
}
else if(p!=NULL){
display(p->left);
cout<<p->word<<":\t"<<p->meaning<<endl;
display(p->right);
}
}
int height(Node *p){
int hl,hr;
if(p==NULL){
return 0;
}
if(p->left==NULL)
hl=0;
else
hl=1+p->left->h;
if(p->right==NULL)
hr=0;
else
hr=1+p->right->h;
return max(hr,hl);
}
int bf(Node *p){
int hl,hr;
if(p==NULL)
return 0;
if(p->left==NULL)
hl=0;
else
hl=p->left->h+1;
if(p->right==NULL)
hr=0;
else
hr=p->right->h+1;
return hl-hr;
}
Node *rotateright(Node *x){
Node *y=x->left;
x->left=y->right;
y->right=x;
y->h=height(y);
x->h=height(x);
return y;
}
Node *rotateleft(Node *x){
Node *y=x->right;
x->right=y->left;
y->left=x;
y->h=height(y);
x->h=height(x);
return y;
}
Node *RR(Node *x){
x=rotateleft(x);
return x;
}
Node *LL(Node *x){
x=rotateright(x);
return x;
}
Node *LR(Node *x){
x->left=rotateleft(x->left);
x=rotateright(x);
return x;
}
Node *RL(Node *x){
x->right=rotateright(x->right);
x=rotateleft(x);
return x;
}
Node *insert(Node *p,string word,string meaning){
if(p==NULL){
p=new Node(word,meaning);
}
else{
int d=word.compare(p->word);
if(d>0){
p->right=insert(p->right,word,meaning);
if(bf(p)==-2){
if(bf(p->right)<=0){
p=RR(p);
}
else{
p=RL(p);
}
}
}
else if(d<0){
p->left=insert(p->left,word,meaning);
if(bf(p)==2){
if(bf(p)>=0)
p=LL(p);
else
p=LR(p);
}
}
else{
cout<<"word already exists"<<endl;
}
}
p->h=height(p);
return p;
}
Node *remove(Node *p,string word){
if(p==NULL){
cout<<"Given word does not exist"<<endl;
}
else{
int d=word.compare(p->word);
if(d>0){
p->right=remove(p->right,word);
if(bf(p)==2){
if(bf(p->right)>=0)
p=LL(p);
else
p=LR(p);
}
}
else if(d<0){
p->left=remove(p->left,word);
if(bf(p)==-2){
if(bf(p->left)<=0)
p=RR(p);
else
p=RL(p);
}
}
else{
if(p->right!=NULL){
Node *temp=p->right;
while(temp->left!=NULL)
temp=temp->left;
p->word=temp->word;
p->meaning=temp->meaning;
p->right=remove(p->right,temp->word);
if(bf(p)==2){
if(bf(p->right)>=0)
p=LL(p);
else
p=LR(p);
}

}
else{
return p->left;
}
}
}
p->h=height(p);
return p;
}

};
int main() {
Dict a;
int ch;
string word;
string meaning;
while(ch!=1 ){
cout<<"1.Exit 2.Display 3.Insert 4.Delete"<<endl;
cin>>ch;
switch (ch){
case 1:
cout<<"terminating program"<<endl;
break;
case 2:
a.display(a.headnode);
break;
case 3:
cin>>word>>meaning;
a.headnode=a.insert(a.headnode,word,meaning);
break;
case 4:
cin>>word;
a.headnode=a.remove(a.headnode,word);
break;
}
}
cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
return 0;
}