public class AVLNode {
    private AVLNode left, right;
    private Comparable data;
    private int leftHeight;
    private int rightHeight;
    private AVLTree tree; //the tree that the node belongs to
    // true if running in a testing mode, false otherwise
    // if false, no priting will be done
    private boolean testing = true;
    
    public AVLNode(Comparable data, AVLTree tree){
	this.data = data;
	this.tree = tree;
    }
    
    public AVLNode getLeft(){
	return left;
    }
    
    public AVLNode getRight(){
	return right;
    }

    public void setLeft(AVLNode left){
	this.left = left;
    }

    public void setRight(AVLNode right){
	this.right = right;
    }
    
    public Comparable getData() {
	return data;
    }

    public void inOrder() {
	if (left != null) left.inOrder();
	System.out.println(data);
	if (right != null) right.inOrder();    
    }

    public void preOrder() {
	System.out.println(data);
	if (left != null) left.preOrder();	
	if (right != null) right.preOrder();    
    }    
    
    public int getBalance() {
	// the absolute value of the height difference
	return Math.abs(leftHeight - rightHeight);
    }

    // recursive insert. Takes a parent node. Returns the height of the 
    // tree rooted at this node
    // Performs all necessary rebalancing 
    public int insert(Comparable data, AVLNode parent) {
	if (data.compareTo(this.data) < 0) {
	    if (left != null) { 
		leftHeight = left.insert(data, this);
	    } else {
		// left is null, inserting the node at the left
		left = new AVLNode(data, tree);
		leftHeight = 1;
	    }
	} else {
	    if (right != null) {
		rightHeight = right.insert(data, this);
	    } else {
	    // right is null, inserting the node at the right
		right = new AVLNode(data, tree);
		rightHeight = 1;
	    }
	}
	// rebalance the tree if needed
	if (getBalance() == 2) {
	    testPrint("Need to rebalance");
	    // figure out which of the four cases take place
	    if (data.compareTo(this.data) < 0) {
		testPrint("data = " + data + " this.data = " + 
				   this.data + " left.data " + left.getData());
		// if the data was inserted to the left
		if (data.compareTo(left.getData()) < 0) {
		    // single R rotation
		    testPrint("single R");
		    return singleR(data, parent);
		} else {
		    // zigzag: LR rotation
		    testPrint("double LR");
		    return doubleLR(data, parent);
		}
	    } else {
		// if the data was inserted to the right
		if (data.compareTo(right.data) > 0) {
		    // single L rotation
		    testPrint("single L");
		    return singleL(data, parent);
		} else {
		    // zigzag: RL rotation
		    testPrint("double RL");
		    return doubleRL(data, parent);
		}
	    }
	}
        return 1 + Math.max(leftHeight,rightHeight);
    }

    // performs a single right rotation 
    // returns the height of the new subtree
    // Assume that this is the rotation that needs to be performed
    private int singleR(Comparable data, AVLNode parent) {
    	// saving away a reference to the left node
	AVLNode myleft = left;

	// rearranging the tree 
	left = left.right;
	myleft.right = this;
	// resetting the heights of the changed nodes
	leftHeight = myleft.rightHeight;
	myleft.rightHeight = Math.max(leftHeight, rightHeight) + 1;

	// if this node is not the root, reset the parent's 
	// reference and height
	if (parent != null) {
	    // we don't know if this node is the left child of its parent or 
	    // the right one, need both cases
	    if (parent.left == this) {
		// if this node is the left child of its parent
		parent.left = myleft;	
		parent.leftHeight = Math.max(myleft.leftHeight, 
					     myleft.rightHeight) + 1;
	    } else {
		// this node is the right child of its parent
		parent.right = myleft;
		parent.rightHeight = Math.max(myleft.leftHeight, 
					      myleft.rightHeight) + 1;
	    }
	} else {
	    // this node is the root, has no parent
	    // need to reset the root reference of the tree
	    tree.setRoot(myleft);
	}
	// the height of the tree rooted at myleft (new root)
	return 1 + Math.max(myleft.leftHeight,myleft.rightHeight);
    }

    private int singleL(Comparable data, AVLNode parent) {
	// this stub needs to be replaced by real code
	// now it returns the height of the tree rooted at this node
	return 1 + Math.max(leftHeight,rightHeight);
    }

    private int doubleLR(Comparable data, AVLNode parent) {
	// this stub needs to be replaced by real code
	// now it returns the height of the tree rooted at this node
	return 1 + Math.max(leftHeight,rightHeight);
    }

    private int doubleRL(Comparable data, AVLNode parent) {
	// this stub needs to be replaced by real code
	// now it returns the height of the tree rooted at this node
	return 1 + Math.max(leftHeight,rightHeight);
    }

    // prints only when in testing mode
    private void testPrint(String s) {
	if (testing) {
	    System.out.println(s);
	}
    }
}

public class AVLTree {
    private AVLNode root;
    
    public AVLTree() {
    }
    
    public boolean isEmpty() {
	return (root == null);
    }
    
    public AVLNode getRoot(){
	return root;
    }
    
    public AVLNode search(Comparable data) {
        AVLNode node = root;

        while (node != null && data.compareTo(node.getData()) !=  0){
            if (data.compareTo(node.getData()) < 0){
                node = node.getLeft();
            } else {
                node = node.getRight();
            }
        }
        return node;
    }
 
    // recursive insert
    public int insert(Comparable data) {
	if (root == null) {
	    root = new AVLNode(data, this);
	    return 1;
	} 
	return root.insert(data, null);
    }

    public void setRoot(AVLNode newroot) {
	root = newroot;
    }
	
    public void inOrder() {
        if (root != null) root.inOrder();
    }

    public void preOrder() {
        if (root != null) root.preOrder();
    }
}

public class AVLTest {
    public static void main(String [] args) {
	AVLTree avl = new AVLTree();
	String [] strings = {"tomatoes", "strawberries","oranges", "kiwi", "apples"
	    //"grapes", "cucumbers", "apples", "kiwi", "tomatoes"
	    //"strawberries", "bananas", "oranges",  
	    //"pumpkins"
	};

	for (int i = 0; i < strings.length; ++i) {
	    System.out.println(avl.insert(strings[i]));
	}

	System.out.println("In-order:");
	avl.inOrder();

	System.out.println("Pre-order:");
	avl.preOrder();
    }

}