SortedSet, NavigableSet and TreeSet in Java - Quiz

SortedSet is the sorted set interface (Java 1.2): unique elements kept in ascending order, by natural ordering (Comparable) or by a Comparator. It adds first(), last(), headSet(), subSet(), tailSet() and comparator() to Set.

NavigableSet (Java 6) extends SortedSet with navigation methods: ceiling(), floor(), higher(), lower(), pollFirst(), pollLast(), descendingSet(), descendingIterator() and range overloads with inclusive flags.

TreeSet is a class that implements both interfaces on a red-black tree; the thread-safe alternative is ConcurrentSkipListSet. So “SortedSet vs TreeSet” is a question of the variable type: declare NavigableSet if you need ceiling()/floor() or range flags, and SortedSet if first(), last() and subSet() are enough.

NavigableSet<Integer> departures = new TreeSet<>();

All four find the element closest to the argument. ceiling(e) returns the smallest element greater than or equal to e; floor(e) — the largest element less than or equal to it; higher(e) and lower(e) do the same but strictly: an equal element is skipped.

NavigableSet<Integer> set = new TreeSet<>(List.of(10, 20, 30));
set.ceiling(20); // 20
set.higher(20);  // 30
set.floor(20);   // 20
set.lower(20);   // 10
set.ceiling(35); // null

If there is no such element, the methods return null instead of throwing. That is why departures.lower(1600) is safer than departures.headSet(1600).last(): on an empty subset last() throws NoSuchElementException. The trap is unboxing: int next = set.ceiling(100); throws NullPointerException when nothing matches, so keep the result in an Integer and check it for null.

The SortedSet methods use a half-open interval: the lower bound is included, the upper bound is not. headSet(to) returns elements strictly less than to, tailSet(from) — elements greater than or equal to from, subSet(from, to) — from from inclusive to to exclusive.

NavigableSet adds overloads with flags: headSet(to, inclusive), tailSet(from, inclusive), subSet(from, fromInclusive, to, toInclusive).

NavigableSet<Integer> scores = new TreeSet<>(List.of(72, 80, 85, 90, 97));
scores.subSet(80, 90);              // [80, 85]
scores.subSet(80, true, 90, true);  // [80, 85, 90]
scores.tailSet(85, false);          // [90, 97]
scores.subSet(75, 95);              // [80, 85, 90]
scores.subSet(90, 80);              // IllegalArgumentException: fromKey > toKey

The bounds do not have to be elements of the set. The smaller bound must come first; for reverse order use descendingSet().subSet(90, 80).

No. headSet(), tailSet(), subSet() and descendingSet() return a view backed by the original set (a backed collection). Changes are visible both ways: an element added to the original TreeSet shows up in the view if it falls into its range, and an element removed through the view disappears from the original.

TreeSet<String> fruits = new TreeSet<>(List.of("apple", "banana", "cherry", "date", "fig"));
NavigableSet<String> upToCherry = fruits.headSet("cherry", true); // [apple, banana, cherry]
fruits.add("blueberry");    // upToCherry: [apple, banana, blueberry, cherry]
upToCherry.remove("apple"); // fruits: [banana, blueberry, cherry, date, fig]
upToCherry.add("grape");    // IllegalArgumentException: key out of range

A value outside the view’s range cannot be added through it. If you need an independent copy of a range, create it explicitly: new TreeSet<>(fruits.headSet("cherry", true)).

pollFirst() and pollLast() return the smallest and largest element and remove it at once; for an empty set they return null, while first() and last() throw NoSuchElementException. A while ((x = set.pollFirst()) != null) loop processes elements in ascending order and empties the set at the same time.

The regular iterator() of a TreeSet always goes in ascending order. For reverse order there is descendingSet() — a reverse-order view — and descendingIterator(), which walks from the largest element to the smallest.

TreeSet<String> steps = new TreeSet<>(List.of("deploy", "build", "test", "review"));
steps.descendingSet(); // [test, review, deploy, build]
steps.pollFirst();     // build
steps.pollLast();      // test
System.out.println(steps); // [deploy, review]

Since Java 21 SortedSet extends SequencedSet: a TreeSet has getFirst(), getLast(), removeFirst(), removeLast() and reversed(), but addFirst() and addLast() throw UnsupportedOperationException — the comparator decides where an element goes.

TreeSet stores its elements as keys of a TreeMap, a red-black tree, so add(), remove() and contains() take O(log n): slower than the O(1) on average of a HashSet, but faster than a linear search in a list. The class is not thread-safe. Duplicates are detected with compareTo() or compare(), not with equals().

Constructors:

• TreeSet() — natural ordering; an element without Comparable causes ClassCastException on add(), null causes NullPointerException;
• TreeSet(Comparator) — order defined by the comparator;
• TreeSet(Collection) — a copy in natural ordering, duplicates dropped: new TreeSet<>(List.of("sql", "java", "git", "java")) gives [git, java, sql];
• TreeSet(SortedSet) — copies both the elements and the comparator.

Which of the last two runs is decided by the compiler from the declared type of the argument: a SortedSet with Comparator.reverseOrder() passed as a Collection is silently re-sorted in ascending order.