import java.util.Scanner;

public class AVLTree<T extends Comparable<T>> {
    class Node {
        T value;
        Node left, right;
        int height = 0;
        int bf = 0;

        public Node(T ele) {
            this.value = ele;
            this.left = this.right = null;
        }
    }

    private Node root;

    public boolean contains(T ele) {
        if (ele == null) {
            return false;
        }
        return contains(root, ele);
    }
    private boolean contains(Node node, T ele) {
        if(node == null) return false;
        int cmp = ele.compareTo(node.value);
        if (cmp > 0)
            return contains(node.right, ele);
        else if (cmp < 0)
            return contains(node.left, ele);
        return true;
    }

    public boolean insert(T ele) {
        if (ele == null || contains(ele))
            return false;
        root = insert(root, ele);
        return true;
    }
    private Node insert(Node node, T ele) {
        if (node == null)
            return new Node(ele);
        int cmp = ele.compareTo(node.value);
        if (cmp < 0)
            node.left = insert(node.left, ele);
        else
            node.right = insert(node.right, ele);
        update(node);
        return balance(node);
    }

    public boolean delete(T ele) {
        if (ele == null || !contains(ele))
            return false;

        root = delete(root, ele);
        return true;
    }
    private Node delete(Node node, T ele) {
        int cmp = ele.compareTo(node.value);
        if (cmp > 0)
            node.right = delete(node.right, ele);
        else if (cmp < 0)
            node.left = delete(node.left, ele);
        else {
            if (node.right == null)
                return node.left;
            else if (node.left == null)
                return node.right;
            if (node.left.height > node.right.height) {
                T successor = findMax(node.left);
                node.value = successor;
                node.left = delete(node.left, successor);
            } else {
                T successor = findMin(node.right);
                node.value = successor;
                node.right = delete(node.right, successor);
            }
        }
        update(node);
        return balance(node);
    }

    private T findMax(Node node) {
        while (node.right != null) {
            node = node.right;
        }
        return node.value;
    }
    private T findMin(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        return node.value;
    }

    private void update(Node node) {
        int leftSubTreeHeight = (node.left == null) ? -1 : node.left.height;
        int rightSubTreeHeight = (node.right == null) ? -1 : node.right.height;

        node.height = 1 + Math.max(leftSubTreeHeight, rightSubTreeHeight);
        node.bf = leftSubTreeHeight - rightSubTreeHeight;
    }

    private Node balance(Node node) {
        if (node.bf == 2) {
            if (node.left.bf >= 0) {
                return leftLeftRotation(node);
            } else {
                return leftRightRotation(node);
            }
        } else if (node.bf == -2) {
            if (node.right.bf >= 0) {
                return rightLeftRotation(node);
            } else {
                return rightRightRotation(node);
            }
        }
        return node;
    }

    private Node leftLeftRotation(Node node) {
        Node newParent = node.left;
        node.left = newParent.right;
        newParent.right = node;
        update(node);
        update(newParent);
        return newParent;
    }
    private Node rightRightRotation(Node node) {
        Node newParent = node.right;
        node.right = newParent.left;
        newParent.left = node;
        update(node);
        update(newParent);
        return newParent;
    }
    private Node leftRightRotation(Node node) {
        node.left = rightRightRotation(node.left);
        return leftLeftRotation(node);
    }
    private Node rightLeftRotation(Node node) {
        node.right = leftLeftRotation(node.right);
        return rightRightRotation(node);
    }

    public void inorder() {
        if (root == null)
            return;
        inorder(root);
        System.out.println();
    }
    private void inorder(Node node) {
        if(node == null) return;
        inorder(node.left);
        System.out.print(node.value + " ");
        inorder(node.right);
    }
    
    public void preorder() {
        if (root == null)
        return;
        preorder(root);
        System.out.println();
    }
    private void preorder(Node node) {
        if(node == null) return;
        System.out.print(node.value + " ");
        preorder(node.left);
        preorder(node.right);
    }
    
    public void postorder() {
        if (root == null)
        return;
        postorder(root);
        System.out.println();
    }
    private void postorder(Node node) {
        if(node == null) return;
        postorder(node.left);
        postorder(node.right);
        System.out.print(node.value + " ");
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        AVLTree<Integer> avl = new AVLTree<>();
        int ch;
        do {
            System.out.println("1. Insert a value");
            System.out.println("2. Delete a value");
            System.out.println("3. Display");
            System.out.println("4. Exit");
            System.out.print("Enter choice: ");
            ch = sc.nextInt();
            switch (ch) {
                case 1:
                    System.out.print("Enter value: ");
                    int ele = sc.nextInt();
                    if(!avl.insert(ele)) {
                        System.out.println("Invalid input");
                    }
                    break;
                case 2:
                    System.out.print("Enter value: ");
                    if(!avl.delete(sc.nextInt())) {
                        System.out.println("Invalid input");
                    }
                    break;
                case 3:
                    avl.preorder();
                    break;
                case 4:
                    System.exit(0);
                    break;
            
                default:
                    break;
            }
        } while(ch != 4);
        sc.close();
    }
}