avl.js

const max = (a, b) => (a > b) ? a : b;

const height = (node) => node == null ? 0 : node.height;

const calculateBalance = (node) => node == null ? 0 : height(node.left) - height(node.right);

const minValNode = (node) => {
    let temp = node;
    while (temp.left != null)
        temp = temp.left;
    return temp;
};

const rotateRight = (x2) => {
    let x = x2.left;
    let temp = x.right;
    x.right = x2;
    x2.left = temp;
    x2.height = max(height(x2.left), height(x2.right)) + 1;
    x.height = max(height(x.left), height(x.right)) + 1;
    return x;
};

const rotateLeft = (y2) => {
    let y = y2.right;
    let temp = y.left;
    y.left = y2;
    y2.right = temp;
    y2.height = max(height(y2.left), height(y2.right)) + 1;
    y.height = max(height(y.left), height(y.right)) + 1;
    return y;
};

const insertNode = (node, key) => {
    if (node == null)
        return {
            left: null,
            right: null,
            key: key,
            height: 1
        };

    if (key < node.key)
        node.left = insertNode(node.left, key);
    else if (key > node.key)
        node.right = insertNode(node.right, key);
    else
        return node;

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

    let balanced = calculateBalance(node);

    // RR
    if (balanced < -1 && key > node.right.key) {
        console.log("\nRR");
        return rotateLeft(node);
    }

    // LL
    if (balanced > 1 && key < node.left.key) {
        console.log("\nLL");
        return rotateRight(node);
    }

    // RL
    if (balanced < -1 && key < node.right.key) {
        console.log("\nRL");
        node.right = rotateRight(node.right);
        return rotateLeft(node);
    }

    // LR
    if (balanced > 1 && key > node.left.key) {
        console.log("\nLR");
        node.left = rotateLeft(node.left);
        return rotateRight(node);
    }

    return node;
};

const deleteNode = (root, key) => {
    if (root == null)
        return root;

    if (key < root.key)
        root.left = deleteNode(root.left, key);
    else if (key > root.key)
        root.right = deleteNode(root.right, key);
    else {
        if ((root.left == null) || (root.right == null)) {
            let temp = null;
            if (temp == root.left)
                temp = root.right;
            else
                temp = root.left;

            if (temp == null) {
                root = null;
            } else
                root = temp;
        } else {
            let temp = minValNode(root.right);
            root.key = temp.key;
            root.right = deleteNode(root.right, temp.key);
        }
    }

    if (root == null)
        return root;

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

    const balanced = calculateBalance(root);

    // RR
    if (balanced < -1 && calculateBalance(root.right) <= 0) {
        console.log("\nRR");
        return rotateLeft(root);
    }

    // LL
    if (balanced > 1 && calculateBalance(root.left) >= 0) {
        console.log("\nLL");
        return rotateRight(root);
    }

    // RL
    if (balanced < -1 && calculateBalance(root.right) > 0) {
        console.log("\nRL");
        root.right = rotateRight(root.right);
        return rotateLeft(root);
    }

    // LR
    if (balanced > 1 && calculateBalance(root.left) < 0) {
        console.log("\nLR");
        root.left = rotateLeft(root.left);
        return rotateRight(root);
    }

    return root;
};

const draw = (tree) => {
    const drawHelper = (node, depth, arr, right) => {
        if (node == null)
            return;

        depth++;
        drawHelper(node.right, depth, arr, 1);

        if (depth > 1) {
            arr[depth - (1 + 1)] = 0;

            if (right)
                arr[depth - (1 + 1)] = 1;
        }

        if (node.left)
            arr[depth - 1] = 1;

        console.log();
        for (let i = 0; i < depth - 1; i++) {
            if (i + 1 == depth - 1 || arr[i])
                process.stdout.write("-");
            else
                process.stdout.write(" ");

            for (let j = 1; j < 4; j++)
                if (i + 1 < depth - 1)
                    process.stdout.write(" ");
                else
                    process.stdout.write("-");
        }

        console.log(node.key);
        for (let i = 0; i < depth; i++) {
            if (arr[i])
                process.stdout.write("-");

            for (let j = 1; j < 4; j++)
                process.stdout.write(" ");
        }
        drawHelper(node.left, depth, arr, 0);
    }

    let arr = new Array(255).fill(0);
    drawHelper(tree, 0, arr, 0);
}


// Main
let treeRoot;
treeRoot = insertNode(treeRoot, 50);
treeRoot = insertNode(treeRoot, 25);
treeRoot = insertNode(treeRoot, 100);
treeRoot = insertNode(treeRoot, 150);
treeRoot = insertNode(treeRoot, 75);
treeRoot = insertNode(treeRoot, 125);
treeRoot = insertNode(treeRoot, 175);
treeRoot = insertNode(treeRoot, 65);
treeRoot = insertNode(treeRoot, 85);

draw(treeRoot);
treeRoot = deleteNode(treeRoot, 100);
treeRoot = deleteNode(treeRoot, 85);

draw(treeRoot);