public class AVLtree {

	private AVLNode root;

	public AVLtree() {
		root = null;
	}

	public void makeEmpty() {
		root = null;

	}

	public boolean isEmpty() {
		return root == null;
	}

	public void printTree() {
		if (isEmpty())

			System.out.println("Tree is Empty!");
		else
			printTree(root);

	}

	public void printTree(AVLNode n) {
		printTree(n.left);
		System.out.println(n.data + " (" + height(n) + ")");
	}

	public void insert(int x) {
		root = insert(x, root);
	}

	private AVLNode insert(int x, AVLNode n) {
		if (n == null)
			return new AVLNode(x, null, null);
		if (x < n.data) {
			n.left = insert(x, n.left);
			if (height(n.left) - height(n.right) == 2)
				if (x < n.left.data)
					n = rotateLeft(n);
				else
					n = doubleLeft(n);
		} else if (x > n.data) {
			n.right = insert(x, n.right);
			if (height(n.right) - height(n.left) == 2)
				if (x < n.right.data)
					n = rotateRight(n);
				else
					n = doubleRight(n);
		} else
			n.height = Math.max(height(n.left), height(n.right)) + 1;
		return n;
	}

	public boolean search(int x) {
		return search(x, root);
	}

	public boolean search(int x, AVLNode n) {
		while (n != null) {
			if (x < n.data)
				n = n.left;
			else if (x > n.data)
				n = n.right;

			else
				return true;
		}
		return false;
	}

	private int height(AVLNode n) {
		if (n == null)
			return -1;
		else
			return n.height;
	}

	private AVLNode rotateLeft(AVLNode node) {

		AVLNode node1 = node.left;
		node1.left = node.right;
		node.right = node1;
		node1.height = Math.max(height(node1.left), height(node1.right)) + 1;
		node.height = Math.max(height(node.left), node1.height) + 1;
		return node;
	}

	private AVLNode rotateRight(AVLNode node) {

		AVLNode node1 = node.right;
		node.right = node1.left;
		node1.left = node;
		node.height = Math.max(height(node.left), height(node.right)) + 1;
		node.height = Math.max(height(node1.right), node.height) + 1;
		return node1;
	}

	private AVLNode doubleLeft(AVLNode node3) {
		node3.left = rotateRight(node3.left);
		return rotateLeft(node3);

	}

	private AVLNode doubleRight(AVLNode node1) {
		node1.right = rotateLeft(node1.right);
		return rotateRight(node1);
	}
}