/////IN header file

typedef struct treenode* tree;
typedef struct treenode{
	tree left;
	tree right;
	int height;
	int data;
}treenode;
///// END HEADER



class UnbalancedTreeSearcher : public ISearch

{

public:



    UnbalancedTreeSearcher(const data_array& data)

    {

        data_array::const_iterator i;
        bst=NULL;
        for(i = data.begin(); i != data.end(); i++)
        	bst=unbal_add(bst,*i);

    } 
    virtual int* find(int element){
    	return bst_find(bst,element);
    }

private:
	tree bst;

	int Max(int a, int b){
		return a>b?a:b;
	}
	int height(tree bst){
		//returns height or -1 if the node exists or not, respectively
		//this keeps the height right for leaf nodes
		if(!bst)
			return -1;
		return bst->height;
	}
	tree unbal_add(tree bst, int data){
	//adds a node with value 'data' to binary tree 'bst'
		if(bst==NULL){
			//this is the final resting place of our node, allocate and initialize it
		
			bst=(tree)malloc(sizeof(treenode));
			bst->data=data;
			bst->left=bst->right=NULL;
		}
		else if(data > bst->data)
			//add this node to the right subtree
			bst->right=unbal_add(bst->right,data);
		else if(data < bst->data)
			//add this node to the left subtree
			bst->left=unbal_add(bst->left,data);
		bst->height=Max(height(bst->left),height(bst->right))+1;
		return bst;
	}
	int* bst_find(tree bst, int data){
		if(!bst)return NULL;
		if(bst->data==data)
			return &bst->data;
		if(bst->data > data)
			return bst_find(bst->left,data);
		else
			return bst_find(bst->right,data);

	}

};

class BalancedTreeSearcher : public ISearch

{

public:



    BalancedTreeSearcher(const data_array& data)

    {

        data_array::const_iterator i;
        bst=NULL;
        for(i = data.begin(); i != data.end(); i++)
        	bst=bal_add(bst,*i);

    } 
    virtual int* find(int element){
    	return bst_find(bst,element);
    }

private:
	int Max(int a, int b){
		return a>b?a:b;
	}
	int height(tree bst){
		//returns height or -1 if the node exists or not, respectively
		//this keeps the height right for leaf nodes
		if(!bst)
			return -1;
		return bst->height;
	}
	tree bst;
	tree bal_add(tree bst, int data){
	//adds a node with value 'data' to binary tree 'bst'
		if(bst==NULL){
			//this is the final resting place of our node, allocate and initialize it
		
			bst=(tree)malloc(sizeof(treenode));
			bst->data=data;
			bst->left=bst->right=NULL;
		}
		else if(data > bst->data){
			//add this node to the right subtree
			bst->right=bal_add(bst->right,data);
			if(height(bst->right)-height(bst->left)==2)
				//if the tree is out of balance, do rotations to get it back
				if(data > bst->right->data)
					//we added to the right subtree of the right node; do a single left rotation
					bst=sleft(bst);
				else
					//we added to the left subtree of the right node; do a double left rotation
					bst=dleft(bst);
		}
		else if(data < bst->data){
			//add this node to the left subtree
			bst->left=bal_add(bst->left,data);
			if(height(bst->left)-height(bst->right)==2)
				//if the tree is out of balance, do rotations to get it back
				if(data < bst->left->data)
					//we added to the left subtree of the left node, do a single right rotation
					bst=sright(bst);
				else
					//we added to the right subtree of the left node, do a double right rotation
					bst=dright(bst);
		}
		bst->height=Max(height(bst->left),height(bst->right))+1;
		return bst;
	}
	
	tree sleft(tree tn){
	//Does a single left rotation about tn

		//reassign pointers
		tree worker=tn->right;
		tn->right=worker->left;
		worker->left=tn;
	
		//recalculate heights
		tn->height=Max(height(tn->left),height(tn->right))+1;
		worker->height=Max(height(worker->right),tn->height)+1;
	
		//return pointer to new pivot node.  when called, make sure this value is assigned, 
		//otherwise the subtree is lost and a memory leak occurs
		return worker;
	}
	tree dleft(tree tn){
	//Does a double left rotation about tn
		tn->right=sright(tn->right);
		return sleft(tn);
	}
	tree sright(tree tn){
	//Does a single right rotation about tn

		//reassign pointers
		tree worker=tn->left;
		tn->left=worker->right;
		worker->right=tn;
	
		//recalculate heights
		tn->height=Max(height(tn->left),height(tn->right))+1;
		worker->height=Max(height(worker->left),tn->height)+1;
	
		//return pointer to new pivot node
		return worker;
	}
	tree dright(tree tn){
	//Does a double right rotation about tn
		tn->left=sleft(tn->left);
		return sright(tn);
	}
	int* bst_find(tree bst, int data){
		if(!bst)return NULL;
		if(bst->data==data)
			return &bst->data;
		if(bst->data > data)
			return bst_find(bst->left,data);
		else
			return bst_find(bst->right,data);

	}

};