How Java works

Pick a topic, write code and watch what happens inside, step by step.

Memory

Collections

Concurrency

Language and JVM

Topics

How TreeMap works

An ordered tree

HashMap keeps no order, while TreeMap always keeps keys sorted. For each Node: smaller on the left, larger on the right.

Each search step discards half: O(log n). About 20 comparisons for 1 million keys.

Press get on the left and watch the path.

The red-black rules

If keys arrive in order, a plain tree turns into a list and becomes O(n). A red-black tree keeps balance with colors.

The three rules on the right are checked live. They ensure the longest path is at most twice the shortest.

Add other keys: the rules never break.

Insert: recolor

A new Node starts red, because that does not change the black count. If its parent is also red, a fix is needed.

If the uncle is red too, the cheapest fix is recoloring: parent and uncle turn black, grandparent turns red.

Press put for 1 on the left and step through.

Insert: rotation

If the uncle is black, colors are not enough. A rotation moves Nodes without breaking the order.

Here we have 10, 5. Press put for 1: a right rotation. Then press Clear and enter 10, 5, 7: a left, then a right rotation.

One insert makes at most 2 rotations.

Remove

A Node with two children is not removed directly: the next key is written in its place and the old Node goes.

If the removed Node is red, no rule breaks. If it is black, fixAfterDeletion restores balance with rotation and color.

Press remove for 30 on the left.

Navigation and traps

Order allows queries that HashMap cannot do: floorKey, ceilingKey, headMap, tailMap, firstKey.

A null key is not allowed, because it must be compared.

The most hidden trap: for TreeMap, same means compareTo == 0, not equals. With a length Comparator, "Leyla" replaces the value of "Aysel".