Binary Search Tree Dictionary

1. A dictionary can be either implemented using a linked list or  a binary search tree.
2. Insertion and Searching in the former is more time consuming as compared to the later. Thus the later approach is preferred. 
3. Each node will have 2 children.
4. The values in the left subtree will be lesser than the parent and the values in the right subtree will be greater than the parent for each node.
5. Threaded children have not been used in this data structure.
6. This binary search tree can be balanced by using AVL tree method. This will further reduce the search time (searching in a skewed tree is equivalent to searching in a link list).
7. Wikipedia Link for BST :- https://en.wikipedia.org/wiki/Binary_search_tree

Below is the implementation of Dictionary in C++ language. It has the following functions:-

• Insert
• Delete
• Update
• Display
• Find 

The find function also display the number of comparisons required for finding the word.

Code 

#‎include‬ <string>
#include <cstring>
#include <iostream>
using namespace std;
class Node{
friend class Dictionary;
private:
Node *left;
Node *right;
string word;
string meaning;
public:
Node(string word="word not set",string meaning="meaning not set"){ //constructor for node
left=NULL;
right=NULL;
this->word=word;
this->meaning=meaning;
}
public:
};
class Dictionary{ //head node is the root of the binary search tree
public:
Node *headnode;
Dictionary(){
headnode=NULL;
}
Node* search(string searchstring,Node* parent){ //search operation on the string
if(parent==NULL){
//cout<<"Word not found"<<endl;
return parent;
}
int d=searchstring.compare(parent->word);
if(d==0){ //if the word in the node is equal to search string
return parent;
}
else if(d>0){ //if the word in the node is smaller than the search string
if(parent->right!=NULL)
return search(searchstring,parent->right);
return parent;
}
else if(d<0){ //if the word in the node is greater than the search string
if(parent->left!=NULL)
return search(searchstring,parent->left);
return parent;
}
else{
cout<<"Code should never reach here Error has been encountered"<<endl;
return NULL;// to get rid of warning
}
}
Node* search2(string searchstring,Node* parent, int count){ //searches for a word and prints the word and its meanings
if(parent==NULL){ //along with the number of comparissons
cout<<"Word not found,no of comparisons required = "<<int(count) <<endl;//word not found,reaches null pointer
return parent;
}
count=count+1;
int d=searchstring.compare(parent->word);
if(d==0){ //word is found
cout<<"Word found,no of comparisons required = "<< int(count)<<endl;
cout<<parent->word<<":-\t"<<parent->meaning<<endl;
return parent;
}
else if(d>0){ //if value in the node is less than the search string
return search2(searchstring,parent->right,count);
}
else if(d<0){ //if value in the node is more that the search string
return search2(searchstring,parent->left,count);
}
else{
cout<<"Code should never reach here Error has been encountered"<<endl;
return NULL;// to get rid of warning
}
}
void insert(string word){ // to insert a word into the tree
string meaning;
//char st[80];
cout<<"Enter meaning"<<endl;
cin.ignore();
getline(cin,meaning);
//cin>>meaning;
Node *temp=search(word,headnode); //search if the word already exists
if(headnode==NULL){ //if the tree is empty then modify the headnode
headnode=new Node(word,meaning);
return;
}
Node *temp2=new Node(word,meaning); //create the node to be inserted
if(temp->word==word){ //if word already exists display message
cout<<"the word already exists"<<endl;
}
else{ //if word does not exist insert at left or right of the root node
int d=word.compare(temp->word);
if(d>0){
temp->right=temp2;
cout<<"the word is successfully inserted"<<endl;
}
else{
temp->left=temp2;
cout<<"the word is successfully inserted"<<endl;
}
}
}
Node* del(Node *parent,string word){ //three cases leaf node,single child,double child
Node *temp;
if(parent==NULL){ //pointer becomes null if the word doesn't exist
cout<<"Element not found"<<endl;
return NULL;
}
int d=word.compare(parent->word);
if(d>0){
parent->right=del(parent->right,word);
return parent;
}
if(d<0){
parent->left=del(parent->left,word);
return parent;
}
//word is now found
if(parent->left==NULL&&parent->right==NULL){ //CASE:- LEAF NODE
temp=parent;
delete (temp);
return NULL;
}
if(parent->right==NULL){ //Case:-Single left child
temp=parent;
parent=parent->left;
delete temp;
return parent;
}
if(parent->left==NULL){ //Case:-Single right child
temp=parent;
parent=parent->right;
delete temp;
return parent;
}
//Node with two children
temp=findmin(parent->right); //find min in right subtree
parent->word=temp->word; //copy the data of min into the node to be deleted
parent->meaning=temp->meaning;
parent->right=del(parent->right,temp->word); //delete the minimum value in the right subtree
return parent;
//In case the node has two children
}
Node* findmin(Node *parent){ //returns pointer to minimum value in a tree
while(parent->left!=NULL){
parent=parent->left;
}
return parent;
}
void update(string word){ //to update the meaning of a word
Node *temp;
temp=search(word,headnode);
if(temp->word!=word){
cout<<"The given word doesn't exists"<<endl;
}
else{
cout<<"Enter the new meaning"<<endl;
string meaning;
cin.ignore();
getline(cin,meaning);
temp->meaning=meaning;
cout<<"The meaning has been updated in the dictionary"<<endl;
}
}
void display(Node *p){ //recursive in order traversal for ascending order
// Traversal is left root right
if(p!=NULL){
display(p->left);
cout<<p->word;
cout<<":-\t";
cout<<p->meaning<<endl;
display(p->right);
}
}
};
int main() {
Dictionary a;
int choice=0,count=0;
string word,meaning;
while(choice!=6){
cout<<"Enter your choice"<<endl;
cout<<"1.insert 2.update 3.delete 4.display entire dictionary 5.search 6.exit";
cin>>choice;
switch (choice){ //menu
case 1:
cout<<"Enter word"<<endl;
cin>>word;
a.insert(word);
break;
case 2:
cout<<"Enter word to update"<<endl;
cin>>word;
a.update(word);
break;
case 3:
cout<<"Enter word to delete"<<endl;
cin>>word;
a.headnode=a.del(a.headnode,word);
break;
case 4:
cout<<"Dictionary contents"<<endl;
a.display(a.headnode);
break;
case 5:
cout<<"Enter the word to search for"<<endl;
cin>>word;
a.search2(word,a.headnode,count);
break;
case 6:
cout<<"Terminating program"<<endl;
break;
default:
cout<<"Invalid choice entered\nPlease re-enter ur choice"<<endl;
break;
}
}
return 0;
}

