Avl

class Demo<K extends Comparable<K>, V> {
    private class Node {
        K key;
        V value;
        int height;
        Node left, right;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.height = 1;
        }
    }

    private Node root;

    // Utility function to get the height of the tree
    private int height(Node node) {
        if (node == null) return 0;
        return node.height;
    }

    // Utility function to get the maximum of two integers
    private int max(int a, int b) {
        return (a > b) ? a : b;
    }

    // Right rotate subtree rooted with y
    private Node rightRotate(Node y) {
        Node x = y.left;
        Node T2 = x.right;

        // Perform rotation
        x.right = y;
        y.left = T2;

        // Update heights
        y.height = max(height(y.left), height(y.right)) + 1;
        x.height = max(height(x.left), height(x.right)) + 1;

        // Return new root
        return x;
    }

    // Left rotate subtree rooted with x
    private Node leftRotate(Node x) {
        Node y = x.right;
        Node T2 = y.left;

        // Perform rotation
        y.left = x;
        x.right = T2;

        // Update heights
        x.height = max(height(x.left), height(x.right)) + 1;
        y.height = max(height(y.left), height(y.right)) + 1;

        // Return new root
        return y;
    }

    // Get balance factor of node
    private int getBalance(Node node) {
        if (node == null) return 0;
        return height(node.left) - height(node.right);
    }

    // Insert a node
    public void insert(K key, V value) {
        root = insertNode(root, key, value);
    }

    private Node insertNode(Node node, K key, V value) {
        // 1. Perform the normal BST insertion
        if (node == null) return new Node(key, value);

        if (key.compareTo(node.key) < 0) {
            node.left = insertNode(node.left, key, value);
        } else if (key.compareTo(node.key) > 0) {
            node.right = insertNode(node.right, key, value);
        } else {
            // Duplicate keys are not allowed
            return node;
        }

        // 2. Update height of this ancestor node
        node.height = 1 + max(height(node.left), height(node.right));

        // 3. Get the balance factor of this ancestor node to check whether this node became unbalanced
        int balance = getBalance(node);

        // If this node becomes unbalanced, then there are 4 cases

        // Left Left Case
        if (balance > 1 && key.compareTo(node.left.key) < 0) {
            return rightRotate(node);
        }

        // Right Right Case
        if (balance < -1 && key.compareTo(node.right.key) > 0) {
            return leftRotate(node);
        }

        // Left Right Case
        if (balance > 1 && key.compareTo(node.left.key) > 0) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // Right Left Case
        if (balance < -1 && key.compareTo(node.right.key) < 0) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        // Return the (unchanged) node pointer
        return node;
    }

    // Method to print tree in order
    public void inorder() {
        inorderRec(root);
    }

    private void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.key + " ");
            inorderRec(root.right);
        }
    }

    public static void main(String[] args) {
        Demo<Integer, String> tree = new Demo<>();

        /* Constructing tree given in the above figure */
        tree.insert(9, "Nine");
        tree.insert(5, "Five");
        tree.insert(10, "Ten");
        tree.insert(0, "Zero");
        tree.insert(6, "Six");
        tree.insert(11, "Eleven");
        tree.insert(-1, "Minus One");
        tree.insert(1, "One");
        tree.insert(2, "Two");

        

        System.out.println("Inorder traversal of the constructed AVL tree is:");
        tree.inorder();

        /* The AVL Tree after deletion of 10
                 1
                /  \
               0    9
             /     /  \
           -1     5     11
                /  \
               2    6
        */
    }
}