DSA DSA In Depth
0%
From-Scratch Build

Left-Leaning Red-Black Order-Statistic Tree

A Left-Leaning Red-Black (LLRB) balanced binary search tree augmented with subtree sizes to support O(log n) insertion, deletion, rank(key), select(k), and range cardinality queries.

~50 min Advanced Lessons: Build Lab: Left-Leaning Red-Black (LLRB) Order-Statistic Tree with rank and select, 2-3-4 Trees, Red-Black Trees & Sedgewick's Left-Leaning Red-Black (LLRB) Isomorphism, Tree Rotations & AVL Trees: Balance Factors, LL/RR/LR/RL Rebalancing & Fibonacci Height Bound, Augmenting BSTs: Order-Statistic Trees (select/rank) & Interval Trees, Randomized Treaps & Implicit Treaps: Rebalancing Without Rotations via split and merge, Skip Lists: Probabilistic Multi-Level Indexing & O(log N) Search Proof
Interactive Build Lab 0/4 Steps Completed

Code & Verify in the Browser Workbench

Complete 4 progressive engineering steps in JavaScript or TypeScript against an in-browser Node.js v22 runtime (virtual filesystem, loopback TCP/HTTP, and automated unit tests) — zero local setup required.

Architecture & 2-3 Tree Isomorphism

Standard Red-Black trees require separate left/right cases across multiple insertion and deletion fixup patterns. Robert Sedgewick's Left-Leaning Red-Black (LLRB) tree establishes a strict 1-to-1 bijection with 2-3 trees by enforcing that all red links lean left:

  1. No node has a red right child (isRed(h.right) === false).
  2. No node has two consecutive left red links (isRed(h.left) && isRed(h.left.left) === false).
  3. Perfect black balance: every path from the root to a null link traverses the exact same number of black links.

Because of this invariant, bottom-up insertion cleanup collapses into just three conditional statements in _fixUp(h):

js
if (this._isRed(h.right) && !this._isRed(h.left)) h = this._rotateLeft(h);
if (this._isRed(h.left) && this._isRed(h.left.left)) h = this._rotateRight(h);
if (this._isRed(h.left) && this._isRed(h.right)) this._flipColors(h);

Subtree Size Augmentation for Order Statistics

By storing node.size = 1 + size(node.left) + size(node.right) in every node and updating it in $O(1)$ during rotations, our balanced BST becomes an Order-Statistic Tree:

  • select(k): Returns the $k$-th smallest key ($0 \le k < n$) in $O(\log n)$ time by comparing $k$ against leftSize = size(curr.left).
  • rank(key): Returns the count of keys strictly less than key in $O(\log n)$ time by accumulating 1 + size(curr.left) whenever descending right.
  • rangeCount(lo, hi): Computes the exact number of elements in $[\text{lo}, \text{hi}]$ in $O(\log n)$ time via rank(hi) - rank(lo) + (has(hi) ? 1 : 0).

Deletion via Red-Link Pushing

Deletion in a 2-3 tree is trivial if we never land on a 2-node at a leaf. On the way down the tree, _moveRedLeft and _moveRedRight borrow from a sibling or merge across the parent so that the current search node always carries a red link, guaranteeing $O(\log n)$ worst-case deletion.

Curriculum Connections

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Rotations, Color Flips & Size Maintenance

  • Core Mechanical Concept: Rotations, Color Flips & Size Maintenance
  • Target Module: index.js (Step1)
  • Engineering Specification: Implement _rotateLeft(h), _rotateRight(h), and _flipColors(h). Whenever links rotate, preserve the parent link color (x.color = h.color; h.color = RED) and recompute subtree sizes bottom-up.
  • Verification Invariant: verifies Step 1: Rotations, Color Flips & Size Maintenance

Step 2: LLRB Insertion & 3-Line FixUp

  • Core Mechanical Concept: LLRB Insertion & 3-Line FixUp
  • Target Module: index.js (Step2)
  • Engineering Specification: Implement _put(h, key, value) and _fixUp(h). Every 2-3 tree insertion maps to 3 local rules on the return path: rotate right-leaning red links left, rotate consecutive left-leaning red links right, and flip colors when both children are red.
  • Verification Invariant: verifies Step 2: LLRB Insertion & 3-Line FixUp

Step 3: Order Statistics (rank & select)

  • Core Mechanical Concept: Order Statistics (rank & select)
  • Target Module: index.js (Step3)
  • Engineering Specification: Use the node.size augmentation to implement rank(key) (number of keys < key) and select(k) (the 0-indexed $k$-th smallest key) in $O(\log n)$ time.
  • Verification Invariant: verifies Step 3: Order Statistics (rank & select)

Step 4: Top-Down 2-3-4 Deletion with Red-Link Pushing

  • Core Mechanical Concept: Top-Down 2-3-4 Deletion with Red-Link Pushing
  • Target Module: index.js (Step4)
  • Engineering Specification: Implement delete(key) using Sedgewick's _moveRedLeft and _moveRedRight helpers so the current node is never a 2-node on the descent path, followed by _fixUp on ascent.
  • Verification Invariant: verifies Step 4: Top-Down 2-3-4 Deletion with Red-Link Pushing

Asymptotic & Memory Layout Guarantees

  • Category: Balanced Trees & Augmentation
  • Difficulty: Advanced (~50 minutes)
  • Key Architectural Highlights:
    • Sedgewick Left-Leaning Red-Black (LLRB) 2-3 tree isomorphism with 3 local fixup operations
    • Subtree size augmentation maintained across rotateLeft, rotateRight, and moveRedLeft/Right
    • O(log n) order-statistic queries: rank(key), select(k), and rangeCount(lo, hi)
  • Tags & Primitives: LLRB Tree, 2-3 Tree Isomorphism, Order Statistics, Tree Rotations, Rank & Select

Production Systems Context & Verification

This from-scratch implementation is engineered with zero external dependencies and deterministic verification harnesses. Every internal invariant—from pointer restoration and bitmask addressing to amortized potential bounds and tree height balance—is asserted directly in test.js. Use the interactive browser workbench above to complete the guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.