TreeMap, TreeSet, and ordered structures
Red-black trees under the hood. O(log n) sorted access, range queries, and floor/ceiling lookups.
Runs on a sandboxed JVM via the public Piston API. Edit the code and hit Run.
Ordered, not just sorted
TreeMap keeps its entries in key order at all times. Iterating a TreeMap gives you a sorted sequence; firstKey, lastKey, ceilingKey, and floorKey all run in O(log n). Compare that with HashMap, where iteration order is unspecified.
Red-black trees
The internal structure is a red-black tree — a self-balancing binary search tree where every path from root to leaf differs in length by at most a factor of two. That guarantee keeps get, put, and remove all at O(log n) regardless of insertion order.
Range views
headMap(k), tailMap(k), and subMap(lo, hi) return live views over a slice of the map. Modifying the view modifies the source and vice versa. These are ideal for pulling out ranges — say, all events between two timestamps — without copying.
Runs on a sandboxed JVM via the public Piston API. Edit the code and hit Run.
Custom ordering
Pass a Comparator to the constructor to override natural ordering: new TreeMap<>(Comparator.reverseOrder()). For custom types, either implement Comparable for a natural order or pass a Comparator — pick one and stick to it, since mixing them is a common bug source.
TreeSet — sorted uniqueness
TreeSet is the set flavor of the same structure. It gives you sorted iteration, first, last, ceiling, floor, headSet, tailSet, and O(log n) membership. Use it when you need both dedupe and order.
When to use it
Reach for TreeMap/TreeSet when you need sorted iteration, range queries, or nearest-neighbor lookups (floor/ceiling). Stick with HashMap/HashSet when order doesn't matter — hashing is faster and more memory-efficient.
Related lessons & next topics
Keep going — these pair well with TreeMap, TreeSet, and ordered structures.
- § 6.01 · Data Structures in JavaArrays and ArrayList — the workhorses
Fixed-size arrays vs dynamic ArrayList. Memory layout, amortized O(1) append, and when each one shines.
Beginner · 22 min - § 6.02 · Data Structures in JavaLinkedList and the Deque interface
Doubly-linked nodes, O(1) insert at either end, and why LinkedList is almost never the right choice.
Beginner · 20 min - § 6.03 · Data Structures in JavaStacks, queues, and ArrayDeque
LIFO, FIFO, and why java.util.Stack is a historical mistake you should avoid.
Intermediate · 24 min - § 6.04 · Data Structures in JavaHashMap, equals, and hashCode
How hashing works, why you must override equals and hashCode together, and the load factor that keeps lookups O(1).
Intermediate · 28 min