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 keywordCode:-
//============================================================================ // 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.

No comments: