AVL Tree (JS)

AVLTree.js

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
        this.height = 1; // Height of the node for balance factor calculations
    }
}

class AVLTree {
    constructor() {
        this.root = null;
    }

    // Get the height of a node
    getHeight(node) {
        return node ? node.height : 0;
    }

    // Calculate balance factor of a node
    getBalanceFactor(node) {
        return node ? this.getHeight(node.left) - this.getHeight(node.right) : 0;
    }

    // Update the height of a node
    updateHeight(node) {
        node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));
    }

    // Right rotation for balancing
    rotateRight(y) {
        console.log(`Right rotation on ${y.value}`);
        const x = y.left;
        const T2 = x.right;

        x.right = y;
        y.left = T2;

        this.updateHeight(y);
        this.updateHeight(x);

        return x;
    }

    // Left rotation for balancing
    rotateLeft(x) {
        console.log(`Left rotation on ${x.value}`);
        const y = x.right;
        const T2 = y.left;

        y.left = x;
        x.right = T2;

        this.updateHeight(x);
        this.updateHeight(y);

        return y;
    }

    // Insert a value into the AVL Tree
    insert(value, node = this.root) {
        if (!node) {
            if (!this.root) this.root = new Node(value);
            return new Node(value);
        }

        if (value < node.value) {
            node.left = this.insert(value, node.left);
        } else if (value > node.value) {
            node.right = this.insert(value, node.right);
        } else {
            return node; // Duplicates are not allowed
        }

        // Update the height of the ancestor node
        this.updateHeight(node);

        // Get the balance factor to check if this node is unbalanced
        const balanceFactor = this.getBalanceFactor(node);
        console.log(`Node: ${node.value}, Balance Factor: ${balanceFactor}`);

        // Left Left Case
        if (balanceFactor > 1 && value < node.left.value) {
            return this.rotateRight(node);
        }

        // Right Right Case
        if (balanceFactor < -1 && value > node.right.value) {
            return this.rotateLeft(node);
        }

        // Left Right Case
        if (balanceFactor > 1 && value > node.left.value) {
            node.left = this.rotateLeft(node.left);
            return this.rotateRight(node);
        }

        // Right Left Case
        if (balanceFactor < -1 && value < node.right.value) {
            node.right = this.rotateRight(node.right);
            return this.rotateLeft(node);
        }

        return node;
    }

    // Public insert method to update root correctly
    add(value) {
        this.root = this.insert(value, this.root);
    }

    // In-order traversal for displaying the tree
    inOrderTraversal(node = this.root, values = []) {
        if (node) {
            this.inOrderTraversal(node.left, values);
            values.push(node.value);
            this.inOrderTraversal(node.right, values);
        }
        return values;
    }

    // Search for a value in the AVL Tree
    search(value, node = this.root) {
        if (!node) return false;
        if (value === node.value) return true;
        return value < node.value
            ? this.search(value, node.left)
            : this.search(value, node.right);
    }
}

// Example usage to trigger rotations
const avl = new AVLTree();
avl.add(30);
avl.add(20);
avl.add(10); // Should trigger a Right rotation at 30 (Left-Left case)
avl.add(40);
avl.add(50); // Should trigger a Left rotation at 30 (Right-Right case)
avl.add(25); // Should trigger Left-Right rotation at 20
avl.add(45); // Should trigger Right-Left rotation at 50

console.log("In-order traversal:", avl.inOrderTraversal());