A Red-Black Tree is a self-balancing binary search tree where each node carries an extra bit: its color (red or black). The color constraints ensure the tree remains approximately balanced, guaranteeing O(log n) time for search, insertion, and deletion.

Why Red-Black Trees?

Standard BSTs degrade to O(n) when inputs arrive sorted. Red-Black Trees enforce balance through color invariants — a simpler mental model than AVL rotations, and widely used in production (Linux kernel, Java TreeMap, C++ std::map).

The Five Invariants

Every valid Red-Black Tree satisfies:

  1. Node Color — Every node is either red or black.
  2. Root Property — The root is always black.
  3. Leaf Property — All NIL (null) leaves are black.
  4. Red Property — A red node cannot have a red child (no two consecutive reds).
  5. Black-Height Property — Every path from a node to its descendant NIL leaves contains the same number of black nodes.

These five rules guarantee the longest path is at most 2× the shortest path, bounding tree height to 2 log(n+1).

Core Operations

A complete Red-Black Tree implementation requires these functions:

Primitives (Building Blocks)

Function Purpose Complexity
leftRotate(node) Rotate node down-left, its right child up O(1)
rightRotate(node) Rotate node down-right, its left child up O(1)
transplant(u, v) Replace subtree rooted at u with subtree rooted at v O(1)
minimum(node) Find leftmost descendant (in-order successor helper) O(log n)

Public API

Function Purpose Complexity
search(key) Find node by key O(log n)
insert(key, value) Add new node, then fix violations O(log n)
delete(key) Remove node, then fix violations O(log n)