Red-Black Trees

Red-Black trees power the ordered collections in every major language runtime. Java’s TreeMap, TreeSet, and even HashMap (for long bucket chains) rely on Red-Black trees internally. Understanding their properties and rebalancing logic gives you direct insight into the performance characteristics of code you write every day.

Unlike AVL trees, which enforce strict height balance, Red-Black trees use a color-based scheme that allows slightly more height imbalance in exchange for fewer rotations during insertion and deletion. This trade-off makes Red-Black trees the preferred self-balancing BST for general-purpose use.

The Five Red-Black Properties

A Red-Black tree is a BST where every node carries a color (red or black) and the tree satisfies these five invariants:

1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL / null) is black. (NIL nodes are implicit — they represent the null children of leaf nodes.)
4. If a node is red, both its children are black. (No two red nodes appear consecutively on any path.)
5. For each node, all paths from that node to its descendant NIL nodes contain the same number of black nodes. (This count is called the node’s black-height.)

These five rules look deceptively simple, but together they produce a powerful guarantee.

Why These Properties Guarantee O(log n)

Claim: A Red-Black tree with n internal nodes has height at most $2 \log_2(n + 1)$.

Proof sketch: Property 5 ensures every root-to-leaf path has the same black-height, call it $b$. Property 4 ensures no path has two consecutive red nodes, so red nodes can appear on at most every other position. The longest possible path alternates red and black: $2b$ nodes. The shortest possible path is all black: $b$ nodes. The subtree rooted at any node contains at least $2^b - 1$ internal nodes (by induction using Property 5). Combining: height $h \leq 2b$ and $n \geq 2^b - 1$, giving $b \leq \log_2(n+1)$ and $h \leq 2\log_2(n+1)$.

The practical impact: Red-Black trees are at most twice the height of a perfect binary tree, guaranteeing O(log n) search, insert, and delete.

Node Structure

sealed interface Color permits Color.Red, Color.Black {
    record Red() implements Color {}
    record Black() implements Color {}
}

class RBNode {
    int val;
    Color color;
    RBNode left;
    RBNode right;
    RBNode parent;

    RBNode(int val) {
        this.val = val;
        this.color = new Color.Red(); // new nodes are always red
        this.left = null;
        this.right = null;
        this.parent = null;
    }
}

Java 25’s sealed interfaces model the color constraint at the type level — a node’s color is either Red or Black, with no other possibilities. The parent pointer enables bottom-up traversal during fixup, which is essential for the uncle-based case analysis.

Why insert as red? Inserting a red node preserves Property 5 (black-height unchanged along every path). It risks violating Property 4 (consecutive reds), which is easier to fix through local rotations and recoloring than a black-height violation would be.

Insertion

Red-Black insertion proceeds in two phases:

Phase 1: Standard BST Insert

Insert the new node as a red leaf using standard BST logic:

void insert(int val) {
    RBNode newNode = new RBNode(val);

    // Standard BST insertion
    RBNode parent = null;
    RBNode current = root;

    while (current != null) {
        parent = current;
        if (val < current.val) {
            current = current.left;
        } else if (val > current.val) {
            current = current.right;
        } else {
            return; // duplicate, skip
        }
    }

    newNode.parent = parent;
    if (parent == null) {
        root = newNode;
    } else if (val < parent.val) {
        parent.left = newNode;
    } else {
        parent.right = newNode;
    }

    // Phase 2: Fix violations
    insertFixup(newNode);
}

Phase 2: Insertion Fixup

After inserting a red node, the only property that can be violated is Property 4 (no consecutive reds). The fixup examines the newly inserted node’s uncle (the sibling of its parent) to determine the correction strategy.

Three cases arise, each with a mirror variant (parent is left child vs right child of grandparent):

Case 1: Uncle is Red

Both parent and uncle are red. Recolor parent and uncle to black, grandparent to red. Move the “problem” up to the grandparent and repeat.

Before:                After recoloring:
      G(B)                  G(R)  ← may violate with G's parent
     / \                   / \
   P(R)  U(R)            P(B)  U(B)
   /                     /
 N(R)                  N(R)

No rotation needed. The recoloring preserves Property 5 (same black-height on all paths) while fixing the red-red violation between N and P. The grandparent turning red propagates the potential violation upward.

Case 2: Uncle is Black, Node is Inner Child

The node is the right child of a left parent (or left child of a right parent) — an “inner” position. Rotate the node and parent to transform this into Case 3.

Before:                After left rotation on P:
      G(B)                  G(B)
     / \                   / \
   P(R)  U(B)            N(R)  U(B)
     \                   /
     N(R)              P(R)

This rotation does not fix the violation — it repositions the nodes so that Case 3 applies.

Case 3: Uncle is Black, Node is Outer Child

The node is the left child of a left parent (or right child of a right parent) — an “outer” position. Rotate the grandparent and recolor.

