☕ JavaCollections Framework

TreeMap

TreeMap is a Red-Black tree implementation of the NavigableMap interface. It stores key-value pairs in sorted order — either the natural ordering of keys (requiring them to implement Comparable) or a custom Comparator provided at construction. All basic operations (get, put, remove, containsKey) are O(log n). TreeMap provides rich navigation operations: finding the closest key, extracting sub-maps, and headMap/tailMap views.

TreeMap — Sorted Keys and Red-Black Tree

TreeMap stores entries in a self-balancing Red-Black tree. A Red-Black tree is a binary search tree with colour properties on nodes (red or black) that guarantee the tree remains balanced — no path from root to leaf is more than twice as long as any other. This balance guarantee ensures O(log n) worst-case time for all basic operations: get, put, remove, and containsKey. Keys must be mutually comparable. If the key type implements Comparable (like String, Integer, LocalDate, and most standard types), TreeMap uses natural ordering by default. If you need custom ordering — case-insensitive string ordering, reverse order, ordering by a computed field — you provide a Comparator to the TreeMap constructor. Keys that are neither Comparable nor have a Comparator produce a ClassCastException on the first put. Unlike HashMap (which uses equals() and hashCode()) and LinkedHashMap (same), TreeMap uses the comparator or natural ordering to determine equality. Two keys are considered equal if compare(k1, k2) == 0. This means TreeMap's notion of equality is based on comparison, not equals(). If your Comparator considers two objects equal by returning 0 but equals() returns false, the TreeMap treats them as the same key and the second put replaces the first. This inconsistency with equals() is a potential source of bugs. The sorted-order property of TreeMap enables the NavigableMap operations that HashMaps cannot provide: floorKey(k) returns the greatest key less than or equal to k, ceilingKey(k) returns the smallest key greater than or equal to k, lowerKey(k) returns the greatest key strictly less than k, and higherKey(k) returns the smallest key strictly greater than k. These enable efficient range queries and nearest-match searches.

Java

// ── TreeMap with natural ordering (Comparable keys): ─────────────────
TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("Charlie", 3);
treeMap.put("Alice",   1);
treeMap.put("Bob",     2);
treeMap.put("Dave",    4);

System.out.println(treeMap);  // {Alice=1, Bob=2, Charlie=3, Dave=4} — sorted!

// ── First and last keys: ──────────────────────────────────────────────
System.out.println(treeMap.firstKey());   // Alice
System.out.println(treeMap.lastKey());    // Dave

// ── Navigation operations: ────────────────────────────────────────────
System.out.println(treeMap.floorKey("Bob"));    // Bob — greatest key <= "Bob"
System.out.println(treeMap.ceilingKey("Bob"));  // Bob — smallest key >= "Bob"
System.out.println(treeMap.lowerKey("Bob"));    // Alice — strictly < "Bob"
System.out.println(treeMap.higherKey("Bob"));   // Charlie — strictly > "Bob"

System.out.println(treeMap.floorKey("Bart"));   // Alice — "Bart" not present, floor is "Alice"
System.out.println(treeMap.ceilingKey("Bart")); // Bob   — ceiling of absent "Bart" is "Bob"

// ── Custom Comparator — reverse order: ───────────────────────────────
TreeMap<String, Integer> reverse = new TreeMap<>(Comparator.reverseOrder());
reverse.put("Charlie", 3); reverse.put("Alice", 1); reverse.put("Bob", 2);
System.out.println(reverse); // {Charlie=3, Bob=2, Alice=1}

// ── Custom Comparator — case-insensitive: ────────────────────────────
TreeMap<String, String> caseInsensitive =
    new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
caseInsensitive.put("hello", "value1");
caseInsensitive.put("HELLO", "value2");  // same key (case-insensitive) — replaces
System.out.println(caseInsensitive.size());   // 1
System.out.println(caseInsensitive.get("Hello")); // value2

SubMap, HeadMap, TailMap Views

TreeMap provides views that expose a portion of the map as a SortedMap or NavigableMap. These views are backed by the original TreeMap — changes to the view are reflected in the original, and changes to the original are reflected in the view. The views enforce their key range, throwing IllegalArgumentException if you try to put a key outside the specified range. headMap(toKey) returns a view of all entries with keys strictly less than toKey. tailMap(fromKey) returns a view of all entries with keys greater than or equal to fromKey. subMap(fromKey, toKey) returns a view of entries with keys in [fromKey, toKey). These are the SortedMap versions with half-open intervals. The NavigableMap overloads provide more control: headMap(toKey, inclusive), tailMap(fromKey, inclusive), and subMap(fromKey, fromInclusive, toKey, toInclusive) let you specify whether each bound is inclusive or exclusive. This is the more flexible form and is usually preferred. These views are particularly useful for range queries: all users with usernames between "A" and "M", all orders placed in a date range, all scores above a threshold. Because TreeMap is sorted, these range queries are O(log n) to find the start position and O(k) to iterate through k results — efficiently proportional to the result size, not the total map size.

Java

TreeMap<Integer, String> scores = new TreeMap<>();
scores.put(10, "F"); scores.put(30, "D"); scores.put(50, "C");
scores.put(70, "B"); scores.put(90, "A");

// ── headMap — keys strictly less than toKey: ─────────────────────────
SortedMap<Integer, String> below60 = scores.headMap(60);
System.out.println(below60);  // {10=F, 30=D, 50=C}

// ── tailMap — keys >= fromKey: ───────────────────────────────────────
SortedMap<Integer, String> above60 = scores.tailMap(60);
System.out.println(above60);  // {70=B, 90=A}

// ── subMap — [fromKey, toKey): ────────────────────────────────────────
SortedMap<Integer, String> passing = scores.subMap(60, 100);
System.out.println(passing);  // {70=B, 90=A}

// ── NavigableMap — inclusive/exclusive control: ───────────────────────
NavigableMap<Integer, String> nav = scores;
System.out.println(nav.subMap(30, true, 70, true));  // {30=D, 50=C, 70=B}
System.out.println(nav.subMap(30, false, 70, false)); // {50=C}
System.out.println(nav.headMap(70, true));  // includes 70: {10=F, 30=D, 50=C, 70=B}
System.out.println(nav.tailMap(50, false)); // excludes 50: {70=B, 90=A}

// ── Views are backed — modifications reflected: ───────────────────────
SortedMap<Integer, String> view = scores.tailMap(50);
view.put(60, "B+");   // adds to original TreeMap — 60 is in range
System.out.println(scores.get(60));   // "B+" — in original map
// view.put(30, "D");  // IllegalArgumentException — 30 not in tailMap(50)

// ── pollFirstEntry / pollLastEntry — remove and return: ───────────────
Map.Entry<Integer, String> first = scores.pollFirstEntry();  // removes min
Map.Entry<Integer, String> last  = scores.pollLastEntry();   // removes max
System.out.println("Removed first: " + first);   // 10=F
System.out.println("Removed last:  " + last);    // 90=A (or 60=B+ if added)

// ── Practical: sorted frequency map: ─────────────────────────────────
String[] words = {"banana", "apple", "cherry", "apple", "banana", "apple"};
TreeMap<String, Long> wordCount = new TreeMap<>();
for (String w : words) wordCount.merge(w, 1L, Long::sum);
System.out.println(wordCount);  // {apple=3, banana=2, cherry=1} — sorted!

TreeMap

TreeMap — Sorted Keys and Red-Black Tree

SubMap, HeadMap, TailMap Views

Related Topics in Collections Framework