Red-Black Trees

Self-balancing binary search trees that recolor and rotate to keep height logarithmic.

What is it?

Red-black trees add a color bit to each node and enforce invariants (root is black, no two reds in a row, every path has the same number of black nodes). When inserts or deletes break an invariant, a handful of rotations and recolors repair it. The result is an ordered map/set that stays balanced even with adversarial input, which is why languages like C++, Java, Swift, and Rust use them for their core associative containers.

Time Complexity

AccessO(log n)

SearchO(log n)

InsertionO(log n)

DeletionO(log n)

Implementation Example

class RBNode {
  constructor(value, color = 'red') {
    this.value = value;
    this.color = color;
    this.left = null;
    this.right = null;
    this.parent = null;
  }
}

class RedBlackTree {
  constructor() {
    this.root = null;
  }

  rotateLeft(node) {
    const pivot = node.right;
    node.right = pivot.left;
    if (pivot.left) pivot.left.parent = node;
    pivot.parent = node.parent;
    if (!node.parent) {
      this.root = pivot;
    } else if (node === node.parent.left) {
      node.parent.left = pivot;
    } else {
      node.parent.right = pivot;
    }
    pivot.left = node;
    node.parent = pivot;
  }

  rotateRight(node) {
    const pivot = node.left;
    node.left = pivot.right;
    if (pivot.right) pivot.right.parent = node;
    pivot.parent = node.parent;
    if (!node.parent) {
      this.root = pivot;
    } else if (node === node.parent.right) {
      node.parent.right = pivot;
    } else {
      node.parent.left = pivot;
    }
    pivot.right = node;
    node.parent = pivot;
  }

  insert(value) {
    const newNode = new RBNode(value);
    if (!this.root) {
      newNode.color = 'black';
      this.root = newNode;
      return;
    }
    let parent = this.root;
    while (true) {
      if (value < parent.value) {
        if (!parent.left) {
          parent.left = newNode;
          break;
        }
        parent = parent.left;
      } else {
        if (!parent.right) {
          parent.right = newNode;
          break;
        }
        parent = parent.right;
      }
    }
    newNode.parent = parent;
    this.fixInsert(newNode);
  }

  fixInsert(node) {
    while (node.parent && node.parent.color === 'red') {
      const grand = node.parent.parent;
      if (node.parent === grand.left) {
        const uncle = grand.right;
        if (uncle && uncle.color === 'red') {
          node.parent.color = 'black';
          uncle.color = 'black';
          grand.color = 'red';
          node = grand;
        } else {
          if (node === node.parent.right) {
            node = node.parent;
            this.rotateLeft(node);
          }
          node.parent.color = 'black';
          grand.color = 'red';
          this.rotateRight(grand);
        }
      } else {
        const uncle = grand.left;
        if (uncle && uncle.color === 'red') {
          node.parent.color = 'black';
          uncle.color = 'black';
          grand.color = 'red';
          node = grand;
        } else {
          if (node === node.parent.left) {
            node = node.parent;
            this.rotateRight(node);
          }
          node.parent.color = 'black';
          grand.color = 'red';
          this.rotateLeft(grand);
        }
      }
    }
    this.root.color = 'black';
  }
}

Red-Black Trees

Red-Black Trees Deep Dive

Red-black trees are binary search trees with a color bit and simple invariants that keep the tree “balanced enough” without expensive rebuilds.

?But why does this matter?

Localized rotations and recolors run only when needed, so inserts and deletes stay O(log n) even if inputs arrive in sorted or adversarial order.

Visual Flow

How it actually moves

Lookup

O(log n)

Binary search tree traversal obeys in-order property.

Insertion

O(log n)

Insert like a BST, then repair invariants via recolor/rotation.

Deletion

O(log n)

Replace node, propagate double-black fixes until tree stabilizes.

Watch the best explainer

Red-Black Trees in 4 Minutes — Intro

Michael Sambol

The most popular quick visual intro to red-black rules and rotations.

City zoning that enforces alternating districts

Picture urban planners who paint districts red or black and demand that every route from city hall to a neighborhood alternates colors and passes the same number of black districts. When construction breaks the rules, they repaint or reroute a couple streets to keep commute times predictable.

Real-world analogy

Storage engines keep fresh writes in an in-memory red-black tree (memtable). Even when one tenant hammers a key range, lookups for everyone else remain fast because the tree height never blows up.

Takeaway

Instead of perfection, red-black trees promise “never too tall,” giving you predictable latency with minimal balancing overhead.

Practical applications

• Ordered maps/sets in standard libraries (C++ std::map, Java TreeMap, Swift OrderedDictionary).
• Kernel schedulers (Linux CFS) and memory managers that sort entities by priority or address.
• Compilers and IDEs that manage symbol tables for million-line codebases.

Technical insights

• The rules “root is black”, “no two reds in a row”, and “equal black height on every path” bound the tree height to ≤ 2*log2(n).
• Recoloring handles most violations; rotations only run when the structure needs to pivot.
• Deletion fix-ups treat “double black” nodes as debt that gets paid as you bubble toward the root.

When to reach for it

