Red Black Tree (JS)

RedBlackTree.js

class Node {
    constructor(value, color = 'RED') {
        this.value = value;
        this.color = color; // Nodes start as RED
        this.left = null;
        this.right = null;
        this.parent = null;
    }

    isRed() {
        return this.color === 'RED';
    }

    isBlack() {
        return this.color === 'BLACK';
    }

    setBlack() {
        this.color = 'BLACK';
    }

    setRed() {
        this.color = 'RED';
    }

    // Toggle color between RED and BLACK
    toggleColor() {
        this.color = this.isRed() ? 'BLACK' : 'RED';
    }
}

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

    // Insert a new node with a given value
    insert(value) {
        const newNode = new Node(value);
        if (!this.root) {
            // New root is always black
            newNode.setBlack();
            this.root = newNode;
            return;
        }

        // Standard BST insertion
        let current = this.root;
        let parent;
        while (current) {
            parent = current;
            if (value < current.value) {
                current = current.left;
            } else if (value > current.value) {
                current = current.right;
            } else {
                return; // No duplicate values allowed
            }
        }

        newNode.parent = parent;
        if (value < parent.value) {
            parent.left = newNode;
        } else {
            parent.right = newNode;
        }

        this.fixInsert(newNode); // Restore Red-Black properties
    }

    // Fix any Red-Black Tree violations after insertion
    fixInsert(node) {
        while (node !== this.root && node.parent.isRed()) {
            let parent = node.parent;
            let grandparent = parent.parent;

            if (parent === grandparent.left) {
                // Case where parent is the left child
                let uncle = grandparent.right;
                if (uncle && uncle.isRed()) {
                    // Case 1: Uncle is red, recolor
                    parent.setBlack();
                    uncle.setBlack();
                    grandparent.setRed();
                    node = grandparent;
                } else {
                    if (node === parent.right) {
                        // Case 2: Uncle is black, node is right child (Left-Right case)
                        this.rotateLeft(parent);
                        node = parent;
                        parent = node.parent;
                    }
                    // Case 3: Uncle is black, node is left child (Left-Left case)
                    parent.setBlack();
                    grandparent.setRed();
                    this.rotateRight(grandparent);
                }
            } else {
                // Mirror cases: parent is the right child
                let uncle = grandparent.left;
                if (uncle && uncle.isRed()) {
                    // Case 1: Uncle is red, recolor
                    parent.setBlack();
                    uncle.setBlack();
                    grandparent.setRed();
                    node = grandparent;
                } else {
                    if (node === parent.left) {
                        // Case 2: Uncle is black, node is left child (Right-Left case)
                        this.rotateRight(parent);
                        node = parent;
                        parent = node.parent;
                    }
                    // Case 3: Uncle is black, node is right child (Right-Right case)
                    parent.setBlack();
                    grandparent.setRed();
                    this.rotateLeft(grandparent);
                }
            }
        }
        this.root.setBlack();
    }

    // Left rotation
    rotateLeft(node) {
        const rightChild = node.right;
        node.right = rightChild.left;

        if (rightChild.left) {
            rightChild.left.parent = node;
        }
        rightChild.parent = node.parent;

        if (!node.parent) {
            this.root = rightChild;
        } else if (node === node.parent.left) {
            node.parent.left = rightChild;
        } else {
            node.parent.right = rightChild;
        }

        rightChild.left = node;
        node.parent = rightChild;
    }

    // Right rotation
    rotateRight(node) {
        const leftChild = node.left;
        node.left = leftChild.right;

        if (leftChild.right) {
            leftChild.right.parent = node;
        }
        leftChild.parent = node.parent;

        if (!node.parent) {
            this.root = leftChild;
        } else if (node === node.parent.left) {
            node.parent.left = leftChild;
        } else {
            node.parent.right = leftChild;
        }

        leftChild.right = node;
        node.parent = leftChild;
    }

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

// Example usage:
const rbt = new RedBlackTree();
rbt.insert(10);
rbt.insert(20);
rbt.insert(30);
rbt.insert(15);
console.log("In-order traversal:", rbt.inOrderTraversal());