1. Overview
Sometimes, we need unique elements in sorted order. In this lesson, we’ll explore how TreeSet supports sorting, nearest-element queries, and range views, along with its strengths and limitations.
The relevant module we need to import when starting this lesson is: treeset-sorted-set-and-natural-processing-start.
If we want to reference the fully implemented lesson, we can import: treeset-sorted-set-and-natural-processing-end.
2. TreeSet and Natural Ordering
A TreeSet uses a self-balancing red-black tree to keep its elements sorted. Basic operations such as add(), contains(), and remove() take logarithmic time as the set grows.
The benefit is that iteration is always sorted, and we also gain access to nearest-element queries that hash-based sets don’t provide.
By default, a TreeSet relies on each element’s Comparable implementation. Strings, therefore, sort lexicographically, and integers sort numerically. We’ve explored natural ordering earlier in the course.
Let’s open TreeSetUnitTest and add a new test, whenUsingNaturalOrder_thenStringsSorted(), to validate TreeSet‘s natural order:
@Test
void whenUsingNaturalOrder_thenStringsSorted() {
TreeSet<String> languages = new TreeSet<>();
languages.add("es");
languages.add("fr");
languages.add("de");
List<String> ordered = new ArrayList<>(languages);
assertEquals(List.of("de", "es", "fr"), ordered);
}
In this test, we insert three language codes in scrambled order. The assertion verifies that iteration returns them in alphabetical order: de, es, fr.
3. Custom Comparator Sorting
We can sort the objects of a TreeSet differently from their natural order. We do this by passing a Comparator to its constructor.
We’ve explored comparators earlier in the course. Let’s add another test to TreeSetUnitTest:
@Test
void whenUsingTaskComparator_thenTasksSortedByCodeLength() {
Comparator<Task> byCodeLength = Comparator.comparingInt(t -> t.getCode()
.length());
TreeSet<Task> tasks = new TreeSet<>(byCodeLength);
tasks.add(new Task("02", "B", "B", null));
tasks.add(new Task("010", "C", "C", null));
tasks.add(new Task("1", "A", "A", null));
List<String> codes = new ArrayList<>();
for (Task task : tasks) {
String code = task.getCode();
codes.add(code);
}
assertEquals(List.of("1", "02", "010"), codes);
}
First, we create a comparator that compares by code length. Then, we pass it to the TreeSet constructor. Shorter codes appear first in the iteration.
A custom comparator replaces natural ordering. It also determines uniqueness: this length-only comparator treats two tasks with equally long codes as the same set element, even when their codes differ.
4. Range-View and Nearest Element Operations
TreeSet implements the NavigableSet interface, which itself extends SortedSet. These APIs provide useful methods for working with sorted collections and for navigating elements based on proximity to a target value.
4.1. Sorted and Navigable Operations
Let’s explore some of the most useful methods provided by these interfaces:
- From SortedSet:
- first() returns the lowest element
- last() returns the highest element
- subSet(from, to) returns a view of elements from from (inclusive) to to (exclusive)
- headSet(to) returns a view of elements strictly less than to
- tailSet(from) returns a view of elements greater than or equal to from
- From NavigableSet:
- lower(e) returns the greatest element strictly less than e
- floor(e) returns the greatest element less than or equal to e
- ceiling(e) returns the least element greater than or equal to e
- higher(e) returns the least element strictly greater than e
- pollFirst() retrieves and removes the lowest element
- pollLast() retrieves and removes the highest element
- Overloaded subSet(), headSet(), and tailSet() allow control of inclusive and exclusive bounds
4.2. Backed Range Views
These range methods return live views backed by the original set. This means that updates in the view are reflected in the underlying TreeSet, and vice versa. Let’s add a range-query test to TreeSetUnitTest:
@Test
void whenUsingRangeQueries_thenCorrectElementsReturned() {
TreeSet<Integer> scores = new TreeSet<>();
scores.add(55);
scores.add(70);
scores.add(85);
scores.add(95);
scores.add(100);
Integer floor = scores.floor(73);
assertEquals(70, floor);
Integer ceiling = scores.ceiling(73);
assertEquals(85, ceiling);
SortedSet<Integer> mid = scores.subSet(70, true, 95, false);
assertEquals(List.of(70, 85), new ArrayList<>(mid));
}
The assertions verify a floor of 70 and a ceiling of 85 for the target 73. The subset includes 70 and excludes 95, so it contains 70 and 85.
5. Comparing HashSet and LinkedHashSet to TreeSet
Let’s compare the inheritance and interface relationships of the three Set implementations.
5.1. Class and Interface Relationships
The class diagram shows how the implementations share a base class and support different ordering interfaces:
To sum up the key points of the three main Set implementations:
- All three extend AbstractSet.
- LinkedHashSet and TreeSet both implement the SequencedSet interface, which provides methods such as getFirst() and getLast().
- TreeSet is unique in also implementing SortedSet and NavigableSet, which give it ordering and range-query capabilities.
Hash-based sets (HashSet and LinkedHashSet) offer constant-time basic operations when hashes are well distributed, but they don’t keep elements sorted. TreeSet uses logarithmic-time operations to maintain sorted order.
5.2. Comparing Iteration Orders
Let’s add a test to TreeSetUnitTest that inserts the same data into all three sets:
@Test
void whenComparingThreeSets_thenOrdersDiffer() {
List<String> data = List.of("es", "fr", "de");
Set<String> hash = new HashSet<>(data);
List<String> hashOrder = new ArrayList<>(hash);
LinkedHashSet<String> linked = new LinkedHashSet<>(data);
List<String> linkedOrder = new ArrayList<>(linked);
TreeSet<String> tree = new TreeSet<>(data);
List<String> treeOrder = new ArrayList<>(tree);
assertEquals(new HashSet<>(data), new HashSet<>(hashOrder));
assertEquals(data, linkedOrder);
assertNotEquals(linkedOrder, treeOrder);
assertEquals(List.of("de", "es", "fr"), treeOrder);
}
Here, the TreeSet produces elements in sorted order (de, es, fr).
The HashSet provides no ordering guarantee, so we check its membership without assuming an iteration order. Its order may happen to match either of the other sets. The LinkedHashSet preserves insertion order (es, fr, de), which differs from the sorted TreeSet order for this data.
6. Practical Use-Case Example: Live Leaderboard
A game leaderboard must stay sorted as scores change. Let’s use a TreeSet to accomplish this:
@Test
void whenBuildingLeaderboard_thenTopScoresDescend() {
TreeSet<Integer> scores = new TreeSet<>(List.of(68, 42, 73, 91, 55));
Iterator<Integer> it = scores.descendingIterator();
List<Integer> topThree = List.of(it.next(), it.next(), it.next());
assertEquals(List.of(91, 73, 68), topThree);
}
The scores set, combined with a descending iterator, lets us retrieve the top scores directly in descending order. This avoids the need for an additional sort step, since the set always maintains elements in sorted order.
7. Performance and Pitfalls
Like every other Java data structure, TreeSet comes with some weak points:
- Each insert or delete may trigger tree rebalancing. Avoid TreeSet for very write-heavy, order-insensitive data.
- A custom comparator must be consistent with equals(); otherwise, logically equal elements may appear as duplicates, or distinct elements may be treated as the same.
- TreeSet isn’t thread-safe.
- Don’t mutate fields used in comparison after insertion. Changing them can invalidate the tree’s ordering.
8. Choosing Among Set Implementations
Closing this lesson, let’s compare TreeSet with the other Java Set structures we’ve learned so far:
| Requirement | Best Choice | Typical Performance (lookup / insertion) | Notes |
|---|---|---|---|
| Pure uniqueness, no order | HashSet | Constant time when hashes are well distributed | No iteration-order guarantee |
| Uniqueness + insertion order | LinkedHashSet | Constant time when hashes are well distributed | Preserves insertion order using links between entries |
| Uniqueness + always-sorted order and ranges | TreeSet | Logarithmic time as the set grows | Supports sorted order and range queries |
Use a TreeSet when we need elements delivered in sorted order, nearest-element queries, or live range views. Choose a hash-based set when sorting and range queries are unnecessary.
9. Conclusion
In this lesson, we’ve explored TreeSet as a sorted Set implementation backed by a red-black tree. We’ve looked at how natural ordering and custom Comparator sorting determine element arrangement, and we’ve examined the range-view and nearest-element operations provided by the NavigableSet and SortedSet interfaces.
We’ve also compared TreeSet with HashSet and LinkedHashSet to understand where each implementation fits. While hash-based sets offer faster write performance, TreeSet is the right choice when sorted iteration, proximity queries, or live range views are required.