Java SortedSet and TreeSet Tutorial and Examples
- Details
- Written by Nam Ha Minh
- Last Updated on 16 June 2019   |   Print Email
In this tutorial, we help you understand deeper about TreeSet in the Java Collections Framework.
You know, TreeSet does not only implement the Set interface, it also implements the SortedSet and NavigableSet interfaces. Therefore, besides inheriting behaviors of a typical Set, TreeSet also inherits behaviors of SortedSet and NavigableSet. The following picture illustrates the API hierarchy:
1. Understanding SortedSet
The key characteristic of a SortedSet is that, it sorts elements according to their natural ordering or by a specified comparator. So considering using a TreeSet when you want a collection that satisfies the following conditions:
- Duplicate elements are not allowed.
- Elements are sorted by their natural ordering (default) or by a specified comparator.
Here’s an example illustrates this characteristic of a SortedSet:
SortedSet<Integer> setNumbers = new TreeSet<>(); setNumbers.addAll(Arrays.asList(2, 1, 4, 3, 6, 5, 8, 7, 0, 9)); System.out.println("Sorted Set: " + setNumbers);
Output:
Sorted Set: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Here, we add elements of an array list to a TreeSet, and as you can see, the duplicate elements are removed and they are sorted by alphanumeric order (natural ordering of numbers).
In addition to basic collection operations and normal set operations, the SortedSet provides the following types of operations:
- Range view: extracts a portion of the set, i.e. a range.
- Endpoints: returns the first and the last element in the sorted set.
- Comparator access: returns the comparator, if an, used to sort the set.
Hence the following interface abstracts a SortedSet:
public interface SortedSet<E> extends Set<E> { // Range-view SortedSet<E> subSet(E fromElement, E toElement); SortedSet<E> headSet(E toElement); SortedSet<E> tailSet(E fromElement); // Endpoints E first(); E last(); // Comparator access Comparator<? super E> comparator(); }
Let’s look at each type of operation in details.
Range view operations:
- subSet(E fromElement, E toElement): returns a sorted set which is a portion of the set whose elements range from fromElement, inclusive, to toElement, exclusive.
- headSet(E toElement): returns a sorted set which is a portion of the set whose elements are strictly less than toElement.
- tailSet(E fromElement): returns a sorted set which is a portion of the set whose elements are greater than or equal to fromElement.
Endpoint operations:
- first(): returns the first (lowest) element currently in the set.
- last(): returns the last (highest) element currently in the set.
Comparator access:
- comparator(): returns the comparator used to order the elements in the set, or null if this set uses the natural ordering of its elements.
2. SortedSet Code Examples
The following code example demonstrates how these operations work with a TreeSetimplementation:
SortedSet<Integer> setNumbers = new TreeSet<>(); setNumbers.addAll(Arrays.asList(2, 1, 4, 3, 6, 5, 8, 7, 0, 9)); System.out.println("Original Set: " + setNumbers); Integer first = setNumbers.first(); System.out.println("First element: " + first); Integer last = setNumbers.last(); System.out.println("Last element: " + last); SortedSet<Integer> subSet = setNumbers.subSet(3, 7); System.out.println("Sub Set: " + subSet); SortedSet<Integer> headSet = setNumbers.headSet(5); System.out.println("Head Set: " + headSet); SortedSet<Integer> tailSet = setNumbers.tailSet(5); System.out.println("Tail Set: " + tailSet); Comparator comparator = setNumbers.comparator(); System.out.println("Sorted by natural ordering? " + (comparator == null));
Output:
Original Set: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] First element: 0 Last element: 9 Sub Set: [3, 4, 5, 6] Head Set: [0, 1, 2, 3, 4] Tail Set: [5, 6, 7, 8, 9] Sorted by natural ordering? true
The following code snippet shows how to use a comparator:
class ZtoAComparator implements Comparator<String> { public int compare(String s1, String s2) { return s2.compareTo(s1); } } SortedSet<String> setStrings = new TreeSet<>(new ZtoAComparator()); setStrings.add("Banana"); setStrings.add("Apple"); setStrings.add("Grape"); setStrings.add("Lemon"); setStrings.add("Watermelon"); System.out.println(setStrings);
Output:
[Watermelon, Lemon, Grape, Banana, Apple]
As you see, the specified comparator sorts the elements into descending order.
If you use Java 8, use Lambda expression to simplify the comparator class like this:
SortedSet<String> setStrings = new TreeSet<>((s1, s2) -> s2.compareTo(s1));
Set API References:
Related Java Set Tutorials:
Other Java Collections Tutorials:
- Java List Collection Tutorial and Examples
- Java Map Collection Tutorial and Examples
- Java Queue Collection Tutorial and Examples
- 18 Java Collections and Generics Best Practices
- Understand equals and hashCode in Java
- Understand object ordering in Java
Comments