• Ordered key/value storage that must stay fast even with adversarial patterns.
• Systems that need range queries in addition to point lookups.
• Schedulers or caches where periodic “rebalance everything” pauses are unacceptable.

Operations Breakdown

Lookup

O(log n)

Binary search tree traversal obeys in-order property.

Insertion

O(log n)

Insert like a BST, then repair invariants via recolor/rotation.

Deletion

O(log n)

Replace node, propagate double-black fixes until tree stabilizes.

Best practices

• Augment nodes with subtree size or aggregates (sum, min) to support order-statistic queries without reworking balancing logic.
• Use pool allocators when the tree churns heavily to reduce fragmentation and GC pressure.
• Expose debugging traversals (color, black-height) so automated tests can assert invariants.

Common pitfalls

• Skipping recolor steps before rotating can silently break invariants until production traffic reveals it.
• Recursive deletion fix-ups risk stack overflows on untrusted depth; keep algorithms iterative.
• Iterators become invalid after structural edits; guard with locks or copy-on-write snapshots.

Every kind of Red-Black Trees

Interviewers rarely say which flavor they mean — they expect you to recognize it from the problem. Each variant below comes with the algorithms it unlocks.

Type 1 of 4

Red-Black Tree

→ full page

The production-default balanced BST: five color rules guarantee the longest path is at most twice the shortest, so height stays O(log n).

What to know

Rules: nodes are red or black; root black; no red-red parent-child; equal black-height on every path.
Insert fixes violations with recolors and at most two rotations.
Delete is the hard case — "double black" resolution has four sub-cases.

Algorithms to reach for

Insert fix-up

O(log n)

Restore color rules after insertion

Delete fix-up

O(log n)

Restore black-height after removal

In the wild: Java TreeMap, C++ std::map/set, Linux CFS run-queue, nginx timers.

Practice problems — hints, approach & solution on their own pages

My Calendar I (ordered-map thinking)Medium Contains Duplicate III (ordered-set window)Hard

Type 2 of 4

AVL Tree

→ full page

The strictest balancer: sibling heights differ by at most 1. Reads are fastest of any BST; writes pay for it with more rotations.

What to know

Balance factor ∈ {−1, 0, 1} stored per node; violations trigger LL/RR/LR/RL rotations.
Height ≤ 1.44 log n — measurably shorter than red-black’s 2 log n bound.
Choose AVL for read-heavy workloads, red-black for mixed ones.

Algorithms to reach for

Rotation rebalancing

O(log n)

Restore balance factor after each write

Height-tracked search

O(log n)

Fastest guaranteed BST lookups

In the wild: Read-heavy in-memory indexes, language runtimes, early filesystem trees.

Practice problems — hints, approach & solution on their own pages

Balance a Binary Search TreeMedium

Type 3 of 4

Splay Tree

→ full page

No stored balance data at all: every access rotates the touched node to the root, so hot items become cheap automatically.

What to know

Zig, zig-zig, zig-zag rotation patterns move accessed nodes up.
Amortized O(log n) even though a single operation can be O(n).
Naturally cache-like: recently used keys sit near the root.

Algorithms to reach for

Splaying

O(log n) amortized

Self-optimizing access; hot keys float to top

Split / join

O(log n) amortized

Cut and merge ordered sets by splaying a boundary

In the wild: Caches with skewed access, rope data structures in editors, network flow libraries.

Type 4 of 4

Treap (Tree + Heap)

→ full page

Each node gets a random priority; BST order by key, heap order by priority. Randomness does the balancing with no case analysis.

What to know

Equivalent to a BST built by inserting keys in random order — expected height O(log n).
split(key) and merge(a, b) make ordered-set union/insertion elegant.
Far simpler to code correctly under pressure than red-black deletion.

Algorithms to reach for

Split / merge

O(log n) expected

Compose all ordered-set ops from two primitives

Implicit treap

O(log n) expected

Array with O(log n) insert/delete/reverse anywhere

In the wild: Competitive programming workhorse, versioned buffers, randomized indexes.

Signature algorithms

Algorithm

Insertion fix-up

After inserting a red node, walk upward repairing red-on-red violations by recoloring and rotating around the grandparent.

Time

O(log n)

Space

O(1)

function fixInsert(tree, node) {
  while (node.parent && node.parent.color === 'red') {
    const grand = node.parent.parent;
    if (node.parent === grand.left) {
      const uncle = grand.right;
      if (uncle && uncle.color === 'red') {
        node.parent.color = 'black';
        uncle.color = 'black';
        grand.color = 'red';
        node = grand;
      } else {
        if (node === node.parent.right) {
          node = node.parent;
          tree.rotateLeft(node);
        }
        node.parent.color = 'black';
        grand.color = 'red';
        tree.rotateRight(grand);
      }
    } else {
      const uncle = grand.left;
      if (uncle && uncle.color === 'red') {
        node.parent.color = 'black';
        uncle.color = 'black';
        grand.color = 'red';
        node = grand;
      } else {
        if (node === node.parent.left) {
          node = node.parent;
          tree.rotateRight(node);
        }
        node.parent.color = 'black';
        grand.color = 'red';
        tree.rotateLeft(grand);
      }
    }
  }
  tree.root.color = 'black';
}