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.
how to delete element
ReplyDeleteI 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