Question

Goal: design and implement a dictionary. implement your dictionary using AVL tree .

Problem​:

Each entry in the dictionary is a pair: (word, meaning). Word is a one-word string, meaning can

be a string of one or more words (it’s your choice of implementation, you can restrict the

meaning to one-word strings). The dictionary is case-insensitive. It means “Book”, “BOOK”, “book” are all the same .

Your dictionary application must provide its operations through the following menu (make sure that you follow this format):

Possible operations:

f) find the meaning of a word.

i) insert and entry.

l) load the dictionary from an input file.

p) print all the entries.

r) remove an entry.

s) save the contents of the dictionary in an output file. x) exit

Please choose an option (f, i, l, p, r, s, or x):

The user should enter one of the options (just one character f, i, l, p,r, s or x). Your program should act based on the user’s option:

Find option:

The program asks the user to enter a word, then searches the dictionary and if it exists, prints the meaning of the word, otherwise prints:

Word not found.

Insert option:

The program asks the user to enter a word. The program searches the word in the dictionary, and if it does not exist, it asks the user to enter the meaning of the word and it should insert the entry (word, meaning) into the dictionary. If the word exists in the dictionary the program prints:

The word you entered already exists in the dictionary.

Load option:

The program asks the user to enter the name (address) of the file containing a set of entries (e.g. “dictionary.txt”). It should open the file, read the entries and insert them in the dictionary. Format of the file: each line is one entry. The first word in the line is the word and the rest of the line is the meaning (it can be just one word, depending on your design).

Print option:

The program should print all the entries sorted based on the word (alphabetically). Each entry on a separate line. For example:

abide follow

boss chief

destroy demolish domestic family ...

Remove option:

The program asks the user to enter a word and the program searches the word in the dictionary and remove it, otherwise prints:

Word not found.

Save option:

The program asks the user to enter the name (address) of a file to store the entries. ​The program should write the entries in the dictionary according to the pre-order traversal of the tree into the output file.​​Each line of the file contains one entry of the dictionary.

Exit option:

Terminates the program.

Guideline:

In addition to AVL tree ADT, you need at least three other classes: one class for word entries (containing word-meaning) and the main dictionary class, and a test class. AVL trees are an enhanced form of Binary Search Trees. You have to implement method remove (modify method remove from Binary Search Tree implementation).

Specific requirements

You must name your main class (the class with the main method) ​dictionary.java.​Make sure to add a readme file that explains your code (different classes and their methods) and any additional notes about your program

Important Remarks

It’s very important that you make sure your program compiles without any problem. Your input and output file format should exactly follow the requirements stated previously.

The code should be in java.

Answer 1

#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;