AtticCollectionsSets
TreeSet
NavigableSet and SortedSet contracts, Red-Black tree mechanics, nearest neighbor lookups, and range queries
TreeSet<E> stores elements in a self-balancing Red-Black binary search tree (backed by TreeMap). Elements are maintained in ascending sorted order according to their natural Comparable ordering or a supplied Comparator.
NavigableSet Lookups & Range Queries
NavigableSet<Integer> ts = new TreeSet<>(List.of(10, 20, 30, 40));
// Extrema
int min = ts.first(); // 10 (throws if empty)
int max = ts.last(); // 40 (throws if empty)
// Nearest Neighbor Lookups
Integer lower = ts.lower(20); // 10 (strictly less: < 20)
Integer floor = ts.floor(20); // 20 (less than or equal: <= 20)
Integer ceiling = ts.ceiling(25); // 30 (greater than or equal: >= 25)
Integer higher = ts.higher(20); // 30 (strictly greater: > 20)
// Polling
Integer polledHead = ts.pollFirst(); // 10 (removes and returns)
Integer polledTail = ts.pollLast(); // 40 (removes and returns)Boundary Query Cheat Sheet
| Method | Comparison | Result on [10, 20, 30, 40] for 20 |
|---|---|---|
lower(e) | Strictly less (< e) | 10 |
floor(e) | Less than or equal (<= e) | 20 |
ceiling(e) | Greater than or equal (>= e) | 20 |
higher(e) | Strictly greater (> e) | 30 |
subSet(10, 30) | Half-open range [10, 30) | [10, 20] |
headSet(30) | Strictly before 30 (< 30) | [10, 20] |
tailSet(20) | Starting from 20 (>= 20) | [20, 30, 40] |
descendingSet() | Reverse-ordered view | [40, 30, 20, 10] |
Null Prohibition: Under natural ordering, TreeSet strictly forbids null elements and
throws NullPointerException on insertion because null.compareTo(...) cannot be evaluated.
Complexity Profile
| Operation | Time Complexity | Notes |
|---|---|---|
add() / remove() / contains() | O(log n) | Balanced Red-Black tree traversal |
first() / last() | O(log n) | Traverses to leftmost or rightmost leaf |
floor() / ceiling() | O(log n) | Locates closest bounded leaf node |