TreeSet

In short: A Set implementation that keeps its elements automatically sorted — internally via a balanced binary tree (red-black tree).

In more detail: Sorting happens either via the natural order (the element has to implement Comparable) or via a Comparator passed at creation. Inserting/removing/searching is somewhat slower for TreeSet with logarithmic instead of constant time compared to HashSet, but the order is always guaranteed to be predictable.

In Depth

// Natural order (String already implements Comparable itself):
TreeSet<String> names = new TreeSet<>();
names.add("Bob");
names.add("Anna");
names.add("Carl");
System.out.println(names); // [Anna, Bob, Carl] - always sorted
 
// Custom order via Comparator, e.g. descending:
TreeSet<Integer> numbers = new TreeSet<>(Comparator.reverseOrder());
numbers.add(5);
numbers.add(1);
numbers.add(3);
System.out.println(numbers); // [5, 3, 1]
 
System.out.println(names.first()); // "Anna" - smallest element
System.out.println(names.last());  // "Carl" - largest element

Internally, TreeSet manages its elements in a red-black tree (a self-balancing variant of a binary tree), which guarantees that inserting, deleting, and searching always run in logarithmic time (O(log n)), no matter in which order elements were inserted. The tree automatically stays balanced, instead of degenerating into a degenerate, list-like structure for certain insertion orders.

Objects meant to end up in a TreeSet either have to implement Comparable<T> themselves (defines a “natural” default order, as already given for String or Integer) or a Comparator has to be passed at creation — without either of the two, TreeSet throws a ClassCastException on the first insertion attempt, because it has no way to compare two elements. Besides the normal Set operations, TreeSet offers handy additional methods thanks to the guaranteed sorting, like first(), last(), headSet(x) (all elements smaller than x), and higher(x) (the next-larger element after x).

See also: HashSet, Set, Sorting