public class AVLTree {

    private class AVLNode{
        private int value;
        private AVLNode leftChild;
        private AVLNode rightChild;

        private int height;

        public AVLNode(int value){
            this.value = value;
        }

        @Override
        public String toString(){
            return "value = "+value+" height = "+height;
        }
    }

    private AVLNode root;

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

    private AVLNode insert(AVLNode root, int value) {
        if (root==null){
            return new AVLNode(value);
        }

        if (root.value > value){
             root.leftChild =insert(root.leftChild, value);
        }else{
            root.rightChild =insert(root.rightChild, value);
        }

         setHeight(root);

       return balance(root);
    }

    private AVLNode balance(AVLNode root) {
        if (isLeftHeavy(root)){
            if (balanceFactor(root.leftChild)<0)
                root.leftChild = rotateLeft(root.leftChild);
            return rotateRight(root);
        }else if (isRightHeavy(root)){
            if (balanceFactor(root.rightChild)>0)
                root.rightChild =rotateRight(root.rightChild);
            return rotateLeft(root);
        }
        return root;
    }

    private boolean isLeftHeavy(AVLNode root){
        return  balanceFactor(root) >1;
    }

    private  boolean isRightHeavy(AVLNode root){
        return balanceFactor(root)<-1;
    }

    private AVLNode rotateLeft(AVLNode root){
        var newRoot = root.rightChild;
        root.rightChild = newRoot.leftChild;
        newRoot.leftChild = root;

        setHeight(root);
        setHeight(newRoot);
        return newRoot;
    }

    private AVLNode rotateRight(AVLNode root){
        var newRoot = root.leftChild;
        root.leftChild = newRoot.rightChild;
        newRoot.rightChild = root;

        setHeight(root);
        setHeight(newRoot);

        return newRoot;
    }

    private int balanceFactor(AVLNode root){
        return height(root.leftChild)-height(root.rightChild);
    }

    private void setHeight(AVLNode root){
        root.height = Math.max(height(root.leftChild), height(root.rightChild)) + 1;
    }

    private int height(AVLNode node){
        return node == null ? -1: node.height;
    }


}