Header Ads

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.



2 comments:

  1. I just want to produce a quick comment to be able to express gratitude back for all those wonderful pointers you’re posting at this site. My time consuming internet investigation has at the conclusion of the day been rewarded with excellent means to show to my guests. I’d personally claim that a number of us guests are very endowed to happens to an excellent network with lots of marvellous people who useful hints. I believe quite privileged to possess used your webpages and check forward to really more fabulous minutes reading here. Thank you for lots of things. https://www.seoexpertindelhi.in/google-word-coach/

    ReplyDelete

Powered by Blogger.