Collections Framework

Sorted Collections

TreeMap and TreeSet keep elements permanently sorted in a red-black tree: O(log n) operations, in-order iteration, and navigation queries (floor, ceiling, ranges) that hash structures cannot answer.

Red-black tree: self-balancing; height ≤ 2 log n guaranteed
Order comes from Comparable or a Comparator supplied at construction
Membership uses compareTo, not equals — keep them consistent
NavigableMap/Set: floorKey, ceilingKey, headMap, tailMap, subMap, descending*
Sorted ≠ sort-once: for one-time ordering, sorting an ArrayList is cheaper

Navigation queries

NavigableMap<LocalDate, Meeting> calendar = new TreeMap<>();

Meeting nextMeeting = calendar.ceilingEntry(today).getValue();   // earliest ≥ today
var thisWeek = calendar.subMap(monday, true, friday, true);      // range view
var latestPast = calendar.floorEntry(today);                     // latest ≤ today

These queries are the reason to choose a tree: schedules, price ladders, version lookups ("newest release ≤ requested"), leaderboards. A HashMap can only answer exact-key questions; a TreeMap answers nearest-key and range questions at the same O(log n).

Custom order at construction

SortedSet<Employee> byPay = new TreeSet<>(
        Comparator.comparingDouble(Employee::salary).reversed()
                  .thenComparing(Employee::id));      // tie-breaker keeps distinct elements
byPay.addAll(staff);

NavigableMap range views: subMap, headMap, tailMap

NavigableMap<Integer, String> gradeBands = new TreeMap<>(Map.of(
        90, "A", 80, "B", 70, "C", 60, "D"));

// subMap(from, fromInclusive, to, toInclusive) — an arbitrary range, live view
SortedMap<Integer, String> passing = gradeBands.subMap(60, true, 100, false);

// headMap(toKey) — everything strictly below toKey; headMap(toKey, true) includes it
SortedMap<Integer, String> belowB = gradeBands.headMap(80);          // {60=D, 70=C}

// tailMap(fromKey) — everything from fromKey up; inclusive by default
SortedMap<Integer, String> bAndUp = gradeBands.tailMap(80);          // {80=B, 90=A}

// all three are VIEWS: writes through to gradeBands, and vice versa
passing.remove(70);          // also removes 70 from gradeBands