/**
 *	@ AVLTree.java
 *	@ Designed by BySelf
 */

/**
 *	AVLTree
 *		Class of AVLTree. 
 *	NOTE:
 *		# You should implemment the code left for you, for this homework.
 *		# If you are still not clear about what AVLTree is, you'd better 
 *		   see the powerpoint in this direcory.
 *		# Submit your homework before 0:00 this Saturday.
 *		# You can ask BySelf on bbs anytime you has question.
 */
class AVLTree 
{
	/**
	 *	private AVLTreeNode root;
	 *		The root of this AVLTree.
	 */
	private AVLTreeNode root;

	/**
	 *	Constructor
	 *		Construct a new empty AVLTree, whose root is null.
	 */
	AVLTree()
	{
		root = null;
	}

	/**
	 *	public void remove(int object)
	 *		Delete the tree node whose value is object.
	 *	NOTE:
	 *		The node must be in this tree, otherwise throw exceprion.
	 */
	public void remove(int object)
	{
		AVLTreeNode toDelete = search(object);
		if (isNewNode(toDelete, object))
		{
			throw new RuntimeException("The node to delete is not in this tree");
		}
		delete(toDelete);
	}

	/**
	 *	public void add(int object)
	 *		Add a new node with value _object_ into this tree.
	 *	NOTE:
	 *		If any node in this tree with value _object_ exist, will cause exception.
	 */
	public void add(int object)
	{
		AVLTreeNode newNode = new AVLTreeNode(object);
		AVLTreeNode searchParent = search(object);
		if (!isNewNode(searchParent, object))
		{
			throw new RuntimeException("The node to add is already in this tree");
		}
		insert(searchParent, newNode);
	}

	/** 
	 *	private AVLTreeNode search(int value)
	 *		Search for the node in this tree whose value is given, if 
	 *		no node is found, return the node which will be the parent
	 *		node after a new node whose value is given be inserted into
	 *		this tree (before re-arrange for balance).
	 *	EXAMPLE:
	 *		This tree is currently a 3 nodes tree like:
	 *						[5]
	 *					 [1]   [8]
	 *		when search(5), return the root node
	 *		when search(3), also return the root node 5, for it will be the 
	 *			parent after 3 inserted.
	 */
	private AVLTreeNode search(int value)
	{
		if (root == null)
			return null;

		// fill your code here
		// if you like change the return value
		AVLTreeNode current = root;
		
		while (current.getLeftChild() != null || current.getRightChild() != null)
		{
			if (value == current.getValue())
				return current;
			else if (value < current.getValue())
			{
				if (current.getLeftChild() == null)
					return current;
				current = current.getLeftChild();
			}
			else
			{
				if (current.getRightChild() == null)
					return current;
				current = current.getRightChild();
			}
		}
		return current;	
	}

	/**
	 *	priavte boolean isNewNode(AVLTreeNode node, int value)
	 *		Decide whether the node returned from search is the same as the 
	 *		node we search for.
	 *	NOTE:
	 *		If node.value == value, the node with _value_ is in this tree.
	 */
	private boolean isNewNode(AVLTreeNode node, int value)
	{
		if ( node == null )
			return true;
		return (node.getValue() != value);
	}