Output

Enter your choice
1.insert 2.update 3.delete 4.display entire dictionary 5.search 6.exit1
Enter word
ghana
Enter meaning
african country
Enter your choice
1.insert 2.update 3.delete 4.display entire dictionary 5.search 6.exit1
Enter word
brazil
Enter meaning
south american country
the word is successfully inserted
Enter your choice
1.insert 2.update 3.delete 4.display entire dictionary 5.search 6.exit1
Enter word
china
Enter meaning
asian counry
the word is successfully inserted
Enter your choice
1.insert 2.update 3.delete 4.display entire dictionary 5.search 6.exit1
Enter word
africa
Enter meaning
continent
the word is successfully inserted
Enter your choice
1.insert 2.update 3.delete 4.display entire dictionary 5.search 6.exit1
Enter word
africa
Enter meaning
continental land
the word already exists
Enter your choice
1.insert 2.update 3.delete 4.display entire dictionary 5.search 6.exit1
Enter word
null
Enter meaning
zero
the word is successfully inserted
Enter your choice
1.insert 2.update 3.delete 4.display entire dictionary 5.search 6.exit1
Enter word
zebra
Enter meaning
animal
the word is successfully inserted
Enter your choice
1.insert 2.update 3.delete 4.display entire dictionary 5.search 6.exit2
Enter word to update
zebra
Enter the new meaning
animal of savana
The meaning has been updated in the dictionary
Enter your choice
1.insert 2.update 3.delete 4.display entire dictionary 5.search 6.exit4
Dictionary contents
africa:- continent
brazil:- south american country
china:- asian counry
ghana:- african country
null:- zero
zebra:- animal of savana
Enter your choice
1.insert 2.update 3.delete 4.display entire dictionary 5.search 6.exit3
Enter word to delete
ghana
Enter your choice
1.insert 2.update 3.delete 4.display entire dictionary 5.search 6.exit4
Dictionary contents
africa:- continent
brazil:- south american country
china:- asian counry
null:- zero
zebra:- animal of savana
Enter your choice
1.insert 2.update 3.delete 4.display entire dictionary 5.search 6.exit5
Enter the word to search for
null
Word found,no of comparisons required = 1
null:- zero
Enter your choice
1.insert 2.update 3.delete 4.display entire dictionary 5.search 6.exit5
Enter the word to search for
ghana
Word not found,no of comparisons required = 3
Enter your choice
1.insert 2.update 3.delete 4.display entire dictionary 5.search 6.exit3
Enter word to delete
zebra
Enter your choice
1.insert 2.update 3.delete 4.display entire dictionary 5.search 6.exit4
Dictionary contents
africa:- continent
brazil:- south american country
china:- asian counry
null:- zero
Enter your choice
1.insert 2.update 3.delete 4.display entire dictionary 5.search 6.exit3
Enter word to delete
brazil
Enter your choice
1.insert 2.update 3.delete 4.display entire dictionary 5.search 6.exit4
Dictionary contents
africa:- continent
china:- asian counry
null:- zero
Enter your choice
1.insert 2.update 3.delete 4.display entire dictionary 5.search 6.exit6
Terminating program