Before:                After right rotation on G + recolor:
      G(B)                  P(B)
     / \                   / \
   P(R)  U(B)            N(R)  G(R)
   /                            \
 N(R)                           U(B)

Parent becomes black (new subtree root), grandparent becomes red. The rotation preserves Property 5 and eliminates the red-red violation.

Complete Fixup Code

void insertFixup(RBNode node) {
    while (node != root && isRed(node.parent)) {
        RBNode parent = node.parent;
        RBNode grandparent = parent.parent;

        if (parent == grandparent.left) {
            RBNode uncle = grandparent.right;

            if (isRed(uncle)) {
                // Case 1: Uncle is red — recolor
                parent.color = new Color.Black();
                uncle.color = new Color.Black();
                grandparent.color = new Color.Red();
                node = grandparent; // move up
            } else {
                if (node == parent.right) {
                    // Case 2: Uncle black, inner child — rotate to Case 3
                    node = parent;
                    rotateLeft(node);
                    parent = node.parent;
                    grandparent = parent.parent;
                }
                // Case 3: Uncle black, outer child — rotate + recolor
                parent.color = new Color.Black();
                grandparent.color = new Color.Red();
                rotateRight(grandparent);
            }
        } else {
            // Mirror: parent is right child of grandparent
            RBNode uncle = grandparent.left;

            if (isRed(uncle)) {
                parent.color = new Color.Black();
                uncle.color = new Color.Black();
                grandparent.color = new Color.Red();
                node = grandparent;
            } else {
                if (node == parent.left) {
                    node = parent;
                    rotateRight(node);
                    parent = node.parent;
                    grandparent = parent.parent;
                }
                parent.color = new Color.Black();
                grandparent.color = new Color.Red();
                rotateLeft(grandparent);
            }
        }
    }
    root.color = new Color.Black(); // Property 2: root is always black
}

boolean isRed(RBNode node) {
    return node != null && node.color instanceof Color.Red;
}

Termination: Case 1 moves the node up by two levels, so the loop runs at most O(log n) times. Cases 2 and 3 perform at most two rotations and terminate. The total insertion cost is O(log n) with at most two rotations.

Rotation Helpers

void rotateLeft(RBNode x) {
    RBNode y = x.right;
    x.right = y.left;

    if (y.left != null) y.left.parent = x;
    y.parent = x.parent;

    if (x.parent == null) {
        root = y;
    } else if (x == x.parent.left) {
        x.parent.left = y;
    } else {
        x.parent.right = y;
    }

    y.left = x;
    x.parent = y;
}

void rotateRight(RBNode x) {
    RBNode y = x.left;
    x.left = y.right;

    if (y.right != null) y.right.parent = x;
    y.parent = x.parent;

    if (x.parent == null) {
        root = y;
    } else if (x == x.parent.right) {
        x.parent.right = y;
    } else {
        x.parent.left = y;
    }

    y.right = x;
    x.parent = y;
}

These are identical to AVL rotations with the addition of parent pointer maintenance.

Where Red-Black Trees Live in Java

TreeMap and TreeSet

TreeMap<K, V> is Java’s ordered map implementation, backed entirely by a Red-Black tree. Every put, get, remove, firstKey, lastKey, floorKey, ceilingKey, subMap, and headMap operation runs in O(log n):

TreeMap<String, Integer> scores = new TreeMap<>();
scores.put("Alice", 95);
scores.put("Bob", 87);
scores.put("Charlie", 92);

// O(log n) ordered operations
String first = scores.firstKey();           // "Alice"
String floor = scores.floorKey("Carl");     // "Charlie" (wait - "Bob"!)
// floorKey returns the greatest key ≤ given key
// "Bob" < "Carl" < "Charlie", so floor is "Bob"

// Range view: O(log n) to create, O(k) to iterate k elements
SortedMap<String, Integer> sub = scores.subMap("Alice", "Charlie");

TreeSet<E> wraps a TreeMap where the values are a dummy constant. All set operations inherit O(log n) performance.

HashMap Treeification

Since Java 8, HashMap converts long bucket chains from linked lists to Red-Black trees. When a single bucket accumulates more than 8 entries (the TREEIFY_THRESHOLD), the chain restructures into a Red-Black tree, improving worst-case lookup from O(n) to O(log n):

// Bucket chain: [Entry1 → Entry2 → ... → Entry9]
// After treeification: Red-Black tree of 9 entries
// Lookup improves from O(9) to O(log 9) ≈ O(3.2)

This protects against hash collision attacks where an adversary crafts keys that all map to the same bucket. Without treeification, such attacks degrade HashMap to O(n) per operation.

The reverse happens when a bucket shrinks below 6 entries (UNTREEIFY_THRESHOLD): the tree converts back to a linked list to save overhead.

