gistfile1.cpp

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <string>

#define null NULL
#define DEBUG

using namespace std;

struct node{
	int value;
	int nodeCount;

	node *left;
	node *right;
};

map<int, int> dict;
map<int, int> reverse_dict;

vector<int> v_in_order;

node* create_node(int data){
	node *newNode = new node();
	newNode->value = data;
	newNode->nodeCount = 1;

	newNode->left = null;
	newNode->right = null;

	return newNode;
}

node* insert(node* current, int data){
	if (current == null){
		current = create_node(data);
	}
	else {
		current->nodeCount += 1;

		if (data <= current->value)
			current->left = insert(current->left, data);
		else
			current->right = insert(current->right, data);
	}

	return current;
}

node* find_minimum(node* current){
	while (current->left != null)
		current = current->left;

	return current;
}

node* delete_node(node* current, int data){
	/*
	If the current node is null, then there is no tree
	under the current node

	else, use recursion to find the node
	*/
	if (current == null) return current;

	current->nodeCount -= 1;

	if (data < current->value)
		current->left = delete_node(current->left, data);
	else if (data > current->value)
		current->right = delete_node(current->right, data);
	else {
		/*
		Case 1: If the current node has no child
		Delete the current node

		Case 2: If there is one child
		Promote the left/right child to current
		position, and delete current node

		Case 3: Neither the left nor the right is NULL
		Find the minimum of the right sub-tree,
		promote it to the current position, and
		delete the minimum node on the right
		*/

		if (current->left == null && current->right == null){
			delete current;
			current = null;
		}
		else if (current->left == null || current->right == null){
			if (current->left == null){
				node* temp = current;
				current = current->right;
				delete temp;
			}
			else {
				node* temp = current;
				current = current->left;
				delete temp;
			}
		}
		else {
			node* min = find_minimum(current->right);
			current->value = min->value;
			current->right = delete_node(current->right, min->value);
		}
	}

	return current;
}

node* recalculate_nodes(node* current){
	if (current == null) return current;

	if (current->left == null && current->right == null){
		current->nodeCount = 1;
	}
	else if (current->left == null || current->right == null){
		if (current->left == null)
			current->nodeCount = current->right->nodeCount;
		else
			current->nodeCount = current->left->nodeCount;
	}
	else {
		current->nodeCount = current->left->nodeCount + current->right->nodeCount;
	}

	return current;
}

bool search(node* current, int data){
	if (current == null) return false;
	if (current->value == data) return true;

	if (data < current->value)
		return search(current->left, data);
	else
		return search(current->right, data);
}

int get_kth_greatest(node* current, int k){
#ifdef DEBUG
	cout << "greatest (" << current->value << " , " << k << " );" << endl;
#endif //DEBUG

	if (current == null) return -1;
	if (k == 0 && current->left == null) return current->value;

	if (current->left == null) return -1;
	if (current->left->nodeCount == k) return current->value;

	if (k > current->left->nodeCount)
		return get_kth_greatest(current->right, k - current->left->nodeCount - 1);
	else
		return get_kth_greatest(current->left, k);
}

void in_order(node* n){
	if (n == null) return;

	in_order(n->left);
	v_in_order.push_back(n->value);
	in_order(n->right);
}

int numbers[] = { 94, 86, 25, 85, 28, 68, 66, 90, 83, 18, 34, 5, 33, 64, 67, 50, 2, 21, 91 };

int main(){
	node *root = null;

	for (int n : numbers) root = insert(root, n);
	in_order(root);
	cout << endl;

	for (int i = 0; i < 19; i++) cout << get_kth_greatest(root, i) << endl;

	system("pause");
}