Java TreeSet class

TreeSet class hierarchy

Java TreeSet class implements the Set interface that uses a tree for storage. It inherits AbstractSet class and implements the NavigableSet interface. The objects of the TreeSet class are stored in ascending order.

The important points about Java TreeSet class are:

  • Java TreeSet class contains unique elements only like HashSet.
  • Java TreeSet class access and retrieval times are quiet fast.
  • Java TreeSet class doesn’t allow null element.
  • Java TreeSet class is non synchronized.
  • Java TreeSet class maintains ascending order.

What is TreeSet ?

TreeSet is like HashSet which contains the unique elements only but in a sorted manner. The major difference is that TreeSet provides a total ordering of the elements. The elements are ordered using their natural ordering, or by a Comparator typically provided at sorted set creation time. The set’s iterator will traverse the set in ascending element order.

How TreeSet works in Java ?

If you look into the TreeSet Api in rt.jar , you will find the following code :

    
  public class TreeSet<E>
              extends AbstractSet<E>
              implements NavigableSet<E>, Cloneable, java.io.Serializable

{
    private transient NavigableMap<E,Object> map;
    
    // Dummy value to associate with an Object in the backing Map
    
    private static final Object PRESENT = new Object();
    
    
    
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }
    
    // SOME CODE ,i.e Other methods in TreeSet
    
    
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }   

    // SOME CODE ,i.e Other methods in TreeSet

}

According to TreeSet Oracle doc :

TreeSet is a NavigableSet implementation backed by TreeMap instance. 


Hence , whenever you are adding element to the TreeSet object , it works just like HashSet , The only difference is that instead of HashMap here we have TreeMap object in the constructor.

As we know in TreeMap each key is unique as it internally uses HashMap . So what we do in the TreeSet is that we pass the argument in the add(Elemene E) that is E as a key in the TreeSet . Now we need to associate some value to the key , so what Java apis developer did is to pass the Dummy  value that is ( new Object () ) which is referred by Object reference PRESENT .

So , actually when you are adding a line in TreeSet like  treeset.add(3)   what java does internally is that it will put that element E here 3 as a key in the TreeMap(created during TreeSet object creation) and some dummy value that is Object’s object is passed as a value to the key .

Now if you see the code of the TreeMap put(Key k,Value V) method , you will find something like this

 public V put(K key, V value) {
//Some code
}

The main point to notice in above code is that put (key,value) will return

1.  null , if key is unique and added to the map
2.  Old Value of the key , if key is duplicate

So , in TreeSet add() method ,  we check the return value of map.put(key,value) method with null value
i.e.

   public boolean add(E e) {
            return map.put(e, PRESENT)==null;
       }

So , if map.put(key,value) returns null ,then
map.put(e, PRESENT)==null      will return true and element is added to the TreeSet.

So , if map.put(key,value) returns old value of the key ,then
map.put(e, PRESENT)==null      will return false and element is  not added to the TreeSet 

What is the runtime performance of the add() method of the TreeSet and HashSet , where n represents the number of elements?

According to TreeSet Oracle doc :

TreeSet implementation provides guaranteed log(n) time cost for the basic operations (add, remove
and contains ) method.

According to HashSet Oracle doc :

HashSet provides constant time performance O(1) for basic operations  (add, remove and contains) method assuming the hash  function disperses the elements properly among the buckets.
One-liner :                TreeSet : O(log(n))  HashSet : O(1)

What is natural ordering in TreeSet ?

“Natural” ordering is the ordering implied by the implementation of Comparable interface by the objects in the TreeSet . Essentially RBTree must be able to tell which object is smaller than other object , and there are two  ways to supply that logic to the RB Tree implementation :

1. We need to implement the Comparable interface in the class(es) used as objects in TreeSet.
2. Supply an implementation of the Comparator would do comparing outside the class itself.

50% LikesVS
50% Dislikes

Leave a Reply

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