Deep Dive (java.util) - TreeMap
Red-Black Trees in the JDK
"When you need your keys sorted, there's a Red-Black tree working silently behind every
get()."
TreeMap is a sorted map backed by a Red-Black tree — a self-balancing binary search tree. This deep dive explains the tree structure, rotations, and when to choose TreeMap over HashMap.
What is TreeMap, Really?
TreeMap stores key-value pairs in a Red-Black tree — a self-balancing binary search tree that guarantees O(log n) operations for get, put, and remove.
Key insight: Unlike HashMap, TreeMap keeps entries sorted by key at all times. Iteration always returns keys in sorted order.
Red-Black Tree Basics
A Red-Black tree is a binary search tree with these additional properties:
These properties guarantee that the tree's height is at most 2 × log₂(n + 1), ensuring O(log n) for all operations.
The Entry Node
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left; // Left child
Entry<K,V> right; // Right child
Entry<K,V> parent; // Parent node
boolean color = BLACK; // RED or BLACK
}
Example Red-Black Tree
In this tree:
Every path from root (13) to a null leaf passes through exactly 2 BLACK nodes
No RED node has a RED child
The root (13) is BLACK
How put() Works — Insert and Rebalance
Phase 1: Binary Search Tree Insert
First, traverse the tree to find the correct position:
Phase 2: Fix Violations (Rotations and Recoloring)
After inserting a RED node, we may violate rule 3 (no adjacent RED nodes). The fixAfterInsertion method corrects this:
Rotation Visualized
How get() Works — Binary Search
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p == null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
if (comparator != null)
return getEntryUsingComparator(key);
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p; // Found!
}
return null; // Not found
}
How remove() Works
Removal from a Red-Black tree is the most complex operation:
Find the node (binary search — O(log n))
If node has two children, replace with in-order successor
Delete the node
Fix Red-Black violations (
fixAfterDeletion)
NavigableMap Operations
TreeMap's killer feature is its rich navigation API:
TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "ten");
map.put(20, "twenty");
map.put(30, "thirty");
map.put(40, "forty");
map.put(50, "fifty");
// Floor: greatest key ≤ given key
map.floorKey(25); // 20
map.floorKey(30); // 30
// Ceiling: smallest key ≥ given key
map.ceilingKey(25); // 30
map.ceilingKey(30); // 30
// Lower/Higher: strictly less/greater
map.lowerKey(30); // 20
map.higherKey(30); // 40
// First/Last
map.firstKey(); // 10
map.lastKey(); // 50
// Range views (backed by the same tree!)
SortedMap<Integer, String> sub = map.subMap(20, 40);
// {20=twenty, 30=thirty} — excludes 40
NavigableMap<Integer, String> desc = map.descendingMap();
// {50=fifty, 40=forty, 30=thirty, 20=twenty, 10=ten}
Key insight: Range views (
subMap,headMap,tailMap) are views — they reflect changes to the original map and vice versa. They don't copy data.
Comparator vs Comparable
TreeMap orders keys using one of two mechanisms:
// Natural ordering (keys must be Comparable)
TreeMap<String, Integer> map1 = new TreeMap<>();
map1.put("Banana", 2);
map1.put("Apple", 1);
map1.put("Cherry", 3);
// Iteration: Apple, Banana, Cherry (alphabetical)
// Custom Comparator — reverse order
TreeMap<String, Integer> map2 = new TreeMap<>(Comparator.reverseOrder());
map2.putAll(map1);
// Iteration: Cherry, Banana, Apple
// Custom Comparator — by string length
TreeMap<String, Integer> map3 = new TreeMap<>(
Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder())
);
Warning: If your
Comparatorsays two keys are equal (comparereturns 0), TreeMap treats them as the same key — the secondputwill overwrite the first, even ifequals()says they're different!
Performance Characteristics
| Operation | Time Complexity | Notes |
|---|---|---|
get(key) |
O(log n) | Binary search down the tree |
put(key, value) |
O(log n) | Search + insert + rebalance |
remove(key) |
O(log n) | Search + delete + rebalance |
containsKey(key) |
O(log n) | Same as get |
containsValue(value) |
O(n) | Must scan all nodes |
firstKey() / lastKey() |
O(log n) | Walk left/right edge |
floorKey() / ceilingKey() |
O(log n) | Modified binary search |
subMap() / headMap() / tailMap() |
O(log n) to create | View creation is cheap |
| Iteration | O(n) | In-order traversal |
TreeMap vs HashMap vs LinkedHashMap
| Aspect | HashMap | TreeMap | LinkedHashMap |
|---|---|---|---|
| Order | None | Sorted by key | Insertion order |
| get/put | O(1) avg | O(log n) | O(1) avg |
| Null keys | 1 allowed | ❌ Not allowed | 1 allowed |
| Null values | ✅ | ✅ | ✅ |
| Thread-safe | ❌ | ❌ | ❌ |
| Navigation | ❌ | ✅ floor/ceiling/range | ❌ |
| Memory | Moderate | High (tree nodes) | HashMap + linked list |
| Best for | General use | Sorted data, range queries | Ordered iteration, LRU cache |
Common Pitfalls
Pitfall 1: Non-Comparable Keys Without Comparator
// ❌ ClassCastException at runtime!
TreeMap<Object, String> map = new TreeMap<>();
map.put(new Object(), "value");
// Object doesn't implement Comparable → crash
// ✅ Provide a Comparator
TreeMap<Object, String> map = new TreeMap<>(
Comparator.comparingInt(System::identityHashCode)
);
Pitfall 2: Inconsistent Comparator and equals()
// ❌ TRAP: Comparator says case-insensitive, equals() is case-sensitive
TreeMap<String, Integer> map = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
map.put("Hello", 1);
map.put("HELLO", 2); // Overwrites! Comparator says "Hello" == "HELLO"
map.size(); // 1, not 2!
Pitfall 3: Null Keys
// ❌ NullPointerException!
TreeMap<String, Integer> map = new TreeMap<>();
map.put(null, 1); // Cannot compare null with Comparable.compareTo()
Summary
The one-liner: TreeMap is a Red-Black tree providing O(log n) sorted map operations with rich navigation APIs — choose it when you need range queries or sorted iteration, accept the O(log n) cost vs HashMap's O(1).