class Node{
    constructor(d){
        this.key = d;
        this.height = 1
        this.left  = null
        this.right = null
    }

}

class AVLTree{

    constructor(){
        this.root = null
    }

    height(node){
        if(node==null)return 0;
        return node.height;
    }

    rightRotate(y){
        let x = y.left
        let T2 = x.right
        //rotation
        x.right = y
        y.left = T2
         //update height
        x.height = Math.max(this.height(x.left),this.height(x.right))+1
        y.height = Math.max(this.height(y.left),this.height(y.right))+1

        return x;

    }

    leftRotate(x){
        let y = x.right
        let T2 = y.left
        //rotation
        y.left = x
        x.right = T2
        //update height
        x.height = Math.max(this.height(x.left),this.height(x.right))+1
        y.height = Math.max(this.height(y.left),this.height(y.right))+1

        return y;
    }
    getBalance(N){
        if(N==null)return 0;
        return this.height(N.left) - this.height(N.right);
    }

    insert(node,key){
        if(node==null) return new Node(key);

        if(key<node.key){
            node.left = this.insert(node.left,key);
        }else if(key>node.key){
            node.right = this.insert(node.right,key);
        }else return node;

        node.height = 1 + Math.max(this.height(node.left),this.height(node.right))

        let balance = this.getBalance(node)

        if(balance > 1 && key<node.left.key){
            return this.rightRotate(node);
        }
        if(balance > 1 && key>node.left.key){
            node.left = this.leftRotate(node.left)
            return this.rightRotate(node);
        }
        if(balance < -1 && key>node.right.key){
            return this.leftRotate(node);
        }
        if(balance < -1 && key<node.right.key){
            node.right = this.rightRotate(node.right);
            return this.leftRotate(node)
        }
        return node
    }
}

let tree = new AVLTree()
tree.root = tree.insert(tree.root, 10);
tree.root = tree.insert(tree.root, 20);
tree.root = tree.insert(tree.root, 30);
tree.root = tree.insert(tree.root, 40);
tree.root = tree.insert(tree.root, 50);
tree.root = tree.insert(tree.root, 25);



console.log(tree)