You insert a million sequential order IDs into a sorted map. Yesterday’s horror story was a plain binary search tree: already-sorted keys became a linked list, and contains walked a million nodes. You use TreeMap instead. The millionth put is still cheap. The keys are still sorted. Nobody rotated the tree by hand.
A red-black tree is a BST with a color on every node and a handful of paint rules that keep the longest path from growing more than about twice the shortest. That is enough to bound height by O(log n) even when the keys arrive in order. It is stricter than “hope the inserts shuffle,” and looser than AVL’s “child heights differ by at most one.” Java’s TreeMap and TreeSet are this shape.
Height, worst-case vs amortized, and how to read a complexity table live on the Data Structures Roadmap. This post stays on the paint: the rules, why they cap height, the rotate-and-recolor idea, and the JDK types that already do the work.
The BST is still the walk
Search, insert, and inorder do not change. Left subtree smaller, right subtree larger. You still walk one path from the root. A node just carries a color besides the two child pointers:
enum Color { RED, BLACK }
final class Node {
int key;
Color color;
Node left;
Node right;
Node parent;
Node(int key, Color color) {
this.key = key;
this.color = color;
}
}Missing children are treated as black sentinels (NIL). OpenJDK TreeMap uses null and pretends null is black. Same rule, fewer objects. The parent pointer is how fixup walks back up after a BST insert; it is not part of the ordering law.
Note: Color is one bit of extra state, not a second key. Recoloring a node does not move it. Rotations move nodes. The BST invariant must survive both.
Five rules, two that do the work
Textbooks list five properties. Remember the last two; the others exist so those two are well-defined.
1. Every node is red or black.
2. The root is black.
3. Every NIL leaf is black.
4. No two reds in a row: a red node has two black children.
5. Black-height: every path from a node down to a NIL
contains the same number of black nodes.No two reds in a row stops a path from packing arbitrary extra nodes without adding blacks. Equal black-height stops one side from accumulating blacks while the other stays skinny. Together they say: you may be a little lopsided, but you may not be a spine.
A legal sketch (B = black, R = red). Every root-to-NIL path has two blacks. No red parent has a red child:
8B
/ \
4R 12B
/ \ \
2B 6B 14RPaint 4 red and 2 red at the same time and rule 4 breaks. Hang a long all-red chain off 14 and both 4 and 5 break. The tree would still be a BST. It would not be red-black.
Why the paint bounds height
Call the black-height of the root b: the number of black nodes on any path down to a NIL, not counting the NIL itself.
Because every path has the same b, the shortest possible path is all black — length b. Because no two reds sit in a row, you cannot put more reds on a path than blacks. The longest path is therefore at most about 2b (black, red, black, red, …).
Ignore the reds for a moment and the blacks still form a tree of height b. A binary tree of height b holds at least 2^b - 1 internal nodes when it is as full as those blacks allow. So for n keys:
n ≥ 2^b - 1
b ≤ log2(n + 1)
height h ≤ 2b ≤ 2 log2(n + 1)That is the slogan people wanted from a plain BST and did not get: height is O(log n) on every input order, including sorted IDs and timestamps. You paid a color bit and some local surgery on insert and delete. You did not pay a full rebuild.
AVL asks for a tighter shape (balance factor −1, 0, or +1 at every node). Lookups can be a comparison or two shorter. Inserts and deletes rotate more often. Maps mutate. That is why TreeMap picked the looser paint.
Insert red, then fix locally
Insert is a BST insert. The new node is painted red. Red does not change any black-height, so rule 5 is still true. The only new crime is a red child under a red parent.
If the parent is black, you are done. If the parent is red, you have a red-red pair. Fixup is a handful of local cases, not a walk of the whole tree:
| After the red insert | Typical fix |
|---|---|
| Parent black | Stop |
| Parent red, uncle red | Recolor parent and uncle black, grandparent red; repeat upward |
| Parent red, uncle black | Rotate into a straight line, rotate around the grandparent, swap colors |
Uncle is the parent’s sibling. Recolor pushes the “extra redness” toward the root. Rotation rearranges three nodes so the BST order stays true and the red-red pair disappears. Either way you touch O(1) nodes per step and at most O(log n) steps — the same height you just proved is logarithmic.
A right rotation around y (left rotation is the mirror). Keys in inorder are still A, x, B, y, C:
y x
/ \ / \
x C → A y
/ \ / \
A B B CYou do not need the six-case chart memorized to use the structure. You need to know that fixup is local: a recolor, or one or two rotations, then maybe the same question one level up. Delete is the same idea with a “double black” deficit instead of an extra red — restore black-height, then stop. This post will not ship a complete insertFixup. Production Java already did.
TreeMap is the production tree
There is no java.util.RedBlackTree. There is TreeMap, documented as a red-black tree, and TreeSet, which is a TreeMap with dummy values. Sorted keys, guaranteed log-height mutates, range views:
NavigableMap<Integer, String> orders = new TreeMap<>();
orders.put(42, "paid");
orders.put(7, "pending");
orders.put(19, "packed");
System.out.println(orders.firstKey()); // 7
System.out.println(orders.higherKey(19)); // 42
System.out.println(orders.subMap(7, 42).keySet()); // [7, 19]Sequential IDs do not degenerate. The millionth insert still walks O(log n) nodes and maybe recolors or rotates on the way back up:
NavigableMap<Integer, String> ids = new TreeMap<>();
for (int i = 1; i <= 1_000_000; i++) {
ids.put(i, "row-" + i);
}
System.out.println(ids.get(1_000_000)); // still a short path, not a millionReach for TreeMap when the hot path needs ordered keys plus log-height updates: a live leaderboard, “next timestamp after this one,” a range of session IDs. Pass a Comparator when natural order is the wrong order. Iteration is in-order by key — you read the layout; you do not sort a HashMap on every request.
Note: TreeMap is still a tree of objects (left, right, parent, color), not a contiguous array. It wins on order-plus-log-n. It loses a cache scan to HashMap and to a sorted ArrayList you binary-search after a single sort. Match the hot operation, as the roadmap asks. It is also not thread-safe; a concurrent sorted map is ConcurrentSkipListMap, a different layout.
When not to use a red-black tree
Skip this shape when:
- You do not need order. Lookup-only uniqueness is a hash table’s job.
HashMap/HashSetare the default. A tree’s comparisons, extra pointers, and rotations are a tax you are not spending. - You are teaching the BST invariant. A color bit and fixup obscure the walk. Learn left < node < right on an unbalanced tree first; then ask what happens under sorted input; then add paint. Rolling your own
Nodewith rotations is for that lesson or for a layout the JDK does not ship — not for a production sorted map in Java. nis tiny. A list and a linear scan will beat a tree of twenty objects. Log n is not a personality.- The data lives on disk. Databases use wide, page-sized nodes (B-trees), not binary nodes, because a disk round-trip is the expensive operation. Painting a BST does not fix that bill.
Use TreeMap / TreeSet when the sentence mentions order and the collection mutates. If the sentence is only “is this key here?”, you wanted a hash table. If the sentence is “I will sort once and probe,” a sorted array can be cheaper than a live tree.
How to read the bill
Same shopping-list reading as the roadmap: pick the structure for the operation on the hot path.
Structure: red-black tree (TreeMap / TreeSet)
search O(log n) — height is bounded, including sorted input
insert O(log n) — BST insert + O(log n) recolor / ≤ a few rotations
delete O(log n)
min / max O(log n) — leftmost / rightmost (TreeMap: firstKey / lastKey)
range O(log n + k) — walk to the bound, then k in-order keys
inorder O(n)
space O(n) — child pointers + parent + one color bitThe h that a plain BST left hanging is now Θ(log n). Worst-case, not expected, not amortized. That is the product you bought with the paint.
Cheat sheet
What: BST + red/black paint; height ≤ ~ 2 log2(n+1)
Rules: no two reds in a row; equal black-height on every path
Insert: hang a red node, then recolor and/or rotate upward
Rotation: local rearrange; inorder (BST order) unchanged
JDK: TreeMap / TreeSet — you do not implement this
Use: ordered keys, log-height mutates, range views
Skip: unordered lookup (HashMap); teaching a plain BSTDo:
- Name order as a requirement before you name a tree.
- Treat
TreeMapas the production red-black tree, not a type you reimplement. - Use range methods (
subMap,higherKey,firstKey) when that is the job.
Don’t:
- Use a tree when a hash table would do and you never iterate in key order.
- Quote O(log n) on a BST you never rebalance and call it the same thing as
TreeMap. - Memorize every uncle-red case before you can choose between
HashMapandTreeMap.
Wrap-up
A red-black tree keeps the BST walk and adds paint that makes height a promise. No two reds in a row, plus equal black-height, cap the longest path at about twice the shortest. Insert paints the new node red and fixes locally with recolors and rotations. You do not rebuild. You do not need AVL’s strict balance unless lookups dominate and you are implementing the tree yourself.
In Java the type is TreeMap (and TreeSet on top of it). Sorted keys, log-height updates, range views — including when the keys arrive already sorted. If you do not need order, you did not need this tree. If you need order and a height guarantee, you already had one.
For the glossary behind height, worst-case, and “what operation is hot,” stay on the Data Structures Roadmap.