Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
An implementation of Binary Search Tree data structure.
#include <sstream>
#include <iostream>
#include <ctime>
using namespace std;
struct element
{
element* next;
};
struct node
{
int key;
node* parent;
// Left child.
node* left;
// Right child.
node* right;
// A linked list of elements in this node. Used for elements with equal keys.
element* list;
};
void joinLists(element* list1, element* list2);
void insert(node* &T, node* newN)
{
node* y = NULL;
node* x = T;
// look for the leaf node that will be the parent of the new value
while(x != NULL) {
y = x;
if(newN->key < x->key) {
x = x->left;
} else if(newN->key > x->key) {
x = x->right;
} else {
// a node with the same key is already present in the tree
// append the list of elements of the new node to the list of the existing node
joinLists(x->list, newN->list);
return;
}
}
if(y == NULL) {
// tree is empty
T = newN;
return;
}
newN->parent = y;
if(newN->key < y->key) {
y->left = newN;
} else {
y->right = newN;
}
}
node* find(node* x, int key)
{
while(x != NULL && key != x->key) {
if(key < x->key) {
x = x->left;
} else {
x = x->right;
}
}
return x;
}
node* findRecursive(node* x, int key)
{
if(x == NULL || x->key == key) {
return x;
}
if(key < x->key) {
return findRecursive(x->left, key);
}
return findRecursive(x->right, key);
}
node* minimum(node* x)
{
while(x->left != NULL) {
x = x->left;
}
return x;
}
node* minimumRecursive(node* x)
{
if(x->left == NULL) {
return x;
}
return minimumRecursive(x->left);
}
node* maximum(node* x)
{
while(x->right != NULL) {
x = x->right;
}
return x;
}
node* maximumRecursive(node* x)
{
if(x->right == NULL) {
return x;
}
return maximumRecursive(x->right);
}
node* successor(node* x)
{
if(x->right != NULL) {
return minimum(x->right);
}
node* y = x->parent;
while(y != NULL && x == y->right) {
x = y;
y = y->parent;
}
return y;
}
node* predecessor(node* x)
{
if(x->left != NULL) {
return maximum(x->left);
}
node* y = x->parent;
while(y != NULL && x == y->left) {
x = y;
y = y->parent;
}
return y;
}
// Remove the provided node.
void remove(node* &T, node* n)
{
node* y;
if(n->left == NULL || n->right == NULL) {
y = n;
} else {
y = successor(n);
}
node* x;
if(y->left == NULL) {
x = y->right;
} else {
x = y->left;
}
if(x != NULL) {
x->parent = y->parent;
}
if(y->parent == NULL) {
// a new root value was set
T = x;
} else {
if(y == y->parent->left) {
y->parent->left = x;
} else {
y->parent->right = x;
}
}
if(y != n) {
n->key = y->key;
}
delete y;
}
// Remove the node with the specified key.
void remove(node* &T, int key)
{
node* n = find(T, key);
if(n == NULL) {
cout << "Key '" << key << "' does not exist in the tree!" << endl;
return;
}
remove(T, n);
}
// Remove the specified element from the provided node.
void remove(node* n, element* ele)
{
element* prev = NULL;
element* current = n->list;
while(true) {
if(current == ele) {
break;
}
if(current->next == NULL) {
cout << "The provided element does not exist in a node with key '" << n->key << "'." << endl;
return;
}
prev = current;
current = current->next;
}
if(prev == NULL) {
n->list = current->next;
} else {
prev->next = current->next;
}
delete current;
}
// Remove the specified element from the node with the specified key.
void remove(node* T, int key, element* ele)
{
node* n = find(T, key);
if(n == NULL) {
cout << "Key '" << key << "' does not exist in the tree!" << endl;
return;
}
remove(n, ele);
}
void sortedOutput(node* x)
{
if(x == NULL) {
return;
}
sortedOutput(x->left);
// output all elements in the node
element* current = x->list;
while(true) {
cout << x->key;
current = current->next;
if(current == NULL) {
break;
}
cout << "-";
}
cout << " ";
sortedOutput(x->right);
}
void joinLists(element* list1, element* list2)
{
// find the tail of the 1st list
element* tail1 = list1;
while(tail1->next != NULL) {
tail1 = tail1->next;
}
// append the 2nd list
tail1->next = list2;
}
int showMenu();
int getInt(string prompt);
int main()
{
srand((unsigned int)time(NULL));
node* T = NULL;
while(true) {
switch(showMenu()) {
case 1: // Insert data
{
node* n = new node;
n->key = getInt("Insert a key: ");
n->list = new element;
n->list->next = NULL;
n->parent = NULL;
n->left = NULL;
n->right = NULL;
insert(T, n);
break;
}
case 2: // Sorted output
{
cout << "Sorted output:" << endl;
sortedOutput(T);
cout << endl;
break;
}
case 3: // Search
{
int key = getInt("Insert a key to look for: ");
if(find(T, key) == NULL) {
cout << "Inserted key does not exist in the tree!" << endl;
} else {
cout << "Inserted key exists!" << endl;
}
break;
}
case 4: // Find minimum
{
cout << "Minimum: ";
cout << minimum(T)->key << endl;
cout << endl;
break;
}
case 5: // Find maximum
{
cout << "Maximum: ";
cout << maximum(T)->key << endl;
cout << endl;
break;
}
case 6: // Find predecessor
{
int key = getInt("Insert a key: ");
node* x = find(T, key);
if(x == NULL) {
cout << "This key does not exist in the tree!" << endl;
break;
}
node* predec = predecessor(x);
if(predec == NULL) {
cout << "The node with key '" << key << "' does not have a predecessor." << endl;
break;
}
cout << "Predecessor of key '" << key << "' is: ";
cout << predec->key << endl;
break;
}
case 7: // Find successor
{
int key = getInt("Insert a key: ");
node* x = find(T, key);
if(x == NULL) {
cout << "This key does not exist in the tree!" << endl;
break;
}
node* succ = successor(x);
if(succ == NULL) {
cout << "The node with key '" << key << "' does not have a successor." << endl;
break;
}
cout << "Successor of key '" << key << "' is: ";
cout << succ->key << endl;
break;
}
case 8: // Remove data
{
int key = getInt("Insert a key: ");
remove(T, key);
break;
}
case 9: // Remove element
{
int key = getInt("Insert a key: ");
node* x = find(T, key);
if(x == NULL) {
cout << "This key does not exist in the tree!" << endl;
break;
}
int count = 1;
element* e = x->list;
while(e->next != NULL) {
++count;
e = e->next;
}
if(count == 1) {
cout << "Node with key '" << key << "' already has only one element!" << endl;
break;
}
// select a random element from the list to remove
int i = rand() % count;
e = x->list;
while(i > 0) {
e = e->next;
--i;
}
remove(T, key, e);
break;
}
case 10: // Exit
{
return 0;
}
}
}
}
int showMenu()
{
cout << endl;
cout << "Binary search tree - menu:" << endl;
cout << endl;
cout << "1) Insert data" << endl;
cout << "2) Sorted output" << endl;
cout << "3) Search" << endl;
cout << "4) Find minimum" << endl;
cout << "5) Find maximum" << endl;
cout << "6) Find predecessor" << endl;
cout << "7) Find successor" << endl;
cout << "8) Remove data" << endl;
cout << "9) Remove element" << endl;
cout << "10) Exit" << endl;
cout << endl;
int option;
do {
option = getInt("Choose: ");
} while(option<1 || option>10);
cout << endl;
return option;
}
int getInt(string prompt)
{
int output;
string input;
while(true) {
cout << prompt;
getline(cin, input);
stringstream ss(input);
if(ss >> output && !(ss >> input)) {
return output;
}
cin.clear();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.