365 lines
9.7 KiB
C++
365 lines
9.7 KiB
C++
|
/*
|
||
|
THIS CODE HAS BEEN TESTED AND IS FULLY OPERATIONAL.
|
||
|
|
||
|
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 Binary Search Tree for implementation.
|
||
|
|
||
|
Code from DataStructuresAndAlgorithms (SPPU - Second Year - Computer Engineering - Content) repository on KSKA Git: https://git.kska.io/sppu-se-comp-content/DataStructuresAndAlgorithms/
|
||
|
*/
|
||
|
|
||
|
// BEGINNING OF CODE
|
||
|
#include <iostream>
|
||
|
#include <string>
|
||
|
using namespace std;
|
||
|
|
||
|
class node {
|
||
|
public:
|
||
|
string key, value;
|
||
|
node *left, *right;
|
||
|
node();
|
||
|
node(string, string);
|
||
|
};
|
||
|
|
||
|
node::node() {
|
||
|
key = "";
|
||
|
value = "";
|
||
|
left = NULL;
|
||
|
right = NULL;
|
||
|
}
|
||
|
|
||
|
node::node(string key, string value) {
|
||
|
this->key = key;
|
||
|
this->value = value;
|
||
|
left = NULL;
|
||
|
right = NULL;
|
||
|
}
|
||
|
|
||
|
class bst {
|
||
|
public:
|
||
|
node *root;
|
||
|
bst();
|
||
|
bst(string, string);
|
||
|
bool insert(string, string);
|
||
|
string search(string);
|
||
|
bool update(string, string);
|
||
|
bool delete_key(string);
|
||
|
void display(node *cur);
|
||
|
void display_asc(node *cur);
|
||
|
};
|
||
|
|
||
|
bst::bst() { root = NULL; }
|
||
|
|
||
|
bst::bst(string key, string value) { root = new node(key, value); }
|
||
|
|
||
|
bool bst::insert(string key, string value) {
|
||
|
if (root == NULL) {
|
||
|
root = new node(key, value);
|
||
|
return 1;
|
||
|
}
|
||
|
|
||
|
node *temp, *prev;
|
||
|
prev = root;
|
||
|
temp = root;
|
||
|
while (temp != NULL) {
|
||
|
prev = temp;
|
||
|
if (temp->key == key) {
|
||
|
return 0;
|
||
|
} else if (temp->key < key) {
|
||
|
temp = temp->right;
|
||
|
} else {
|
||
|
temp = temp->left;
|
||
|
}
|
||
|
}
|
||
|
if (prev->key < key) {
|
||
|
prev->right = new node(key, value);
|
||
|
} else {
|
||
|
prev->left = new node(key, value);
|
||
|
}
|
||
|
return 1;
|
||
|
}
|
||
|
|
||
|
string bst::search(string key) {
|
||
|
node *temp = root;
|
||
|
while (temp != NULL) {
|
||
|
if (temp->key == key) {
|
||
|
return temp->value;
|
||
|
} else if (temp->key < key) {
|
||
|
temp = temp->right;
|
||
|
} else {
|
||
|
temp = temp->left;
|
||
|
}
|
||
|
}
|
||
|
return "\0"; // not present
|
||
|
}
|
||
|
|
||
|
bool bst::update(string key, string value) {
|
||
|
node *temp;
|
||
|
temp = root;
|
||
|
while (temp != NULL) {
|
||
|
if (temp->key == key) {
|
||
|
temp->value = value;
|
||
|
return 1;
|
||
|
} else if (temp->key < key) {
|
||
|
temp = temp->right;
|
||
|
} else {
|
||
|
temp = temp->left;
|
||
|
}
|
||
|
}
|
||
|
return 0;
|
||
|
}
|
||
|
|
||
|
bool bst::delete_key(string key) {
|
||
|
if (root == NULL) {
|
||
|
return 0;
|
||
|
}
|
||
|
|
||
|
node *temp, *prev;
|
||
|
prev = root;
|
||
|
temp = root;
|
||
|
|
||
|
if (temp->key == key) {
|
||
|
// delete root case
|
||
|
if (temp->left == NULL && temp->right == NULL) {
|
||
|
// no child
|
||
|
root = NULL;
|
||
|
delete temp;
|
||
|
} else if (temp->left != NULL && temp->right == NULL) {
|
||
|
// single child left
|
||
|
root = temp->left;
|
||
|
delete temp;
|
||
|
} else if (temp->left == NULL && temp->right != NULL) {
|
||
|
// single child right
|
||
|
root = temp->right;
|
||
|
delete temp;
|
||
|
} else {
|
||
|
// two child
|
||
|
// using left largest
|
||
|
node *l_temp = temp->left;
|
||
|
node *l_prev = temp;
|
||
|
if (l_temp->right == NULL) {
|
||
|
l_prev->left = l_temp->left;
|
||
|
} else {
|
||
|
while (l_temp->right != NULL) {
|
||
|
l_prev = l_temp;
|
||
|
l_temp = l_temp->right;
|
||
|
}
|
||
|
l_prev->right = l_temp->left;
|
||
|
}
|
||
|
|
||
|
// deleting temp
|
||
|
l_temp->right = temp->right;
|
||
|
l_temp->left = temp->left;
|
||
|
root = l_temp;
|
||
|
delete temp;
|
||
|
}
|
||
|
return 1;
|
||
|
} else if (temp->key < key) {
|
||
|
temp = temp->right;
|
||
|
} else {
|
||
|
temp = temp->left;
|
||
|
}
|
||
|
|
||
|
while (temp != NULL) {
|
||
|
// delete non root node
|
||
|
if (temp->key == key) {
|
||
|
if (temp->left == NULL && temp->right == NULL) {
|
||
|
// no child
|
||
|
if (temp->key < prev->key) {
|
||
|
// left child
|
||
|
prev->left = NULL;
|
||
|
} else {
|
||
|
// right child
|
||
|
prev->right = NULL;
|
||
|
}
|
||
|
delete temp;
|
||
|
} else if (temp->left != NULL && temp->right == NULL) {
|
||
|
// single child left
|
||
|
if (temp->key < prev->key) {
|
||
|
// left child
|
||
|
prev->left = temp->left;
|
||
|
delete temp;
|
||
|
} else {
|
||
|
// right child
|
||
|
prev->right = temp->left;
|
||
|
delete temp;
|
||
|
}
|
||
|
} else if (temp->left == NULL && temp->right != NULL) {
|
||
|
// single child right
|
||
|
if (temp->key < prev->key) {
|
||
|
// left child
|
||
|
prev->left = temp->right;
|
||
|
delete temp;
|
||
|
} else {
|
||
|
// right child
|
||
|
prev->right = temp->right;
|
||
|
delete temp;
|
||
|
}
|
||
|
} else {
|
||
|
// two child
|
||
|
// using left largest
|
||
|
node *l_temp = temp->left;
|
||
|
node *l_prev = temp;
|
||
|
if (l_temp->right == NULL) {
|
||
|
l_prev->left = l_temp->left;
|
||
|
} else {
|
||
|
while (l_temp->right != NULL) {
|
||
|
l_prev = l_temp;
|
||
|
l_temp = l_temp->right;
|
||
|
}
|
||
|
l_prev->right = l_temp->left;
|
||
|
}
|
||
|
|
||
|
// deleting temp
|
||
|
if (temp->key < prev->key) {
|
||
|
// left child
|
||
|
prev->left = l_temp;
|
||
|
} else {
|
||
|
// right child
|
||
|
prev->right = l_temp;
|
||
|
}
|
||
|
l_temp->left = temp->left;
|
||
|
l_temp->right = temp->right;
|
||
|
delete temp;
|
||
|
}
|
||
|
return 1;
|
||
|
} else if (temp->key < key) {
|
||
|
prev = temp;
|
||
|
temp = temp->right;
|
||
|
} else {
|
||
|
prev = temp;
|
||
|
temp = temp->left;
|
||
|
}
|
||
|
}
|
||
|
return 0;
|
||
|
}
|
||
|
|
||
|
void bst::display(node *cur) {
|
||
|
if (cur == NULL) {
|
||
|
return;
|
||
|
}
|
||
|
display(cur->left);
|
||
|
cout << cur->key << " : " << cur->value << endl;
|
||
|
display(cur->right);
|
||
|
}
|
||
|
|
||
|
void bst::display_asc(node *cur) {
|
||
|
if (cur == NULL) {
|
||
|
return;
|
||
|
}
|
||
|
display_asc(cur->right);
|
||
|
cout << cur->key << " : " << cur->value << endl;
|
||
|
display_asc(cur->left);
|
||
|
}
|
||
|
|
||
|
/*
|
||
|
// void printTree(node *root, int space = 0, int height = 20) {
|
||
|
if (root == nullptr) return;
|
||
|
space += height;
|
||
|
printTree(root->right, space);
|
||
|
cout << endl;
|
||
|
for (int i = height; i < space; i++) cout << " ";
|
||
|
cout << root->key << endl;
|
||
|
printTree(root->left, space);
|
||
|
}
|
||
|
*/
|
||
|
|
||
|
int main() {
|
||
|
bst tree;
|
||
|
int ch;
|
||
|
string k, v, ans;
|
||
|
do {
|
||
|
cout << "--- MAIN MENU ---" << endl;
|
||
|
cout << "1 -> Insert" << endl;
|
||
|
cout << "2 -> Search" << endl;
|
||
|
cout << "3 -> Update" << endl;
|
||
|
cout << "4 -> Delete" << endl;
|
||
|
cout << "5 -> Display Descending" << endl;
|
||
|
cout << "6 -> Display Ascending" << endl;
|
||
|
cout << "0 -> Exit" << endl;
|
||
|
cout << "Choose an option (0-6):\t";
|
||
|
cin >> ch;
|
||
|
switch (ch) {
|
||
|
case 1:
|
||
|
cout << "Key to insert:\t";
|
||
|
cin >> k;
|
||
|
cout << "Enter value:\t";
|
||
|
cin >> v;
|
||
|
if (tree.insert(k, v)) {
|
||
|
cout << "Element inserted successfully." << endl;
|
||
|
} else {
|
||
|
cout << "Element already exists." << endl;
|
||
|
}
|
||
|
break;
|
||
|
case 2:
|
||
|
cout << "Key to search:\t";
|
||
|
cin >> k;
|
||
|
ans = tree.search(k);
|
||
|
if (ans == "\0") {
|
||
|
cout << "Element not found" << endl;
|
||
|
} else {
|
||
|
cout << "Value is:\t" << ans << endl;
|
||
|
}
|
||
|
break;
|
||
|
case 3:
|
||
|
cout << "Key to update:\t";
|
||
|
cin >> k;
|
||
|
cout << "Enter new value:";
|
||
|
cin >> v;
|
||
|
if (tree.update(k, v)) {
|
||
|
cout << "Element updated successfully." << endl;
|
||
|
} else {
|
||
|
cout << "Element not present." << endl;
|
||
|
}
|
||
|
break;
|
||
|
case 4:
|
||
|
cout << "Key to delete:\t";
|
||
|
cin >> k;
|
||
|
if (tree.delete_key(k)) {
|
||
|
cout << "Element deleted successfully." << endl;
|
||
|
} else {
|
||
|
cout << "Element not present." << endl;
|
||
|
}
|
||
|
break;
|
||
|
case 5:
|
||
|
cout << "Data in descending order is:\t" << endl;
|
||
|
tree.display(tree.root);
|
||
|
break;
|
||
|
case 6:
|
||
|
cout << "Data in ascending order is:\t" << endl;
|
||
|
tree.display_asc(tree.root);
|
||
|
break;
|
||
|
case 0:
|
||
|
cout << "\n// END OF CODE\n\n";
|
||
|
break;
|
||
|
default:
|
||
|
cout << "Please choose a valid option (0-6)." << endl;
|
||
|
break;
|
||
|
}
|
||
|
} while (ch != 0);
|
||
|
|
||
|
return 0;
|
||
|
}
|
||
|
// END OF CODE
|
||
|
|
||
|
/*
|
||
|
Sample output:
|
||
|
|
||
|
Choose an option (0-6): 1
|
||
|
Key to insert: Test1
|
||
|
Enter value: 8
|
||
|
Element inserted successfully.
|
||
|
|
||
|
Choose an option (0-6): 1
|
||
|
Key to insert: Test2
|
||
|
Enter value: 9
|
||
|
Element inserted successfully.
|
||
|
|
||
|
Choose an option (0-6): 5
|
||
|
Data in descending order is:
|
||
|
Test1 : 8
|
||
|
Test2 : 9
|
||
|
|
||
|
Choose an option (0-6): 0
|
||
|
|
||
|
// END OF CODE
|
||
|
|
||
|
*/
|