jsschools

Red-Black Tree

A self-balancing BST that enforces five color-based properties to guarantee O(log n) worst-case operations with fewer rotations than an AVL tree.

Spec ↗

Syntax

// Nodes are colored RED or BLACK.
// Properties ensure no path from root to leaf is more than
// twice as long as any other such path.
class RBNode { constructor(val) { this.val = val; this.color = 'RED';
  this.left = null; this.right = null; this.parent = null; } }

Parameters

NameTypeRequiredDescription
val any Yes The value stored at this node.

Returns

RedBlackTree — A self-balancing Red-Black tree instance.

Examples

// Conceptual outline — full implementation is verbose.
// The five invariants:
// 1. Every node is RED or BLACK.
// 2. The root is BLACK.
// 3. All leaf (null) nodes are BLACK.
// 4. A RED node's children are BLACK.
// 5. All paths from a node to its NULL descendants contain
//    the same number of BLACK nodes (black-height).

// JavaScript's built-in Map/Set use Red-Black trees internally
// in most V8 versions.
const m = new Map([[3, 'c'], [1, 'a'], [2, 'b']]);
console.log([...m.keys()].sort((a, b) => a - b));
Output 
[ 1, 2, 3 ]

// Demonstrate stable O(log n) insert regardless of input order
// (conceptual — using sorted input that would degenerate a plain BST)
const sorted = Array.from({ length: 1_000 }, (_, i) => i);
// In a plain BST this creates a degenerate linked list (height 1000).
// A Red-Black tree rebalances to height ≤ 2*log2(1001) ≈ 20.
console.log('max RB height ≤', Math.ceil(2 * Math.log2(1001)));
Output 
max RB height ≤ 20

Notes

| Operation | Best | Avg | Worst | Space | |----------|---------|---------|---------|-------| | Search | O(log n)| O(log n)| O(log n)| O(n) | | Insert | O(log n)| O(log n)| O(log n)| O(n) | | Delete | O(log n)| O(log n)| O(log n)| O(n) | Red-Black trees perform at most 2 rotations on insert (AVL may do O(log n)), making them preferred for write-heavy workloads (e.g., Linux kernel CFS scheduler, std::map in C++, Java TreeMap). AVL trees are preferred when reads dominate.

See also