It is based on TreeMap, the main different is that TreeSet is an implementation of Set interface and TreeMap on Map interface.

This kind of collection sorts your entries just when they are inserted. No need to call sort().

The elements are ordered using their natural ordering, or by a Comparator class provided at set creation time, depending on which constructor is used. An example of use is as follows:

Collection<String> userNames = newTreeSet<String>(Collator.getInstance());
It is important to note that in contrats to a Set where the ordering is defined in terms of the equals operation (whether or not an explicit comparator is provided), the TreeSet instance performs all element comparisons using its compareTo (or compare) method.

1. Time complexity

Provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

  average / worst case
space O(n)
contains O(log n)
add O(log n)
remove O(log n)


2. Advantages

  • It is cleaner to implement.
  • It is always sorted.
  • You cannot have duplicate entries. If you need duplicates, change to a List.
  • So much information in a short declaration, TreeSet<String> : this is a sorted collection of Strings without duplicates, and I can be sure that this is true at every moment.
  • Real performance, in principle, is faster than to insert all elements in a List and next sort them from scratch. The tree insert has a time complexity of O(log(n)), leading to overall O(n*log(n)) (quick or merge sort algorithms). Comparing with other classes:


    • TreeSet keeps things in object comparison order. The key is defined by the Comparable interface. TreeSet Implements SortedSet interface that extends Set interface which extends the Collection interface.

    • LinkedList keeps things in the insertion order. LinkedList Implements List and Queue interfaces that both of them extends the Collection interface.

    • ArrayList uses more memory, is faster for some operations. ArrayList implements the List interface that extends Collection.

    • TreeMap, similarly, removes the need to sort by a key. The map is built in key order during the inserts and maintained in sorted order at all times. TreeMap implements SortedMap that extends the Map interface.


    Highlight that the Java implementation of TreeSet is a quite bit slower than using an ArrayList and sort.

3. Not synchronized

It is not synchronized. If multiple threads access a tree set concurrently, and at least one of the threads modifies the set, it must be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the set. If no such object exists, the set should be "wrapped" using the Collections.synchronizedSortedSet method. This is best done at creation time, to prevent accidental unsynchronized access to the set:

   SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));

The iterators returned by this class's iterator method are fail-fast: if the set is modified at any time after the iterator is created, except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException on a best-effort basis Thus, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

The fail-fast behavior of iterators should be used only to detect bugs.Therefore, it would be wrong to write a program that depended on this exception for its correctness. This is so because it is impossible to make any hard guarantees in the presence of unsynchronized concurrent modification.

Remember that in order to write short and bug free code, we have to use the right collection for the right task.

Please, feel free to give me your comments :)


Pin It

Add comment