C++ Program for implementation of dictionary using AVL Tree
#include <iostream>
#include <iomanip>
using namespace std;
class node
{
int key;
string meaning;
node *left,*right;
int height;
public:
node()
{
left=right=NULL;
height=1;
meaning="";
key=-1;
}
node(int key,string meaning)
{
this->key=key;
this->meaning=meaning;
left=right=NULL;
height=1;
}
friend class Dictionary;
};
class Dictionary
{
node *root;
public:
Dictionary()
{
root=NULL;
}
int max(int,int);
int getheight(node*);
node *insert(node *rnode,int key,string meaning);
void insertInit(int key,string meaning);
node *rightRotate(node *);
node *leftRotate(node *);
int getbalance(node*);
void preorder();
void preorderRec(node*);
void postorder();
void postorderRec(node *);
void inorder();
void inorderRec(node *);
};
int Dictionary::max(int a,int b)
{
return (a>b)?a:b;
}
int Dictionary::getheight(node *nnode)
{
if(nnode==NULL)
return 0;
else
return nnode->height;
}
int Dictionary::getbalance(node *n)
{
if(n==NULL)
return 0;
else
return (getheight(n->left)-getheight(n->right));
}
node* Dictionary::rightRotate(node *y)
{
node *x=y->left;
node *xr=x->right;
//Update Pointers after rotation
x->right=y;
y->left=xr;
y->height=max(getheight(y->left),getheight(y->right))+1;
x->height=max(getheight(x->left),getheight(x->right))+1;
return x;
}
node* Dictionary::leftRotate(node *y)
{
node *x=y->right;
node *t2=x->left;
x->left=y;
y->right=t2;
y->height=max(getheight(y->left),getheight(y->right))+1;
x->height=max(getheight(x->left),getheight(x->right))+1;
return x;
}
node* Dictionary::insert(node *rnode,int key,string meaning)
{
//1. Normat BST Operation
if(rnode==NULL) //Empty Dictionary
return new node(key,meaning);
if(key<rnode->key)
rnode->left=insert(rnode->left,key,meaning);
else if(key>rnode->key)
rnode->right=insert(rnode->right,key,meaning);
else //equal value key
return rnode;
//2. update height of ancestors
rnode->height=1+max(getheight(rnode->left),getheight(rnode->right));
//3. Get balancing factor
int balance=getbalance(rnode);
//4. perform rotations and return nre root
//LL Case
if(balance>1 && key<rnode->left->key)
return rightRotate(rnode);
//RR Case
if(balance<-1 && key>rnode->right->key)
return leftRotate(rnode);
//LR Case
if(balance>1 && key>rnode->left->key)
{
rnode->left=leftRotate(rnode->left);
return rightRotate(rnode);
}
//RL Case
if(balance<-1 && key<rnode->right->key)
{
rnode->right=rightRotate(rnode->right);
return leftRotate(rnode);
}
return rnode; //no change in root
}
void Dictionary::preorder()
{
preorderRec(root);
}
void Dictionary::postorder()
{
postorderRec(root);
}
void Dictionary::inorder()
{
inorderRec(root);
}
void Dictionary::preorderRec(node *n)
{
if(n)
{
cout<<endl<<n->key<<" "<<n->meaning;
preorderRec(n->left);
preorderRec(n->right);
}
}
void Dictionary::inorderRec(node *n)
{
if(n)
{
inorderRec(n->left);
cout<<endl<<n->key<<" "<<n->meaning;
inorderRec(n->right);
}
}
void Dictionary::postorderRec(node *n)
{
if(n)
{
postorderRec(n->left);
postorderRec(n->right);
cout<<endl<<n->key<<" "<<n->meaning;
}
}
void Dictionary::insertInit(int key,string meaning)
{
root=insert(root,key,meaning);
}
int main() {
Dictionary d;
d.insertInit(10,"Apple");
d.insertInit(20,"Banana");
d.insertInit(30,"Orange");
d.insertInit(40,"Grapes");
d.insertInit(50,"Papaya");
cout<<"\nASCENDING ORDER:";
d.inorder();
cout<<"\nPreorder: ";
d.preorder();
cout<<"\nPostorder: ";
d.postorder();
return 0;
}
Output
ASCENDING ORDER:
10 Apple
20 Banana
30 Orange
40 Grapes
50 Papaya
Preorder:
20 Banana
10 Apple
40 Grapes
30 Orange
50 Papaya
Postorder:
10 Apple
30 Orange
50 Papaya
40 Grapes
20 Banana
No comments:
Post a Comment