/**
 * Created by Mohy on 4/28/2017.
 */
public class AVLTree<T extends Comparable<T>> {
    Node root;

    int height(Node n) {
        if (n == null)
            return 0;
        return n.height;
    }

    int getHeight(Node n) {
        if (n == null)
            return 0;
        return 1 + Math.max(getHeight(n.left), getHeight(n.right));

    }

    Node rightRotate(Node n) {
        Node newRoot = n.left;
        Node temp = newRoot.right;
        newRoot.right = n;
        n.left = temp;
        n.height = Math.max(height(n.left), height(n.right)) + 1;
        newRoot.height = Math.max(height(newRoot.left), height(newRoot.right)) + 1;
        return newRoot;
    }

    Node leftRotate(Node n) {
        Node newRoot = n.right;
        Node temp = newRoot.left;
        newRoot.left = n;
        n.right = temp;
        n.height = Math.max(height(n.left), height(n.right)) + 1;
        newRoot.height = Math.max(height(newRoot.left), height(newRoot.right)) + 1;
        return newRoot;
    }
    int getBalance(Node n) {
        if (n == null) {
            return 0;
        }
        return height(n.left) - height(n.right);
    }

    Node search(Node<T> n, T key) {
        if (n == null)
            return null;
        Node temp;
        if (key.compareTo(n.key) > 0) {
            temp = search(n.left, key);
        } else temp = search(n.right, key);
        return temp;
    }

    Node insert(Node<T> n, T key) {
        if (n == null)
            return (new Node<T>(key));
        if (key.compareTo(n.key) < 0) {
            n.left = insert(n.left, key);
        } else if (key.compareTo(n.key) > 0) {
            n.right = insert(n.right, key);
        } else return n;// duplicate case not allowed
        n.height = Math.max(height(n.left), height(n.right)) + 1;
        int balance = getBalance(n);
        if (balance > 1 && key.compareTo((T) n.left.key)< 0) {//left left insertion case
            return rightRotate(n);
        }
        if (balance < -1 && n.right.key.compareTo(key) < 0) {//right right insertion case
            return leftRotate(n);
        }
        if (balance > 1 && n.left.key.compareTo(key) < 0) { //left right insertion
            n.left = leftRotate(n.left);
            return rightRotate(n);
        }
        if (balance < -1 && n.right.key.compareTo(key) > 0) {//right left insertion
            n.right = rightRotate(n.right);
            return leftRotate(n);
        }
        return n;
    }

    T getMinValue(Node node) {
        // if (node == null) return Integer.MIN_VALUE;
        if (node.left == null) return (T) node.key;
        return getMinValue(node.left);
    }

    private Node delete(Node<T> node, T data) {

        if (node == null) return null;

        if (data.compareTo(node.key) > 0) {
            node.left = delete(node.left, data);
        }
        if (data.compareTo(node.key) < 0) {
            node.right = delete(node.right, data);
        } else {

            if (node.left == null && node.right != null) {
                node = node.right;

            } else if (node.right == null && node.left != null) {
                node = node.left;
            } else {
                T O = getMinValue(node.right);
                node.key = O;
                node.right = delete(node.right, O);
            }
        }
        if (node == null) {
            return null;
        }

        node.height = getHeight(node);

        int balance = getBalance(node);

        if (balance > 1) {
            if (getBalance(node.left) >= 0) {
                node = rightRotate(node);
            } else {
                node.left = leftRotate(node.left);
                node = rightRotate(node);
            }
        } else if (balance < -1) {
            if (getBalance(node.right) <= 0) {
                node = leftRotate(node);
            } else {
                node.right = rightRotate(node.right);
                node = leftRotate(node);
            }
        }
        return node;
    }

    public static void printAvlTree(Node n) {
        if (n == null) return;
        printAvlTree(n.right);
        printAvlTree(n.left);
        System.out.print(" " + n.key);
    }

    public static void main(String[] args) {
        AVLTree<Integer> tree = new AVLTree<>();
        tree.root = tree.insert(tree.root, 5);
        tree.root = tree.insert(tree.root, 10);
        tree.root = tree.insert(tree.root, 8);
        tree.root = tree.insert(tree.root, 9);
        tree.root = tree.insert(tree.root, 7);
        printAvlTree(tree.root);
    }


}