ConcurrentSkipListMap vs TreeMap

For concurrent ordered maps, Java provides ConcurrentSkipListMap instead of a concurrent Red-Black tree. Skip lists achieve O(log n) expected time through randomized layering rather than tree rotations, and they support lock-free concurrent access:

ConcurrentSkipListMap<String, Integer> concurrentMap = new ConcurrentSkipListMap<>();
// Thread-safe, O(log n) ordered operations
// No global lock — uses CAS for lock-free updates

Why not a concurrent Red-Black tree? Tree rotations require restructuring multiple nodes atomically, which conflicts with fine-grained locking. Skip lists avoid this problem because insertions affect only local pointers.

Deletion Overview

Red-Black tree deletion is notoriously complex — six cases for the fixup, each with a mirror variant, totaling twelve code branches. The high-level process:

1. Perform standard BST deletion. If the deleted node or its replacement is red, recolor to black and finish.
2. If a “double-black” situation arises (a black node is removed, creating a black-height deficit), enter the deletion fixup.
3. The fixup examines the sibling’s color and its children’s colors to determine rotations and recolorings.

The six fixup cases:

• Case 1: Sibling is red → rotate to create a black sibling, then fall into Case 2–4.
• Case 2: Sibling is black with two black children → recolor sibling red, propagate up.
• Case 3: Sibling is black, sibling’s far child is black, near child is red → rotate sibling to transform into Case 4.
• Case 4: Sibling is black, sibling’s far child is red → rotate parent, recolor, done.

Interviewers almost never ask you to implement Red-Black deletion. If they ask about it, describe the case structure and state that the operation performs at most three rotations and O(log n) recolorings.

Comparison: AVL vs Red-Black vs B-Tree

Property	AVL Tree	Red-Black Tree	B-Tree
Balance guarantee	|balance| ≤ 1	Longest ≤ 2× shortest	All leaves at same depth
Max height	1.44 log₂ n	2 log₂(n+1)	log_t(n) for branching factor t
Lookup	Fastest (shortest)	Fast	Fewer disk reads (wide nodes)
Insert rotations	≤ 2	≤ 2	Split/merge
Delete rotations	O(log n)	≤ 3	Split/merge
Best for	Read-heavy in-memory	General in-memory	Disk-based storage
Used in	Custom read-heavy structures	Java TreeMap, C++ std::map	Databases, filesystems

B-Trees extend the self-balancing concept to M-way trees optimized for disk I/O. Each node holds up to M−1 keys and M children, reducing tree height to $\log_M(n)$. Database indexes (MySQL InnoDB, PostgreSQL) use B+ Trees (a variant where all data lives in leaves) because they minimize disk seeks.

Worked Example: Building a Red-Black Tree

Insert values 10, 20, 30, 15, 25 into an empty Red-Black tree:

Insert 10: Tree is empty. 10 becomes root, colored black (Property 2).

10(B)

Insert 20: 20 > 10, goes right. Colored red. Parent 10 is black → no violation.

10(B)
  \
  20(R)

Insert 30: 30 > 20, goes right of 20. Red-red violation: 20(R) and 30(R). Uncle of 30 is null (black). 30 is outer child (right-right). → Case 3: left rotate 10, recolor.

  20(B)
 / \
10(R) 30(R)

Insert 15: 15 > 10, goes right of 10. Red-red violation: 10(R) and 15(R). Uncle of 15 is 30(R). → Case 1: recolor parent (10→B), uncle (30→B), grandparent (20→R). But 20 is root → recolor back to black (Property 2).

  20(B)
 / \
10(B) 30(B)
  \
  15(R)

Insert 25: 25 < 30, goes left of 30. Red-red violation: 30(B)… wait, 30 is black. No violation. 25 is red, parent 30 is black → valid.

  20(B)
 / \
10(B) 30(B)
  \   /
 15(R) 25(R)

All five properties hold. The tree has height 2, which is O(log 5) ≈ 2.3. Optimal.

Interviewer Tips

Red-Black trees come up in interviews at two levels:

Conceptual level (common): “Explain the Red-Black tree properties.” “Why does HashMap use Red-Black trees?” “Compare AVL vs Red-Black.” Prepare clear, confident answers for these. The five properties, the O(log n) height proof sketch, and the HashMap treeification story are the high-value talking points.

Implementation level (rare): Full Red-Black tree implementation is too complex for a standard interview. If an interviewer goes here, they test your ability to reason about cases and handle complexity systematically. Focus on the insertion fixup — three cases plus mirror — and walk through a concrete example.

The winning strategy: State the five properties from memory. Explain that insertion always adds a red node (preserving black-height) and fixes red-red violations by examining the uncle’s color. Mention that Java’s TreeMap uses this structure, giving O(log n) for all ordered operations. That level of understanding satisfies 95% of interview questions about Red-Black trees.