Java TreeMap Visualization | Red-Black Tree, put, remove

The idea: a sorted map is a balanced search tree

A java.util.TreeMap keeps its keys in order. Inside, it is a red-black tree: a binary search tree where every node is an Entry object with six fields. Smaller keys go left, larger keys go right. The colours keep the tree balanced, so its height stays below 2·log₂(n + 1) and every get, put and remove takes O(log n) compares.

An Entry with the fields key 37, value v37, left pointing to Entry 35, right to Entry 40, parent to Entry 30 and color BLACK; next to it the red-black tree after Demo 1: root 50 black, 30 red with children 10 black and 37 black, 5, 20, 35 and 40 red leaves, 70 black, with a dashed parent pointer from 37 up to 30 — Each Entry links to its two children and to its parent, and holds one colour bit; the tree orders the keys from left to right.

A TreeMap never calls hashCode or equals. It only asks one question: compare(a, b), which is a.compareTo(b) for natural order, or the Comparator you passed to the constructor. A negative result means "go left", a positive one "go right", and 0 means "same key".

The canvas follows the real JDK 21 code. The left panel shows the Java method that is running, with the current line in yellow. The right panel shows the tree of Entry objects, red or black, with each value under its key, and the map's fields root, size, modCount and comparator. The strip below lists the entries in key order, the way any iterator returns them. Every tree shape on this page was checked against a real TreeMap read with reflection.

put: walk down, add a red leaf, fix

put(k, v) starts at root and compares k with each key on the way down. If it meets an equal key, it only replaces the value and returns the old one: size and modCount do not change (Demo 2: put(35, "new") returns "v35"). Otherwise it falls off the tree at a null child and hangs a new red Entry there.

A red leaf keeps every path's black count the same, but its parent may be red too, and a red node may not have a red child. fixAfterInsertion repairs that by looking at the uncle, the grandparent's other child:

case	what fixAfterInsertion does	in Demo 1
parent is black	nothing	put 40, put 35
uncle is red	parent and uncle turn black, grandparent turns red; then check the grandparent the same way (it may move up)	put 20; put 10 (moves up to 30)
uncle is black, new node on the outside	recolour, then one rotation at the grandparent	put 5: rotateRight(20)
uncle is black, new node on the inside (zig-zag)	rotate at the parent first, then the outside case: two rotations	put 37: rotateLeft(35), rotateRight(40)

An insert recolours at most O(log n) nodes and does at most two rotations. A missing child (null) counts as black, so a new node whose uncle does not exist gets rotated (Demo 1: build the tree).

remove: the successor trick

Unlinking a node with zero or one child is easy: its child (if any) takes its place. A node with two children cannot just be unlinked. deleteEntry finds its successor, the next key in order (one step right, then left as far as possible), copies the successor's key and value into the node, and deletes the successor's old Entry instead. The successor has no left child, so that delete is the easy kind.

remove(30) copies the successor's key and value into 30's Entry and deletes the successor's old Entry, which has at most one child.

If the Entry that is unlinked was red, nothing else changes. If it was black, the paths through that spot now have one black node too few, and fixAfterDeletion pushes the missing black back in. It looks at the sibling: a red sibling is turned into a black one with a rotation; a black sibling with two black children turns red and the problem moves up one level; a black sibling with a red child ends the fix with one or two rotations. Demo 3 shows both kinds: remove(30) deletes a red leaf (no fix), and remove(50) copies 70 into the root, then deletes a black leaf and goes through all three sibling cases, three rotations in total.

Order makes questions possible that a HashMap cannot answer quickly. Each is one walk down the tree, O(log n):

floorKey(k): the greatest key ≤ k. lowerKey(k): the greatest key < k.
ceilingKey(k): the least key ≥ k. higherKey(k): the least key > k.
firstKey() and lastKey(): follow the left (or right) links to the end.

The JDK does not keep a "best so far" variable. It walks down, and when the next child it needs is null, it climbs the parent pointers until it comes up from the correct side. On the tree of Demo 1, floorKey(33) = 30, ceilingKey(33) = 35, higherKey(40) = 50 (found by climbing from 40 past 37 and 30) and lowerKey(10) = 5 (Demo 4).

Iteration starts at the leftmost Entry, and each next() calls successor(e): the leftmost node of the right subtree, or, with no right subtree, the first ancestor reached from its left side. One next() can take O(log n) steps, but a full loop walks every link at most twice, so it is O(n) in total (Demo 5).

Views: headMap, tailMap, subMap

headMap(k) (keys < k), tailMap(k) (keys ≥ k), subMap(a, b) and descendingMap() copy nothing. Each returns a small object that holds the map and its bounds and checks them on every call. So the view is live: in Demo 5, map.put(25, …) on the map shows up in headMap(35) at once. Putting a key outside the bounds through the view throws IllegalArgumentException: key out of range.

TreeMap vs other maps

	TreeMap	HashMap	LinkedHashMap	ConcurrentSkipListMap
order	by key	none	insertion (or access)	by key
get / put / remove	O(log n)	O(1) average	O(1) average	O(log n) expected
floor, ceiling, ranges	yes	no	no	yes
null key	no (natural order)	one	one	no
threads	not safe	not safe	not safe	safe, lock-free

Pitfalls

The comparator defines "same key". With String.CASE_INSENSITIVE_ORDER, "apple" and "Apple" compare as 0, so they are one key: the second put replaces the value and keeps the first spelling, {apple=2} (Demo 6). A comparator that disagrees with equals breaks the Map contract in this way.
No null keys with natural order or with most comparators: put(null, …) throws NullPointerException because the key must be compared. Null values are fine.
Don't change a key after putting it in the map if that changes its order. The Entry stays where it was, so later lookups go the wrong way.
Fail-fast iterators. Every structural change (a new key or a removal, not a value replacement) does modCount++. An iterator remembers expectedModCount; if the map changed behind its back, the next next() throws ConcurrentModificationException. Remove inside a loop with it.remove(), which updates expectedModCount (Demo 6).
Not thread-safe. Use Collections.synchronizedSortedMap or ConcurrentSkipListMap for shared maps.

What the page leaves out

buildFromSorted, the linear-time build that putAll and the copy constructor use for a SortedMap; descending iterators and descendingMap; pollFirstEntry and friends; subMap with both bounds; putIfAbsent, compute and merge; serialization; and TreeSet, which is a TreeMap whose values are one shared dummy object. The page also draws a new Entry red at once: the JDK creates it black and fixAfterInsertion makes it red in its first line.