TreeMap and red-black trees

Think of a TreeMap as a well-organized library shelf. A HashMap is a storage room with labeled bins: great when you know the exact label. A TreeMap keeps every book in order, so you can ask for the book just before or just after the one you named.

For this lesson, we'll focus on TreeMap internals: red-black tree rules, Entry{key,value,left,right,parent,color}, insertion followed by fixAfterInsertion, rotations and recoloring at intuition level, Comparable versus Comparator, null-key behavior, NavigableMap APIs, and the practical TreeMap versus HashMap versus LinkedHashMap decision. Range-query patterns get their own lesson, so we'll link to Range queries with TreeMap instead of repeating that full playbook here.

01Picture it first: a self-correcting family tree

A binary search tree keeps smaller keys on the left and larger keys on the right. That alone is not enough, because inserting sorted keys into a plain BST creates a linked list and turns lookup into O(n). A red-black tree adds one bit of color per node and a few repair rules so the tree never gets too tall.

The diagram shows the local move you should recognize. A rotation changes parent-child links while preserving sorted order.

Fig. 1

A small red-black tree before and after a left rotation, with orange red nodes and ink black nodes, showing that sorted order is preserved while the heavy right side is lifted

The important idea is not memorizing every case. Rotations preserve order; recoloring preserves the black-height rules. TreeMap combines those two moves after insertions and removals.

02Red-black trees under the hood

A TreeMap entry is a node in a binary search tree. The OpenJDK class is called Entry, and conceptually it looks like this:

static final class Entry<K, V> implements Map.Entry<K, V> {
    K key;
    V value;
    Entry<K, V> left;
    Entry<K, V> right;
    Entry<K, V> parent;
    boolean color; // RED or BLACK
}

Every search compares the requested key with the current node's key. Smaller goes left, larger goes right, equal means this is the entry. The only question is how the tree avoids becoming a long chain.

These are the five red-black rules interviewers expect:

1. Every node is either red or black.
2. The root is black.
3. Every missing child, often drawn as a NIL leaf, is black.
4. A red node cannot have a red parent or red child.
5. Every path from a node to its descendant NIL leaves has the same number of black nodes.

Those rules imply a useful bound: a red-black tree with n real nodes has height at most 2 * log2(n + 1). For 1,000,000 entries, log2(1,000,001) is about 20, so the height is at most about 40. That is why operations are O(log n), even though the tree is not perfectly balanced.

03Put: BST insert, then fix the colors

Insertion starts exactly like a normal binary search tree insert. Walk down using compare, attach the new node where the missing child was, and color the new node red. Red is the optimistic choice: it does not change the black count on any root-to-leaf path.

TreeMap<Integer, String> prices = new TreeMap<>();
prices.put(10, "low");
prices.put(20, "mid");
prices.put(30, "high");

System.out.println(prices.keySet()); // [10, 20, 30]

A plain BST would be 10 -> 20 -> 30, a right-leaning chain. A red-black tree repairs that local shape. After inserting 30, the new red node has a red parent (20), which violates rule 4. Since the uncle is black or missing, fixAfterInsertion rotates left around 10 and recolors 20 black and 10 red.

At intuition level, fixAfterInsertion repeats this loop:

1. If the new node is the root, make it black and stop.
2. If the parent is black, all rules are fine and stop.
3. If the parent and uncle are red, recolor parent and uncle black, grandparent red, then continue from grandparent.
4. If the parent is red and the uncle is black, rotate to straighten a zig-zag if needed, then rotate around the grandparent and recolor.

// Not JDK code, just the shape of the algorithm.
while (node != root && colorOf(parentOf(node)) == RED) {
    if (parentOf(node) == leftOf(parentOf(parentOf(node)))) {
        Entry<K, V> uncle = rightOf(parentOf(parentOf(node)));
        if (colorOf(uncle) == RED) {
            setColor(parentOf(node), BLACK);
            setColor(uncle, BLACK);
            setColor(parentOf(parentOf(node)), RED);
            node = parentOf(parentOf(node));
        } else {
            // rotate and recolor, mirrored for the other side
        }
    }
}
root.color = BLACK;