C++ Program for implementing Dictionary ADT using AVL Tree

Problem Statement:-

A Dictionary stores keywords & its meanings. Provide facility for adding new keywords, deleting keywords, updating values of any entry. Provide facility to display whole data sorted in ascending/ Descending order. Also find how many maximum comparisons may require for finding any keyword. Use Height balance tree and find the complexity for finding a keyword

Code:-

//============================================================================
// Name        : AVL.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#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;
 }
 void print()
 {
  cout<<endl<<setw(10)<<key<<setw(10)<<meaning;
 }
 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)
 {
  n->print();
  preorderRec(n->left);
  preorderRec(n->right);
 }
}

void Dictionary::inorderRec(node *n)
{
 if(n)
 {
  inorderRec(n->left);
  n->print();
  inorderRec(n->right);
 }
}

void Dictionary::postorderRec(node *n)
{
 if(n)
 {
  postorderRec(n->left);
  postorderRec(n->right);
  n->print();
 }
}
void Dictionary::insertInit(int key,string meaning)
{
 root=insert(root,key,meaning);
}
int main() {
 Dictionary d;
// d.insertInit("V","Vaibhav");
// d.insertInit("N","Navnath");
// d.insertInit("K","Kumbhar");
// d.insertInit("G","Ganesha");
// d.insertInit("5","Five");

 d.insertInit(10,"10");
 d.insertInit(20,"20");
 d.insertInit(30,"30");
 d.insertInit(40,"40");
 d.insertInit(50,"50");
 d.insertInit(25,"25");
 cout<<"\nASCENDING ORDER:";
 d.inorder();

 cout<<"\nPreorder: ";
 d.preorder();

 cout<<"\nPostorder: ";
 d.postorder();

 return 0;
}

Output:-

P.S. : Change code according to your need.