/**
* Implements an AVL tree.
* Note that all "matching" is based on the compareTo method.
* @author Mark Allen Weiss
* adapted to BinarySearchTree interface D. Gruntz
*/
public class AVLSearchTree implements BinarySearchTree {

	/** The tree root. */
	private Node root;

	public BinarySearchTreeNode getRoot(){
		return root;
	}

	/**
	* Test if the tree is logically empty.
	* @return true if empty, false otherwise.
	*/
	public boolean isEmpty() {
		return root == null;
	}

	public int size(){
		return size(root);
	}
	
	private static int size(Node p){
		if(p==null)return 0;
		else return 1 + size(p.left) + size(p.right);
	}
	
	public int height(){
		return height(root);
	}
	
	/**
	* Return the height of node t, or -1, if null.
	*/
	private static int height(Node t) {
		return t == null ? -1 : t.height;
	}

	/**
	* Find an item in the tree.
	* @param x the item to search for.
	* @return the matching item or null if not found.
	*/
	public Object search(Comparable key) {
		return search(root, key);
	}

	/**
	* Internal method to find an item in a subtree.
	* @param x is item to search for.
	* @param t the node that roots the tree.
	* @return node containing the matched item.
	*/
	private Object search(Node t, Comparable x) {
		while(t != null)
			if(x.compareTo(t.key) < 0)
				t = t.left;
			else if(x.compareTo(t.key) > 0)
				t = t.right;
			else
				return t.element;    // Match

		return null;   // No match
	}

	/**
	* Insert into the tree; duplicates are ignored.
	* @param x the item to insert.
	*/
	public void insert(Comparable key, Object element) {
		root = insert(root, key, element);
	}

	/**
	* Internal method to insert into a subtree.
	* @param x the item to insert.
	* @param t the node that roots the tree.
	* @return the new root.
	*/
	private Node insert(Node p, Comparable key, Object element) {
		if(p == null)
			p = new Node(key, element);
		else {
			int c = key.compareTo(p.key);
			if(c < 0) {
				p.left = insert(p.left, key, element);
				if(height(p.left) - height(p.right) == 2)
					if(height(p.left.left) > height(p.left.right))
						p = rotateR(p);
					else
						p = rotateLR(p);
			}
			else if(c > 0) {
				p.right = insert(p.right, key, element);
				if(height(p.right) - height(p.left) == 2)
					if(height(p.right.right) > height(p.right.left))
						p = rotateL(p);
					else
						p = rotateRL(p);
			}
			else
				p.element = element;
		}
		p.height = Math.max(height(p.left), height(p.right)) + 1;
		return p;
	}

	/**
	* Remove from the tree. Nothing is done if x is not found.
	* @param x the item to remove.
	*/
	public void remove (Comparable key){
		root = remove(root, key);	
	}
	
	/**
	* Internal method to remove out of a subtree.
	* @param key the item to remove.
	* @param p the node that roots the tree.
	* @return the new root.
	*/
	private Node remove(Node p, Comparable key){
		/* NOT YET IMPLEMENTED */
		return p;
	}
	
	/**
	* Rotate binary tree node with left child.
	* For AVL trees, this is a single rotation for case 1.
	* Update heights, then return new root.
	*/
	private static Node rotateR(Node k2) {
		Node k1 = k2.left;
		k2.left = k1.right;
		k1.right = k2;
		k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
		k1.height = Math.max(height(k1.left), k2.height) + 1;
		return k1;
	}

	/**
	* Rotate binary tree node with right child.
	* For AVL trees, this is a single rotation for case 4.
	* Update heights, then return new root.
	*/
	private static Node rotateL(Node k1) {
		Node k2 = k1.right;
		k1.right = k2.left;
		k2.left = k1;
		k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
		k2.height = Math.max(height(k2.right), k1.height) + 1;
		return k2;
	}

	/**
	* Double rotate binary tree node: first left child
	* with its right child; then node k3 with new left child.
	* For AVL trees, this is a double rotation for case 2.
	* Update heights, then return new root.
	*/
	private static Node rotateLR(Node k3) {
		k3.left = rotateL(k3.left);
		return rotateR(k3);
	}

	/**
	* Double rotate binary tree node: first right child
	* with its left child; then node k1 with new right child.
	* For AVL trees, this is a double rotation for case 3.
	* Update heights, then return new root.
	*/
	private static Node rotateRL(Node k1) {
		k1.right = rotateR(k1.right);
		return rotateL(k1);
	}


	// Test program
	public static void main(String [ ] args) {
		AVLSearchTree t = new AVLSearchTree();
		final int NUMS = 4000;
		final int GAP  =   37;

		System.out.println("Checking... (no more output means success)");

		for(int i = GAP; i != 0; i = (i + GAP) % NUMS)
			t.insert(new Integer(i), new Integer(i));

		for(int i = 1; i < NUMS; i++)
		if(((Integer)(t.search(new Integer(i)))).intValue() != i)
			System.out.println("Find error1!");
	}
}

class Node implements BinarySearchTreeNode {
	Comparable key;
	Object element;
	Node left, right;
	int height;

	Node(Comparable key){this(key, null);}
	Node(Comparable key, Object element){
		this.key = key; this.element = element;
	}
	Node(Comparable key, Object element, Node left, Node right){
		this(key, element); this.left = left; this.right = right;
	}
	
	public Object getKey(){return key;}
	public BinarySearchTreeNode getLeft(){return left;}
	public BinarySearchTreeNode getRight(){return right;}
}