JavaScript AVL tree

Binary search tree

This is tree there every node have only two childs, left and right. Left node contain value less his vertex, right vertex contain value more that parent vertex.

AVL tree

AVL tree is a self-balancing Binary Search Tree where the difference between heights of left and right subtrees cannot be more than one for all nodes. If difference bitween heights is bigger, balancing should fix difference.

Node

For avl tree need to have the balance factor, it is difference between right and left heights.

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

    getBalanceFactor() {
        const lHeight = this.left ? this.left.height : 0;
        const rHeight = this.right ? this.right.height : 0;
        return rHeight - lHeight;
    }

    fixHeight() {
        const lHeight = this.left ? this.left.height : 0;
        const rHeight = this.right ? this.right.height : 0;
        this.height = (lHeight > rHeight ? lHeight : rHeight) + 1;
    }
}

Balancing

Balancing of tree uses methods of left and right rotation.

Left rotating is applying if right height more that left height. It make right node is root. Previous root became a left node of new root. Previous root loose right node, and it replace left node from current root, so previous root receive new right node - it is old left node from current root.

Before

{
    key: 1,
    height: 3,
    left: undefined,
    right: {
        key: 2,
        height: 2,
        left: undefined,
        right: {
            key: 3,
            height: 1,
            left: undefined,
            right: undefined
        }
    }
}

After

{
    key: 2,
    height: 2,
    left: {
        key: 1,
        height: 1,
        left: undefined,
        right: undefined
    },
    right: {
        key: 3,
        height: 1,
        left: undefined,
        right: undefined
    }
}

Right rotating is applying if left height more that right height. It make left node is root. Previous root became a right node of new root. Previous root loose left node, and it replace right node from current root, so previous root receive new left node - it is old right node from current root.

Before

{
    key: 3,
    height: 3,
    left: {
        key: 2,
        height: 2,
        left: {
            key: 1,
            height: 1,
            left: undefined,
            right: undefined,
        },
        right: undefined,
    },
    right: undefined,
}

After

{
    key: 2,
    height: 2,
    left: {
        key: 1,
        height: 1,
        left: undefined,
        right: undefined
    },
    right: {
        key: 3,
        height: 1,
        left: undefined,
        right: undefined
    }
}

Balance method apply left rotation if right height more that left height. If right node have negative balance - two left nodes. Right rotation applying to this node before. For left height applying equal procedure.

Insertion

If value is less that value of vertex need to insert this into left node, if bigger in right node. After insertion need to apply balancing.

Removing

If value is less that value of node, need to remove node from left, if bigger from right. After node is found, and have child vertexes, if node have no right vertex just need to replace by this left node. If node contain right child, need to find minimum for right tree. For minimum we should assign left node - are the left children of removed vertex, and after possible to replace removed node to minimum.

Code for tree

class Tree {
    constructor() {
        this.root = undefined;
    }

    rotateLeft(node) {
        const root = node.right;

        const left = node;
        left.right = root.left;
        root.left = left;

        left.fixHeight();
        root.fixHeight();

        return root;
    }

    rotateRight(node) {
        const root = node.left;

        const right = node;
        right.left = root.right;
        root.right = right;

        right.fixHeight();
        root.fixHeight();

        return root;
    }

    balance(node) {
        node.fixHeight();

        if (node.getBalanceFactor() === 2 ) {
            if (node.right.getBalanceFactor() < 0) {
                node.right = this.rotateRight(node.right);
            }
            return this.rotateLeft(node);
        }

        if (node.getBalanceFactor() === -2) {
            if (node.left.getBalanceFactor() > 0) {
                node.left = this.rotateLeft(node.left);
            }
            return this.rotateRight(node);
        }

        return node;
    }

    insert(node) {
        if (! this.root) {
            this.root = node;
            return;
        }
        this.root = this._insert(this.root, node);
    }

    _insert(vertex, node) {
        if (node.key === vertex.key) {
            return vertex;
        }
        if (node.key < vertex.key) {
            if (! vertex.left) {
                vertex.left = node;
            } else {
                vertex.left = this._insert(vertex.left, node);
            }
        } else {
            if (! vertex.right) {
                vertex.right = node;
            } else {
                vertex.right = this._insert(vertex.right, node);
            }
        }

        return this.balance(vertex);
    }

    findMin(node) {
        return node.left ? this.findMin(node.left) : node;
    }

    removeMin(node) {
        if (! node.left) {
            return node.right;
        }
        node.left = this.removeMin(node.left);
        return this.balance(node);
    }

    remove(k) {
        this.root = this._remove(this.root, k);
        return this.root;
    }

    _remove(node, k) {
        if (! node) {
            return;
        }

        if (k < node.key) {
            node.left = this._remove(node.left, k);
        } else if (k > node.key) {
            node.right = this._remove(node.right, k);
        } else {
            const left = node.left;
            const right = node.right;

            if (! right) {
                return left;
            }

            const min = this.findMin(right);
            min.left = left;
            min.right = this.removeMin(right);

            node = this.balance(min);
        }

        return node;
    }

    find(k, node) {
        if (! node) {
            node = this.root;
        }

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