Java Reference ยท Collections
The TreeSet class
Reference for java.util.TreeSet: a sorted set backed by a red-black tree, natural ordering or a Comparator, and floor, ceiling and range views.
TreeSet<E> keeps its elements sorted at all times. It is backed by a red-black tree, so add, remove and contains take O(log n) time, and iteration returns elements in ascending order. Besides the normal Set methods it offers navigation: the smallest and largest element, the closest element below or above a value, and live range views.
Order comes from the elements' natural ordering (Comparable) or from a Comparator passed to the constructor. Whichever you use also defines what "duplicate" means: two elements that compare as 0 are treated as the same.
TreeSet<Integer> nums = new TreeSet<>(List.of(5, 1, 3)); // [1, 3, 5] TreeSet<String> byLength = new TreeSet<>(Comparator.comparing(String::length));
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.
Syntax
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable
| Constructor | Description |
|---|---|
TreeSet() |
Empty set using natural ordering. |
TreeSet(Comparator<? super E> c) |
Empty set using the comparator. |
TreeSet(Collection<? extends E> c) |
Natural ordering, filled from c. |
TreeSet(SortedSet<E> s) |
Same elements and same comparator as s. |
| Member | Description |
|---|---|
first(), last() |
Smallest and largest. Throw NoSuchElementException when empty. |
lower(e), floor(e), ceiling(e), higher(e) |
Neighbors of e: <, <=, >=, >. Return null if none. |
pollFirst(), pollLast() |
Remove and return an end; null when empty. |
headSet(to), tailSet(from), subSet(from, to) |
Live range views (variants take inclusive flags). |
descendingSet(), descendingIterator() |
Reverse order. |
Usage notes
- Complexity:
O(log n)foradd,remove,contains,floor,ceilingand the other navigation methods. Range views are created inO(log n). - Consistency with equals: the comparator decides duplicates, not
equals(). A comparator that ignores a field silently drops elements that differ in that field. - No null elements with natural ordering:
add(null)throwsNullPointerException. A custom comparator may acceptnull, but avoid it. - Elements must be mutually comparable, otherwise
ClassCastExceptionis thrown on insertion. - Views are live.
headSet,tailSetandsubSetreflect changes to the parent set, and inserting a value outside a view's range throwsIllegalArgumentException. - Not synchronized. For concurrent use consider
ConcurrentSkipListSet. - Do not mutate a field that takes part in the ordering after the element is inserted.
- Java 21 also gives
TreeSetthe sequenced methods (getFirst,reversed, ...).
Related
- Set, HashSet, TreeMap, Comparable
- Lessons: TreeMap and TreeSet, Choosing a collection