/*********************************
Name:			Mary Soy
Date:			11-13-09
Class:			3333
Professor:		Schweller
File:			AVLTree.h
*********************************/
#include <iostream>
#include <string>
using namespace std;

class node
{
public:
	node()
	{
		right = NULL;
		left = NULL;
		height = 0;
	}

	string data;
	node * right;
	node * left;
	int height;
};

class bst
{
public:
	bst();

	void insert(string s);
    void display();

	//string find(string s);

private:
	void rightRotation( node * & r );
	void leftRotation( node * & r );
	void doubleRotationRight( node * & r );
	void doubleRotationLeft( node * & r );

	int height(node *);
	void recInsert(string s, node * & root);
	void recDisplay(node * r);
	node * root;
};

bst::bst()
{
	root = NULL;
}

int bst::height(node * p)
{
	if( p == NULL )
		return -1;
	else
		return p->height;
}


void bst::rightRotation( node * & r )
{
	node * a = r;
	node * b = r->right;
	node * bleft = b->left;

	r = b;
	a->right = bleft;
	b->left = a;

	a->height = max( height(a->right), height(a->left) ) +1;
	b->height = max( height(b->right), height(b->left) ) +1;
}


void bst::leftRotation( node * & r )
{
	node * a = r;
	node * b = r->left;
	node * bright = b->right;

	r = b;
	a->left = bright;
	b->right = a;

	a->height = max( height(a->right), height(a->left) ) +1;
	b->height = max( height(b->right), height(b->left) ) +1;
}
void bst::doubleRotationRight( node * & r )
{
	leftRotation( r->right );
	rightRotation( r );
}
void bst::doubleRotationLeft( node * & r )
{
	rightRotation( r->left );
	leftRotation( r );
}




void bst::recInsert(string s, node * & r)
{
	if( r == NULL )  //base case: empty tree
	{
		r = new node;
		r->data = s;
		r->height = 0;
	}
	else if( s < r->data  ) //insert left
	{
		recInsert(s, r->left);

		if( height(r->left) - height(r->right) > 1 )
		{  //violation!
			//do some type of rotation
			if( s < r->left->data )
				leftRotation(r);
			else //its a double
				doubleRotationLeft(r);
		}

		r->height = max( height(r->left), height(r->right) ) +1;
	}
	else//insert right, if greater or equal to root
	{
		recInsert(s, r->right);

		if( height(r->right) - height(r->left) > 1 )
		{
			if( s > r->right->data )
				rightRotation(r);
			else
				doubleRotationRight(r);
		}

		r->height = max( height(r->left), height(r->right) ) +1;
	}
}

void bst::insert(string s)
{
	recInsert(s, root);
}

void bst::recDisplay(node * r)
{
	if( r != NULL )
	{
		cout << r->data << endl;
		recDisplay(r->left);
		recDisplay(r->right);
	}
}

void bst::display()
{
	recDisplay(root);
}