#include <iostream>
#include <iomanip>
#include <time.h>
#include <cctype>
using namespace std;

long COUNTER, TOTAL;

struct Tree 
{
	int key;
	Tree *left;
	Tree *right;
};

int depth(Tree *t)
{
	if (t == NULL) return 0;
	int ld = depth(t->left);
	int rd = depth(t->right);
	return ld > rd ? ld+1 : rd+1;
}


bool full(Tree *t) // test if t is full
{
	if (t->left == NULL && t->right == NULL) return true;
	if (t->left == NULL && t->right != NULL) return false;
	if (t->left != NULL && t->right == NULL) return false;
	if (full(t->left) && full(t->right) &&
		depth(t->left) == depth(t->right)) return true;
	return false;
}

long no_of_nodes(Tree *t)
{
	if (t == NULL) return 0;
	return 1+no_of_nodes(t->left)+no_of_nodes(t->right);
}


Tree *balance_insert(int key, Tree *t)
{

	if (t == NULL)
	{
		Tree *temp;
		temp = new Tree;
		temp->key = key;
		temp->left = temp->right = NULL;
		return temp;
	}
	if (full(t) || !full(t->left) )
		t->left = balance_insert(key, t->left);
	else // t is not full but left is full;
		t->right = balance_insert(key, t->right);
	return t;
}


Tree *insert(int key, Tree *t)
{
	if (t == NULL)
	{
		Tree *temp;
		temp = new Tree;
		temp->key = key;
		temp->left = temp->right = NULL;
		return temp;
	}
	if (t->key > key) // go to the left;
		t->left = insert(key, t->left);
	else 
		t->right = insert(key, t->right);
	return t;
}


Tree *search(int key, Tree *t)
{
	if (t==NULL) return t;
	COUNTER++;
	if (t->key == key)
		return t;
	if (t->key > key) // go to the left;
		return search(key, t->left);
	return search(key, t->right);
}


Tree *blind_search(int key, Tree *t)
{
	if (t == NULL) return t;
	COUNTER++;
	if (t->key == key)
		return t;
	Tree *found;
	found = blind_search(key, t->left);
	if (found != NULL)
		return found;
	return blind_search(key, t->right);
}


int max(Tree *t)
{
	if (t->right == NULL)
		return t->key;
	return max(t->right);
}


int min(Tree *t)
{
	if (t->left == NULL)
		return t->key;
	return max(t->left);
}


Tree *remove(int key, Tree *t)
{
	if (t == NULL) return t;
	if (t->key > key)
	{ 
		t->left = remove(key, t->left);
		return t;
	}
	if (t->key < key)
	{
		t->right = remove(key, t->right);
		return t;
	}
	// t->key == key 
	if (t->left == NULL && t->right == NULL)
	{
		delete t;
		return NULL;
	}
	int newkey;
	if (t->left != NULL)
	{
		newkey = max(t->left);
		t->left = remove(newkey, t->left);
		t->key = newkey;
	}
	else // t->left == NULL and t->right != NULL)
	{
		newkey = min(t->right);
		t->right = remove(newkey, t->right);
		t->key = newkey;
	}
	return t;
}


void print_tree(Tree *t)
{
	if (t==NULL) return;
	print_tree(t->left);
	cout << t->key << " ";
	print_tree(t->right);
}


int main()
{
	long elp,no, inc=5000; 
	int key, i,	rno = 10000;
	Tree *bst, *tree;
	cout.setf(ios::fixed);
    cout.precision(3);
	bst = tree = NULL;
	srand(time(NULL));

cout << "  Total" <<  "   BST Search 10K keys" << "   Blind Search 10K keys " 
     << "   5K to BST" << "    5K to bal\n";
cout << "  Nodes" << setw(10) << "    Ave # n"
                  << setw(11) << "Sec."
				  << setw(10) << "    Ave # n"
                  << setw(13) << "Sec."
				  << setw(13) << "Sec,depth"
				  << setw(14) << "Sec,depth\n";
cout << "----------------------------------------";
cout << "---------------------------------------\n";

for (no=0;no <= 500000; no += inc)
{

	cout << setw(7) << no_of_nodes(bst);
	TOTAL = 0;
	elp = clock();
	for (i =0; i<rno; i++)
	{
		COUNTER=0;
		key = rand();
		search(key, bst);
		TOTAL += COUNTER;
	}
	cout << setw(11) << double(TOTAL)/rno;
	cout << setw(10) << double(clock()-elp)/CLOCKS_PER_SEC;	

	if (no < inc*10) // <= inc*10
	{ 
		TOTAL = 0;
		elp = clock();
		for (i =0; i<rno; i++)
		{
			COUNTER=0;
			key = rand();
			blind_search(key, tree);
			TOTAL += COUNTER;
		}
		cout << setw(12) << double(TOTAL)/rno;
		cout << setw(12) << double(clock()-elp)/CLOCKS_PER_SEC;
	}
	else
		cout << setw(24) << "--- skip ---     ";

	elp = clock();
	for (i=0; i< inc; i++)	
		bst = insert(rand(), bst);
	cout << setw(10) << double(clock()-elp)/CLOCKS_PER_SEC;
	cout << "," << setw(3) << depth(bst);

	if (no < inc*10) // <= inc*10
	{
		elp = clock();
		for (i=0; i< inc; i++)	
			tree = balance_insert(rand(),tree);
		cout << setw(9) << double(clock()-elp)/CLOCKS_PER_SEC; 
		cout << "," << setw(3) << depth(tree) << endl;
	}
	else
	{
		cout << " --- skip ---\n";
		tree=bst;
	}
} 
return 0;	
}