2-3-4 Trees, Red-Black Trees & Sedgewick's Left-Leaning Red-Black (LLRB) Isomorphism

The Four Classical Red-Black Invariants & The 2-3-4 B-Tree Bijection

In a standard Red-Black Tree (CLRS Chapter 13), every node (or incoming parent link) is colored either Red or Black subject to four invariants:

1. Root Rule: The root is always Black.
2. External Leaf Rule: Every null leaf sentinel is Black.
3. Red Rule (No Red-Red Parent-Child): If a node is Red, both of its children are Black.
4. Black-Height Rule (Perfect 2-3-4 Balance): Every simple path from any node $u$ down to any descendant null leaf contains the exact same number of Black nodes, denoted $\text{bh}(u)$ (the black-height).

Sedgewick's Left-Leaning (LLRB 2-3) Simplification: If we forbid 4-nodes from persisting at rest and force every 3-node's red glue edge to lean left, then right-leaning red links are illegal and two consecutive left-leaning red links represent a temporary 4-node awaiting a split (flipColors). Every LLRB insertion ascending the recursion stack runs the exact same 3 if-statements:

1. if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h); — Lean a right-leaning 3-node to the left.
2. if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); — Balance a skewed temporary 4-node so its two children are both red.
3. if (isRed(h.left) && isRed(h.right)) flipColors(h); — Split the temporary 4-node into two 2-nodes and pass the middle key up to the parent as a red link!

Implementation: Complete Sedgewick LLRB Insertion Engine

// C++20: Sedgewick Left-Leaning Red-Black (LLRB) Tree Insertion in 45 Lines
struct LLRBNode {
    int key;
    bool red = true; // New nodes are always inserted with a RED incoming link
    LLRBNode *left = nullptr, *right = nullptr;
    explicit LLRBNode(int k) : key(k) {}
};

inline bool isRed(const LLRBNode* x) noexcept { return x != nullptr && x->red; }

LLRBNode* rotateLeft(LLRBNode* h) noexcept {
    LLRBNode* x = h->right;
    h->right = x->left;
    x->left = h;
    x->red = h->red;
    h->red = true;
    return x;
}

LLRBNode* rotateRight(LLRBNode* h) noexcept {
    LLRBNode* x = h->left;
    h->left = x->right;
    x->right = h;
    x->red = h->red;
    h->red = true;
    return x;
}

void flipColors(LLRBNode* h) noexcept {
    h->red = !h->red;
    h->left->red = !h->left->red;
    h->right->red = !h->right->red;
}

LLRBNode* insertNode(LLRBNode* h, int key) {
    if (!h) return new LLRBNode(key);
    if (key < h->key)      h->left  = insertNode(h->left, key);
    else if (key > h->key) h->right = insertNode(h->right, key);

    // The 3-line LLRB invariant restoration pipeline:
    if (isRed(h->right) && !isRed(h->left))     h = rotateLeft(h);
    if (isRed(h->left)  && isRed(h->left->left)) h = rotateRight(h);
    if (isRed(h->left)  && isRed(h->right))      flipColors(h);
    return h;
}