import java.util.*;

public class Main {

    static int rotations = 0;

    static class Node {
        int key;
        Node left;
        Node right;
        int height;

        Node(int key) {
            this.key = key;
            this.left = null;
            this.right = null;
            this.height = 1;
        }
    }

    // Create a new node
    public static Node createNode(int key) {
        return new Node(key);
    }

    // Return stored height
    public static int height(Node node) {
        if (node == null)
            return 0;

        return node.height;
    }

    // Calculate balance factor
    public static int getBalance(Node node) {
        if (node == null)
            return 0;

        return height(node.left) - height(node.right);
    }

    // Right Rotation
    public static Node rightRotate(Node y) {

        rotations++;

        Node x = y.left;
        Node T2 = x.right;

        // Rotation
        x.right = y;
        y.left = T2;

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

        x.height = 1 + Math.max(
            height(x.left),
            height(x.right)
        );

        return x;
    }

    // Left Rotation
    public static Node leftRotate(Node x) {

        rotations++;

        Node y = x.right;
        Node T2 = y.left;

        // Rotation
        y.left = x;
        x.right = T2;

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

        y.height = 1 + Math.max(
            height(y.left),
            height(y.right)
        );

        return y;
    }

    // AVL Insertion
    public static Node insert(Node node, int key) {

        //  Normal BST insertion
        if (node == null) {
            return createNode(key);
        }

        if (key < node.key) {
            node.left = insert(node.left, key);
        }
        else if (key > node.key) {
            node.right = insert(node.right, key);
        }
        else {
            return node; // for Duplicate keys
        }

        //  Update height
        node.height = 1 + Math.max(
            height(node.left),
            height(node.right)
        );

        // Calculate balance factor
        int balance = getBalance(node);

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

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

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

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

        return node;
    }
    
    // Find the node with the smallest key in a subtree
    public static Node minValueNode(Node node) {
        Node current = node;

        while (current.left != null) {
            current = current.left;
        }

        return current;
    }

    // AVL Deletion
    public static Node deleteNode(Node root, int key) {

        // normal BST deletion
        if (root == null) {
            return null;
        }

        if (key < root.key) {
            root.left = deleteNode(root.left, key);
        }
        else if (key > root.key) {
            root.right = deleteNode(root.right, key);
        }
        else {

            //Node has no child or only a right child
            if (root.left == null) {
                return root.right;
            }

            // Node has only a left child
            else if (root.right == null) {
                return root.left;
            }

            //Node has two children
            Node successor = minValueNode(root.right);

            //inorder successor's key
            root.key = successor.key;

            // Delete the inorder successor
            root.right = deleteNode(root.right, successor.key);
        }

        root.height = 1 + Math.max(
            height(root.left),
            height(root.right)
        );

        //balance factor
        int balance = getBalance(root);

        // LL Case
        if (balance > 1 && getBalance(root.left) >= 0) {
            return rightRotate(root);
        }

        // LR Case
        if (balance > 1 && getBalance(root.left) < 0) {
            root.left = leftRotate(root.left);
            return rightRotate(root);
        }

        //  RR Case
        if (balance < -1 && getBalance(root.right) <= 0) {
            return leftRotate(root);
        }

        // RL Case
        if (balance < -1 && getBalance(root.right) > 0) {
            root.right = rightRotate(root.right);
            return leftRotate(root);
        }

        return root;
    }


    // Inorder traversal
    public static void inorder(Node root) {

        if (root == null)
            return;

        inorder(root.left);

        System.out.print(
            root.key + "(" + root.height + ") "
        );

        inorder(root.right);
    }

      
    public static void main(String[] args) {

        int[] arr = {
           50, 30, 70, 20, 40, 60, 80,
           10, 5, 15, 25, 27, 26, 65,
           62, 64, 90, 100, 95
        };

        Node root = null;

    // Insert all elements
        for (int key : arr) {
            root = insert(root, key);
        }

    
        int insertionRotations = rotations;

        System.out.println("After AVL insertion:");

        System.out.print("Inorder: ");
        inorder(root);
        System.out.println();

        if (root != null) {
            System.out.println("Root = " + root.key);
        } 
        else {
            System.out.println("Root = null");
        }

        System.out.println("Insertion rotations = " + insertionRotations);

       // Reset counter
       rotations = 0;

       //Delete keys
       int[] deleteKeys = {70, 20, 50, 10, 90};

       for (int key : deleteKeys) {
 
          root = deleteNode(root, key);

          System.out.println("\nAfter deleting " + key + ":");

          System.out.print("Inorder: ");
          inorder(root);
          System.out.println();

          if (root == null) {
              System.out.println("Root = null");
          }
          else {
              System.out.println("Root = " + root.key);
          }  

          System.out.println("Rotations so far = " + rotations);
    }

        // Final deletion rotation count
        System.out.println("\nTotal deletion rotations = " + rotations);
} 

}