---
title: "Red-Black Tree"
description: "Balance kept by recoloring and rotation — the tree behind most standard libraries."
source: https://vizlearn.app/algorithms/data-structures/red-black-tree
access: premium (interactive player requires Lifetime; this doc is free)
---

# Red-Black Tree

A red-black tree is a binary search tree with one extra bit of state per node: red or black. The color does not sort the keys. It limits how uneven the tree can become, so insertion and search stay O(log n) even when keys arrive in sorted order.

Think of every route from the root as carrying a black-node budget. New nodes start red because red spends none of that budget. If a new red node gets a red parent, the uncle's color decides the repair. The tree does not rotate merely because it looks crooked.

This lesson covers insertion and search. Deletion has a separate double-black repair procedure and is deliberately out of scope.

## How Red-Black Tree Invariants Work

Every valid red-black tree obeys five rules:

1. Every node is red or black.
2. The root is black.
3. Every missing child, called a **NIL leaf**, is black.
4. A red node cannot have a red child.
5. Every path from a node down to a NIL leaf contains the same number of black nodes.

The visualizer calls the final count **black-height**, or BH. Its workbench counts black nodes strictly below the current node and includes the terminal NIL leaf. Textbooks differ on whether the starting node belongs in the count; the repair logic only requires one convention used consistently.

Rule 4 stops long runs of red nodes. Rule 5 makes the black skeleton equally deep on every route. Together, they imply that the longest root-to-leaf path is at most twice the shortest. A tree with `n` internal nodes has height at most `2 log2(n + 1)`.

The **Sorted stress** scenario makes that bound visible. It inserts `10, 20, 30, 40, 50, 60, 70`. The red-black tree finishes at edge-height 3; an ordinary BST given the same keys becomes a height-6 vine. Searching for 70 takes four probes in the repaired tree instead of seven in the plain BST.

## How Red-Black Tree Insertion Repair Works

Insertion begins as ordinary BST insertion. Smaller keys go left, larger keys go right, and a duplicate leaves the tree unchanged. The new leaf is red.

Why red? A black leaf would add one black node to only the route where it was inserted. Equal black-height could fail immediately. A red leaf adds zero to every black count, though it may create a red-red edge with its parent. The first root is the exception: there is no existing route to unbalance, and its two NIL children give it black-height 1 in either color. It still enters red through the same code path, then the root rule changes it to black.

If the parent is black, there is no red-red edge and repair stops. If the parent is red, inspect the uncle:

- **Red uncle:** color the parent and uncle black, color the grandparent red, then move the repair cursor up to the grandparent.
- **Black uncle, including NIL:** classify the local path as a line or triangle, recolor the middle node and grandparent, then rotate.

The red-uncle case is safe because its black-height ledger balances exactly. Before recoloring, a route through the local family counts the black grandparent once and the red child zero times. After recoloring, it counts the red grandparent zero times and the now-black parent or uncle once. The subtotal remains one on both sides. No pointer has to move; only a possible red-red conflict has moved upward.

There are four black-uncle shapes:

| Case | Local path        | Repair                                                                      |
| ---- | ----------------- | --------------------------------------------------------------------------- |
| LL   | left, then left   | recolor, rotate right at the grandparent                                    |
| RR   | right, then right | recolor, rotate left at the grandparent                                     |
| LR   | left, then right  | rotate left at the parent, then recolor and rotate right at the grandparent |
| RL   | right, then left  | rotate right at the parent, then recolor and rotate left at the grandparent |

LL and RR are outer **lines**, so one grandparent rotation finishes the structural repair. LR and RL are inner **triangles**. Their first rotation straightens the bend into a line; their second performs the same grandparent repair as LL or RR. That is why insertion needs at most two rotations. Recoloring may climb toward the root, but the pointer rewiring never does.

The triangle presets include a ghost counterexample. If the first parent rotation is skipped, the shortcut leaves the old grandparent and inserted node joined by a red-red edge. Black-height alone can still look plausible, which is exactly why one invariant cannot stand in for all five.

Rotations preserve the in-order key sequence. A middle transfer subtree, shown as `T2`, moves to the only slot where its keys still fit. After repair, the root is forced black.

## Red-Black Tree Step by Step

The default run performs `insert 10, insert 20, insert 30, insert 15, insert 12, search 15`.

1. **Insert 10.** The root slot is NIL, so 10 attaches as red. It has no parent, so no red-red edge is possible; its NIL children give black-height 1. The root rule then changes it to black.

2. **Insert 20.** The search walks right from 10. Node 20 attaches red, and parent 10 is black, so no uncle check or rotation is needed.

