🌲 Red-Black Tree — Self-Balancing BST

A left rotation around node x makes x's right child y become the new subtree root, moving x down to y's left child and adopting y's former left subtree as x's new right child. It is applied when the tree has a right-leaning imbalance — specifically during insertion when the new red node is a right child of a right child (the "right-right" case in insertion fix-up).

Let bh(x) be the black-height of node x. By the no-consecutive-reds rule, at most half the nodes on any root-to-leaf path can be red, so the actual height h ≤ 2·bh(root). The subtree rooted at any node with black-height k contains at least 2^k−1 internal nodes, so n ≥ 2^bh−1, giving bh ≤ log₂(n+1) and h ≤ 2·log₂(n+1).

Linux's Completely Fair Scheduler (CFS) stores runnable processes in a red-black tree keyed by virtual runtime, so the process with the smallest runtime (the next to run) can be found in O(log n) time. The kernel's memory manager uses red-black trees to track virtual memory areas (VMAs) per process, and the epoll subsystem uses them to manage file descriptors efficiently.

A 2-3-4 tree (or B-tree of order 4) stores 1–3 keys per node with 2–4 children, maintaining perfect balance. Every 2-3-4 tree maps exactly to a red-black tree: a 2-node becomes a single black node; a 3-node becomes a black node with a red child; a 4-node becomes a black node with two red children. This correspondence gives an alternative proof of red-black tree correctness and underpins the LLRB (left-leaning red-black) tree variant.

The LLRB variant, popularised by Robert Sedgewick (2008), adds the constraint that red links always lean left (a red node is always a left child). This reduces the number of structural cases to handle during insertion and deletion from about 6–8 to 3, resulting in implementations of roughly 50 lines of code versus 200+ for the standard Cormen-Leiserson-Rivest formulation. Java's TreeMap uses the standard formulation; some functional language libraries prefer LLRB.

Yes. Because each insertion or deletion modifies only O(log n) nodes (along the path from root to the affected leaf), a persistent red-black tree can be created by path-copying: duplicating only the O(log n) nodes that change and sharing the rest. This gives O(log n) time and space per operation with full version history, and is used in persistent functional data structures such as Clojure's sorted maps.

Deletion first performs a standard BST deletion (replacing the node with its in-order successor if it has two children). If the deleted node or its replacement was red, no black-height violation occurs. If a black node is removed, a "double-black" deficit propagates upward and is resolved by six cases of sibling-colour and nephew-colour analysis, each either re-rooting a subtree with rotations and recolouring, or pushing the deficit up. At most three rotations suffice.