An implementation of Binary Search Tree data structure.

BinarySearchTree.cpp

#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();
	}
}