library
intermediateTreeMap, TreeSet & Natural Ordering
Use sorted collections backed by Red-Black trees and understand Comparable vs Comparator in this context.
TreeMap<K,V> and TreeSet<E> maintain their elements in sorted order, backed by a Red-Black tree. All operations (get, put, remove, containsKey) are O(log n).
TreeMap = a filing cabinet where files are always in alphabetical order. Finding any file takes longer than a HashMap (drawer scan) but you can instantly find 'all files from A to M.'
Key Concepts
1
Sorting requires elements to be comparable. Two options:
1. Natural ordering: elements implement Comparable<T>. TreeSet<String> uses String's natural ordering (lexicographic).
2. Custom Comparator: pass a Comparator to the constructor. TreeMap<String, V>(String.CASE_INSENSITIVE_ORDER).
2
Navigable operations (unique to sorted collections):
- firstKey()/lastKey(): smallest/largest element
- headMap(key)/tailMap(key): view of elements before/after a key
- subMap(from, to): range view
- floorKey(key)/ceilingKey(key): nearest key ≤ or ≥
- descendingMap(): reverse-order view
3
Consistency with equals: if compareTo() returns 0 for two objects, TreeSet treats them as equal (even if equals() returns false). This can cause 'lost' elements. Example: a case-insensitive comparator makes 'ABC' and 'abc' equal in a TreeSet — only one is kept.
4
When to use TreeMap vs HashMap: TreeMap when you need sorted iteration or range queries. HashMap when you only need O(1) lookups and don't care about order.