	/**
	 *	private void delete(AVLTreeNode toDelete)
	 *		Delete the node toDelete from this AVLTree.
	 *	NOTE:
	 *		# Here are several things you should do:
	 *			1. remove toDelete from this tree
	 *			2. change subTreeHeight
	 *			3. re-arrange the tree, to make this tree balance again
	 *		# Make sure the result tree is balance, and all the node's balance value
	 *		  are correct.
	 *		# The balance value of tree leaf is always 0.
	 */
	private void delete(AVLTreeNode toDelete)
	{
		// fill your code here
		AVLTreeNode node = toDelete.getParent();
		AVLTreeNode newRoot, temp;
		
	/*the node toDelete is the root of the tree*/	
		if ( node == null)
		{
			if ( root.getLeftChild() == null && root.getRightChild() == null)
				root = null;
			else if ( root.getLeftChild() == null )
			{
				root = root.getRightChild();
				root.setParent(null);
				root.setSubTreeHeight(0);
				root.balanceValue = 0;
			}
			else if ( root.getRightChild() == null )
			{
				root = root.getLeftChild();
				root.setSubTreeHeight(0);
				root.balanceValue = 0;
			}
			else
			{
				newRoot= root.getLeftChild();
				if ( newRoot.getRightChild() == null )
				{
					newRoot.setRightChild( root.getRightChild() );
					root.getRightChild().setParent( newRoot );
					root = newRoot;
					root.setSubHeight( root );
					root.setBalance( root );
				}
				else
				{
					while ( newRoot.getRightChild() != null)
						newRoot = newRoot.getRightChild();
					newRoot.getParent().setRightChild( null );
					temp = newRoot.getParent();
					while ( temp != root )
					{
						temp.setSubHeight(temp);
						temp.setBalance(temp);
						temp = temp.getParent();
					}
					newRoot.setParent( null );
					newRoot.setLeftChild( root.getLeftChild() );
					newRoot.setRightChild( root.getRightChild() );
					root.getLeftChild().setParent( newRoot );
					root.getRightChild().setParent( newRoot );
					root = newRoot;
					if ( root.getLeftChild().balanceValue == 1 && root.getLeftChild().getRightChild() == null )
						root.getLeftChild().rotateRight();
					root.setSubHeight( root );
					root.setBalance( root );
				}
			}
			return;
		}

		
	/*the node toDelete is on the left branch of it's parent*/
		if ( node.getLeftChild() == toDelete)
		{
			if ( toDelete.getLeftChild() == null && toDelete.getRightChild() == null )
			{
				node.setLeftChild(null);
				if ( node.balanceValue == 0 )
				{
					node.setSubHeight(node);
					node.setBalance(node);
					node = root;
				}
			}
			else if ( toDelete.getLeftChild() == null )
			{
				toDelete.getRightChild().setParent( node );
				node.setLeftChild( toDelete.getRightChild() );
			}
			else if ( toDelete.getRightChild() == null )
			{
				toDelete.getLeftChild().setParent( node );
				node.setLeftChild( toDelete.getLeftChild() );
			}
			else
			{
				temp = toDelete.getLeftChild();
				if ( temp.getRightChild() != null )
				{
					while ( temp.getRightChild() != null )
						temp = temp.getRightChild();
					temp.setLeftChild( toDelete.getLeftChild() );
					toDelete.getLeftChild().setParent( temp );
					temp.setRightChild( toDelete.getRightChild() );
					toDelete.getRightChild().setParent( temp );
				}
				else
				{
					temp.setRightChild( toDelete.getRightChild() );
					toDelete.getRightChild().setParent( temp );
				}
				temp.setParent( node );
				node.setLeftChild( temp );
				temp.setSubHeight( temp );
				temp.setBalance( temp );
				if ( temp.balanceValue == -1 && temp.getRightChild().balanceValue == -1)
					temp.getRightChild().rotateLeft();
			}

			if ( node.balanceValue != -1 )
				node.balanceValue --;
			else if ( node == root && root.getRightChild().balanceValue == 1 )
			{
				root.getRightChild().rotateRight();
				root.getRightChild().rotateLeft();
			}
			else 
			{	
				if ( node.getRightChild().balanceValue == 1 )
				{
					node.getRightChild().rotateRight();
					node.getRightChild().rotateLeft();
				}
				else
					node.getRightChild().rotateLeft();
			}
			
		}

	/*the node toDelete is on the right branch of it's parent*/
		else
		{
			if ( toDelete.getLeftChild() == null && toDelete.getRightChild() == null )
			{	
				node.setRightChild(null);
				if ( node.balanceValue == 0 )
				{
					node.setSubHeight(node);
					node.setBalance(node);
					node = root;
				}
			}
			else if ( toDelete.getLeftChild() == null )
			{
				toDelete.getRightChild().setParent( node );
				node.setRightChild( toDelete.getRightChild() );
			}
			else if ( toDelete.getRightChild() == null )
			{
				toDelete.getLeftChild().setParent( node );
				node.setRightChild( toDelete.getLeftChild() );
			}
			else
			{
				temp = toDelete.getLeftChild();
				if ( temp.getRightChild() != null)
				{
					while ( temp.getRightChild() != null)
						temp = temp.getRightChild();
					temp.setLeftChild( toDelete.getLeftChild() );
					toDelete.getLeftChild().setParent( temp );
					temp.setRightChild( toDelete.getRightChild() );
					toDelete.getRightChild().setParent( temp );
				}
				else
				{