AtticCollectionsMaps
TreeMap
NavigableMap contracts, Red-Black tree key sorting, boundary lookups, and range query slices
TreeMap<K, V> orders its entries by key using the key's natural Comparable ordering or an explicit Comparator. It implements NavigableMap<K, V> and SortedMap<K, V>.
Sorted Key & Boundary Lookups
NavigableMap<Integer, String> tm = new TreeMap<>();
tm.put(30, "C");
tm.put(10, "A");
tm.put(20, "B");
// Bounds
int first = tm.firstKey(); // 10 (throws if empty)
int last = tm.lastKey(); // 30 (throws if empty)
// Nearest Key Lookups
Integer lower = tm.lowerKey(20); // 10 (strictly < 20)
Integer floor = tm.floorKey(20); // 20 (<= 20)
Integer ceiling = tm.ceilingKey(25); // 30 (>= 25)
Integer higher = tm.higherKey(20); // 30 (strictly > 20)
// Sub-maps and Range Views
SortedMap<Integer, String> slice = tm.subMap(10, 30); // [10, 20]| Method | Return Type | Rule |
|---|---|---|
firstKey() / lastKey() | K | Lowest or highest key |
firstEntry() / lastEntry() | Map.Entry<K, V> | Lowest or highest entry (returns null if empty) |
lowerKey(k) | K | Strictly less than k |
floorKey(k) | K | Less than or equal to k |
ceilingKey(k) | K | Greater than or equal to k |
higherKey(k) | K | Strictly greater than k |
pollFirstEntry() / pollLastEntry() | Map.Entry<K, V> | Removes and returns boundary entry |
subMap(from, to) | SortedMap<K, V> | Half-open slice [from, to) |
Null Key Prohibition: Under natural ordering, TreeMap forbids null keys and throws
NullPointerException on insertion because keys must be comparable. null values are permitted.
Complexity Profile
| Operation | Time Complexity | Notes |
|---|---|---|
get() / put() / remove() | O(log n) | Balanced Red-Black tree traversal |
firstKey() / lastKey() | O(log n) | Leftmost or rightmost leaf lookup |
Range Views (subMap, headMap) | O(log n) | Cost to locate initial boundary key |