3. **Insert 30.** The path goes right from 10 and right from 20. Nodes 30 and 20 are both red. The uncle is NIL, which counts as black, and the shape is an RR line. Color 20 black, color 10 red, then rotate left at 10. Node 20 becomes the black root with red children 10 and 30.

4. **Insert 15.** The path is 20, left to 10, then right. Node 15 attaches below red parent 10. The uncle is 30, also red. Color 10 and 30 black, color grandparent 20 red, and move the repair cursor to 20. Because 20 is the root, the final root assignment changes it back to black. No pointer moves.

5. **Insert 12.** The path is 20, 10, 15, then left. Parent 15 is red and the uncle is NIL black. Relative to grandparent 10, the path bends right then left: RL. First rotate right at 15 to straighten the triangle. Then color 12 black, color 10 red, and rotate left at 10.

   The final tree has black root 20. Its left child is black 12 with red children 10 and 15; its right child is black 30. Every red node has black children, and every route from the root to NIL has the same black-height.

6. **Search 15.** Compare with 20 and go left. Compare with 12 and go right. The third probe matches 15. Repair changed the shape, but BST order still guides the search.

The workbench uses `z` for the repair cursor, `p` for parent, `u` for uncle, and `g` for grandparent. Node fills always mean persistent red-black state. Rings and role tags show the current action, so a red node never doubles as an error marker.

## When to Use a Red-Black Tree

Red-black trees sit behind real ordered indexes. Java's [`TreeMap`](https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/TreeMap.html) explicitly documents a red-black-tree implementation. GNU libstdc++ builds its `map`, `set`, `multimap`, and `multiset` family on an internal [`_Rb_tree`](https://gcc.gnu.org/onlinedocs/gcc-12.3.0/libstdc%2B%2B/api/a00413_source.html); the C++ standard guarantees ordered logarithmic behavior, not that every implementation must use this structure. The Linux kernel's [rbtree API](https://docs.kernel.org/core-api/rbtree.html) supports ordered, performance-sensitive structures such as high-resolution timers.

Choose a red-black tree when you need sorted iteration, predecessor or successor queries, range scans, and frequent updates with worst-case O(log n) bounds. If you only need exact-key lookup, a hash table is usually simpler and faster. If the index lives on disk or must exploit cache lines aggressively, a wide B-tree family is usually a better fit.

The closest alternative is an AVL tree. AVL keeps a stricter height bound and often gives shorter lookup paths, which suits read-heavy in-memory indexes. Red-black trees permit a little more height and perform at most two rotations per insertion; recoloring may climb, but structural changes stay local. AVL insertion also ends with one single or double rotation, so the decision is not a slogan about rotation count alone. Prefer AVL when lookup density matters most. Prefer red-black when ordered maps see frequent insertions and deletions and looser balance reduces structural churn.

## Time and Space Complexity

| Operation    | Time     | Extra space in this implementation   |
| ------------ | -------- | ------------------------------------ |
| Search       | O(log n) | O(1), iterative                      |
| Insert       | O(log n) | O(1), iterative with parent pointers |
| One rotation | O(1)     | O(1)                                 |

The BST walk follows one root-to-leaf path. A red-uncle repair may continue upward, but it follows that same path. A black-uncle repair uses at most two rotations and then finishes. The height bound keeps the total time complexity O(log n).

## Edge Cases

- **Empty tree:** search reaches NIL with zero node probes. The first inserted node is normalized to a black root.
- **Duplicate key:** insertion stops at the equal node. Shape, colors, node count, and shadow BST stay unchanged.
- **NIL uncle:** NIL is black, so repair takes the line-or-triangle branch.
- **Red root during repair:** red-uncle recoloring may temporarily turn the root red. The final root assignment restores the invariant.
- **Null transfer subtree:** rotation still works when `T2` is NIL; there is no internal child pointer to move.
- **Visualization limit:** the panel draws at most 13 nodes. Red-black trees have no fixed capacity; this cap protects label and edge readability.

## Common Mistakes

- **Treating NIL as "no color."** Repair depends on NIL being black. A missing uncle is a black uncle.
- **Inserting new leaves as black.** That can change black-height on only one branch. Red is the safe initial color.
- **Rotating whenever the tree looks tall.** Height is not the branch condition. Parent and uncle colors come first; only a black uncle leads to shape classification.
- **Using one rotation for LR or RL.** A triangle must become a line before the grandparent rotation.
- **Recoloring every relative at once.** The animation separates each write because intermediate states matter. Code should make the same assignments intentionally.
- **Dropping `T2` during rotation.** The middle subtree must move to the demoted pivot. Losing it drops keys; attaching it on the wrong side breaks BST order.
- **Checking only black-height.** A tree can have equal black-height and still contain a red-red edge. Validate root color, the red-parent rule, and black-height together.