/*********************************************************************
*
*	AVL tree, for LU COSC1374, Spring 2003,  by Chung-Chih Li, 
*
**********************************************************************/

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

long COUNTER, TOTAL;

struct AVLTree 
{
	long key;
	int height; // height of the tree. 
	AVLTree  *left;
	AVLTree  *right;
};

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

template<typename T>
int height(T *t)
{
	if (t == NULL) return 0;
	int ld = height(t->left);
	int rd = height(t->right);
	return ld > rd ? ld+1 : rd+1;
}

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


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;
}


AVLTree *LL(AVLTree *t)
{
	AVLTree *newt, *old_lr;
	old_lr = (t->left)->right;
	newt=t->left;
	newt->right = t;
	t->left = old_lr;
	t->height = (newt->height)-1;
	return newt;
}

AVLTree *LR(AVLTree *t)
{
	int h=t->height;
	AVLTree *newt, *a, *b, *c, *d;
	newt = (t->left)->right;
	a = t->left;
	b = t;
	c = ((t->left)->right)->left;
	d = ((t->left)->right)->right;
	newt->left = a;
	newt->right = b;
	(newt->left)->right = c;
	(newt->right)->left = d;
	newt->height = h;
	(newt->left)->height = (newt->right)->height = h-1;
	return newt;
}

AVLTree *RR(AVLTree *t)
{
	AVLTree *newt, *old_rl;
	old_rl = (t->right)->left;
	newt=t->right;
	newt->left = t;
	t->right = old_rl;
	t->height = (newt->height)-1;
	return newt;
}

AVLTree *RL(AVLTree *t)
{
	int h=t->height;
	AVLTree *newt, *a, *b, *c, *d;
	newt = (t->right)->left;
	a = t;
	b = t->right;
	c = ((t->right)->left)->left;
	d = ((t->right)->left)->right;
	newt->left = a;
	newt->right = b;
    (newt->left)->right = c;
	(newt->right)->left = d;
	newt->height = h;
	(newt->left)->height = (newt->right)->height = h-1;
	return newt;
}
	

// Inser key into an AVL tree
AVLTree *insert(int key, AVLTree *t)
{
	if (t == NULL)
	{
		AVLTree *temp;
		temp = new AVLTree;
		temp->key = key;
	    temp->height = 1;
		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);
	int l=0,r=0;
	if (t->left != NULL) l=(t->left)->height;
	if (t->right != NULL) r=(t->right)->height;
	if (l - r == 2)  // LL or LR rotation
	{
		int ll=0, lr=0;
		if  ((t->left)->left != NULL) ll = ((t->left)->left)->height;
		if  ((t->left)->right != NULL) lr = ((t->left)->right)->height;
		if (ll-lr == 1) // LL  rotation
			t = LL(t);
		else // if (lr-ll == 1) // LR rotation must be (lr-ll)==1
			t = LR(t);
		return t;
	}
	if (r - l == 2)  // RR or RL rotation
	{
		int rr=0, rl=0;
		if  ((t->right)->left != NULL) rl = ((t->right)->left)->height;
		if  ((t->right)->right != NULL) rr = ((t->right)->right)->height;
		if (rr-rl == 1) // RR  rotation
			t = RR(t);
		else // if (lr-ll == 1) // LR rotation must be (lr-ll)==1
			t = RL(t);
		return t;
	}
	t->height = (l > r) ? l+1 : r+1;
	return t;
}

template<typename T>
T *search(int key, T *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);
}


template<typename T>
int max(T *t)
{
	if (t->right == NULL)
		return t->key;
	return max(t->right);
}

template<typename T>
int min(T *t)
{
	if (t->left == NULL)
		return t->key;
	return max(t->left);
}


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

template<typename T> 
void iprint_tree(T *t)
{
	if (t==NULL) return;
	cout << t->key << " ";
	iprint_tree(t->left);
	iprint_tree(t->right);
}

template<typename T>
T *delete_tree(T *t)
{
	if (t == NULL) return NULL;
	if (t->left != NULL)
		delete_tree(t->left);
	if (t->right != NULL)
		delete_tree(t->right);
	delete t;
	return NULL;
}

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


cout << setw(6)  << "";
cout << setw(18) << "";
cout << setw(18) << "Search 1M keys";
cout << setw(18) << "";
cout << setw(18) << "Search 1M keys" << endl;

cout << setw(6)  << "Total";
cout << setw(18) << "Construct BST";
cout << setw(18) << "in BST";
cout << setw(18) << "Construct AVL";
cout << setw(18) << "in AVL" << endl;

cout << setw(6)  << "Nodes";
cout << setw(9) << "Sec.";
cout << setw(9) << "Height";
cout << setw(9) << "Sec.";
cout << setw(9) << "Ave # n";
cout << setw(9) << "Sec.";
cout << setw(9) << "Height";
cout << setw(9) << "Sec.";
cout << setw(9) << "Ave # n" << endl;
cout << "----------------------------------------";
cout << "---------------------------------------\n";

for (no=inc; no <= maxno; no += inc)
{

	cout << setw(7) << no;
/////////////////  Regular BST
	elp = clock();
	for (i=0; i< no; i++)	
	{
		key = rand()*i;
		bst = insert(key, bst);
	}
	cout << setw(10) << double(clock()-elp)/CLOCKS_PER_SEC;
	cout << setw(5) << height(bst);
	TOTAL = 0;
	elp = clock();
	for (i =0; i<rno; i++)
	{
		COUNTER=0;
		key = rand()*rand();
		search(key, bst);
		TOTAL += COUNTER;
	}
	cout << setw(10) << double(clock()-elp)/CLOCKS_PER_SEC;	
	cout << setw(9) << double(TOTAL)/rno;
	bst = delete_tree(bst);
/////////////////  AVL BST
	elp = clock();
	for (i=0; i< no; i++)
	{
		key = rand()*i;
		avlt = insert(key, avlt);
	}
	cout << setw(12) << double(clock()-elp)/CLOCKS_PER_SEC;
	cout << setw(5) << height(avlt);
	TOTAL = 0;
	elp = clock();
	for (i =0; i<rno; i++)
	{
		COUNTER=0;
		key =  rand()*rand();
		search(key, avlt);
		TOTAL += COUNTER;
	}
	cout << setw(10) << double(clock()-elp)/CLOCKS_PER_SEC;
	cout << setw(9) << double(TOTAL)/rno;
	avlt = delete_tree(avlt);
	cout << endl;
} 
return 0;	
}