TreeMap and sorted maps

the picture

you know how a HashMap is fast but has no idea which key is "next"? sometimes order is the whole point: leaderboards, time series, price levels, "which shift covers 14:30?".

a binary search tree is the classic answer: smaller keys to the left, bigger to the right, so finding a key is a walk from the root, halving the candidates at each step. the catch is that it only halves if the tree is bushy. insert keys in sorted order into a plain BST and every node hangs off the right of the last one. you've built a linked list with extra steps, and lookups are O(n).

a red-black tree is a BST with a tidiness rule. every node carries one extra bit, its colour, and four rules hold after every insert:

1. every node is red or black.
2. the root is black.
3. a red node never has a red child.
4. every path from a node down to an empty spot passes the same number of black nodes.

rules 3 and 4 together mean the longest path can be at most twice the shortest. so the height stays under 2·log₂(n + 1), whatever order the keys arrive in. when an insert breaks a rule, the tree fixes it locally with recolors and rotations.

that's the exact algorithm from TreeMap.fixAfterInsertion in jdk 25. i checked the trees it builds against the real TreeMap (read through reflection): same shape, same colours, for every sequence in the figure.

three moves, that's all there is:

• recolor when the new node's parent and uncle are both red: parent and uncle go black, grandparent goes red, and the check continues from the grandparent (it may now have a red parent).
• one rotation when the uncle is black and the three nodes form a straight line: the parent moves up, the grandparent moves down.
• two rotations when they form a zig-zag: the first straightens it, the second is the straight-line case.

a rotation is a constant-time pointer swap, and an insert does at most two of them. recolors can climb the tree, but that's O(log n) at worst. that's why put is O(log n) with a small constant.

what sorted buys you

TreeMap implements NavigableMap, which is SortedMap plus "search around" methods:

void main() {
    TreeMap<Integer, String> m = new TreeMap<>();
    for (int k : List.of(50, 20, 70, 10, 40, 60, 30)) m.put(k, "v" + k);
    IO.println(m.keySet());
    IO.println(m.floorKey(45) + " " + m.ceilingKey(45) + " " + m.lowerKey(40) + " " + m.higherKey(40));
    IO.println(m.headMap(40) + " " + m.tailMap(60, false).keySet());
    IO.println(m.subMap(20, 50).keySet() + " " + m.firstKey() + " " + m.lastEntry());
    IO.println(m.floorKey(5) + " " + m.descendingMap().firstKey());
}

[10, 20, 30, 40, 50, 60, 70]
40 50 30 50
{10=v10, 20=v20, 30=v30} [70]
[20, 30, 40] 10 70=v70
null 70

the defaults trip people up: headMap(to) excludes to, tailMap(from) includes from, subMap(from, to) is from-inclusive, to-exclusive (like String.substring). every one of them has an overload with explicit boolean flags, and the views are live: put into the map and a matching key shows up in the view.

a real use: grade boundaries, or any "which bracket does this fall into" table.

var grades = new TreeMap<Integer, String>(Map.of(90, "A", 80, "B", 70, "C", 60, "D"));
IO.println(grades.floorEntry(85).getValue() + " " + grades.floorEntry(90).getValue() + " " + grades.floorEntry(59));

the comparator is the law

a TreeMap never calls equals or hashCode. it calls compareTo (or your Comparator) and that's it. two keys that compare as 0 are, as far as the map is concerned, the same key.

two more ways it bites:

• keys must be comparable. a key type that isn't Comparable (and no Comparator given) throws ClassCastException on the very first put, even into an empty map.
• no null keys with natural ordering: put(null, v) throws NullPointerException, because there's nothing to compare it with. (null values are fine.)

TreeMap or HashMap?

in my rough measurements (100,000 Integer keys, jdk 25, the same setup as the deque numbers), TreeMap.get took about 150 ns against about 33 ns for HashMap.get. a balanced tree of 100,000 nodes means 17 to 20 levels of pointer chasing, a hash table is one or two hops. so: HashMap by default, TreeMap when you need the order or the navigation. and if several threads need a sorted map, there's ConcurrentSkipListMap (more in concurrent collections).