TreeSet in Java – The Sorted Set

TreeSet in Java is one of the implementation of the Set interface. How it differs from the other popular implementation HashSet is that unlike HashSet which is unordered, TreeSet stores its element in sorted order.

The elements in TreeSet are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used to create the TreeSet.

TreeSet implementation in Java

If you have idea about the HashSet Internal Implementation in Java then you must be knowing that internally HashSet uses HashMap to store its element. Same way TreeSet internally uses TreeMap.
TreeSet in Java is a NavigableSet implementation based on a TreeMap.

Features of TreeSet in Java

Some of the features of the TreeSet which are discussed in this post are as follows-

  1. TreeSet stores only unique elements like other Set implementations.
  2. TreeSet stores its element in sorted order.
  3. Null elements are not permitted in TreeSet.
  4. TreeSet is not thread-safe.
  5. The iterators returned by the iterator method of the TreeSet class are fail-fast. Which means, if the set is modified at any time after the iterator is created, in any way except through the iterator’s own remove method, the Iterator throws a ConcurrentModificationException.

Java TreeSet constructors

TreeSet class in Java has 4 constructors.

  • TreeSet()– Constructs a new, empty tree set, sorted according to the natural ordering of its elements.
  • TreeSet(Collection<? extends E> c)– Constructs a new tree set containing the elements in the specified collection, sorted according to the natural ordering of its elements.
  • TreeSet(Comparator<? super E> comparator)– Constructs a new, empty tree set, sorted according to the specified comparator.
  • TreeSet(SortedSet s)– Constructs a new tree set containing the same elements and using the same ordering as the specified sorted set.

Java example creating a TreeSet

This example shows how TreeSet is created and elements added to it.

Output

As you can see from the output elements are sorted as per the natural ordering for the Strings which is ascending. Also duplicate element is added only once.

No nulls in TreeSet

Though other Set implementations like HashSet and LinkedHashSet allow adding null as element, TreeSet in Java doesn’t allow null. It will throw NullPointerExcpetion of there is an attempt to add null.

Output

Methods in Java TreeSet class

Some of the methods of the TreeSet class in Java.

  • ceiling(E e)– Returns the least element in this set greater than or equal to the given element, or null if there is no such element.
  • descendingIterator()– Returns an iterator over the elements in this set in descending order.
  • descendingSet()– Returns a reverse order view of the elements contained in this set.
  • floor(E e)– Returns the greatest element in this set less than or equal to the given element, or null if there is no such element.
  • higher(E e)– Returns the least element in this set strictly greater than the given element, or null if there is no such element.
  • tailSet(E fromElement)– Returns a view of the portion of this set whose elements are greater than or equal to fromElement.
  • tailSet(E fromElement, boolean inclusive)– Returns a view of the portion of this set whose elements are greater than (or equal to, if inclusive is true) fromElement.

Sorting TreeSet elements in different order using Comparator

You can provide your own Comparator, if you want any other ordering than natural ordering.

Output

Here constructor of TreeSet is used that takes Comparator as argument and a Comparator is implemented as a Lambda expression to reverse the sort order.

TreeSet is not thread-safe

TreeSet in Java is not thread safe as it is not synchronized. If multiple threads access a TreeSet concurrently, and at least one of the threads modifies the set structurally, it must be synchronized externally. You can wrap your TreeSet using the Collections.synchronizedSortedSet() method.

Performance of TreeSet

Since TreeSet is a tree based implementation so provides guaranteed log(n) time cost for the basic operations (add, remove and contains). But it is slower than the other implementations HashSet and LinkedHashSet because of the added functionality of keeping the elements sorted.

For differences among the HashSet, LinkedHashSet and TreeSet refer this post- HashSet Vs LinkedHashSet Vs TreeSet in Java

That’s all for the topic TreeSet in Java – The Sorted Set. If something is missing or you have something to share about the topic please write a comment.


You may also like

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.