• ← Previous
• Next →

A SortedSet interface is one of the widely used Collection interfaces. As shown in the below figure, TreeSet is the implementation class of the SortedSet interface (and also NavigableSorted set, which extends SortedSet). It is highly recommended that one should go through SortedSet Interface and NavigableSet Interface. before getting into the details of the TreeSet class.

Figure: TreeSet Class

The TreeSet class implements all the methods defined in SortedSet and NavigableSet interfaces and it does not provide any other extra methods. A TreeSet uses a Balanced binary Tree as its underlying data structure. A Balanced Binary Tree is a very popular data structure where the operations like add, remove, find etc can be done in log(n) time.

A TreeSet inherits all the basic properties of a Set and a SortedSet. Accordingly, a TreeSet cannot have duplicate elements; this means a TreeSet cannot have 2 objects say, obj1 and obj2 where obj1.equals(obj2) is true; In addition, all the elements of a TreeSet are in Sorted order, by default all the elements of a TreeSet are ordered using their Natural Ordering. But, TreeSet also provides an option of using a Comparator, where an application has the control over the sorting order and it can be changed. Lastly,, a TreeSet cannot have heterogeneous element, we will see more about this in the below example program.

TreeSet Class Constructors

TreeSet class provides four Constructors and, the following table lists them.

Here is an Example program, that demonstrates the usage of all the above mentioned operations.

 import java.util.ArrayList;
 import java.util.Comparator;
 import java.util.TreeSet;

 class ComparatorClassDemo implements Comparator {
     @Override
     public int compare(Object arg0, Object arg1) {
         Integer x = (Integer) arg0;
         Integer y = (Integer) arg1;
         if (x < y)
             return 1;
         else if (x > y)
             return -1;
         else
             return 0;
     }
 }

 public class TreeSetDemo {
     public static void main(String[] args) {
         ArrayList alistObj = new ArrayList();
         alistObj.add(34);
         alistObj.add(34);
         alistObj.add(23);
         //alistObj.add("Mike");

         TreeSet tsetObj1 = new TreeSet();
         TreeSet tsetObj2 = new TreeSet(new ComparatorClassDemo());
         TreeSet tsetObj3 = new TreeSet(alistObj);

         tsetObj1.add(4);
         tsetObj1.add(24);
         tsetObj1.add(13);

         tsetObj2.add(4);
         tsetObj2.add(24);
         tsetObj2.add(13);

         System.out.println (" TreeSet1: " + tsetObj1);
         System.out.println (" TreeSet2: " + tsetObj2);
         System.out.println (" TreeSet3: " + tsetObj3);

         System.out.println(" Comparator Object: " + tsetObj2.comparator()
                            + ", Default Object (Comparable): " 
                            + tsetObj1.comparator());
     }
 }

The above program demonstrates quite a few important properties of the TreeSet. Notice the output below, all the elements of the set are in sorted order. This is the basic difference between a Set vs TreeSet. The first TreeSet represented by the object "tsetObj1" is created by the default constructor, and it sorts the elements using the Natural Ordering (Ascending order is the default natural order).

Another important property of a TreeSet is demonstrated, if you notice the object, "tsetObj2", the elements of this TreeSet is sorted using a Comparator. A comparator object of class "ComparatorClassDemo" is passed as an argument, hence all the elements of TreeSet represented by the object "tsetObj2" are sorted in descending order(The logic defined by the comparator) and NOT the Natural order. The "ComparatorClassDemo" class implemented a Comparator and hence overrides the method "compare", hence all the elements that are inserted into the tsetObj2 are compared using "compare()" method as opposed to the default "compareTo()" method defined by the Comparable Interface..

The third TreeSet is created from the Collection object passed to the Constructor. In the above example, "TreeSet tsetObj3 = new TreeSet(alistObj);", alistObj is an ArrayList, and as we know an ArrayList can have duplicate elements. (Get familiar with ArrayList here, Understanding ArrayList Now as you can see in the below output, newly created TreeSet, "tsetObj3" does not have duplicate elements, as a Set does not allow duplicate elements. If you notice, "alistObj.add("Mike");" this statement has been commented out in the above example program, this is because a TreeSet cannot have "Heterogeneous Elements", this is because recollect the property of a SortedSet, All the elements in a SortedSet must be mutually comparable, which implies, element1.compareTo(element2) or comparator.compare(element1, element2) must not throw "ClassCastException". That statement make perfect sense for an ArrayList but not for a TreeSet.

The last statement in the program demonstrates the usage of the "Comparator" method.

Let us Compile/run the program, Here is the output:

  TreeSet1: [4, 13, 24]
  TreeSet2: [24, 13, 4]
  TreeSet3: [23, 34]
  Comparator Object: ComparatorClassDemo@23a65a18, Default Object (Comparable): null

Clone Operation on the TreeSet

TreeSet interface provides an other important operation called "clone" , where one can get to make a shallow copy of the TreeSet. So, what a shallow copy mean ? It means the elements of the TreeSet are not copied, it just just creates an instance of the TreeSet. A change made using one object, gets reflected to the other object. Basically, if you are familiar with "C" programming it like 2 pointers to the same variable, where the pointer points to the address of a variable and changes made to the variable at that address will be seen by all the pointers pointing to that address.

An example program demonstrating the concept of "Clone" method is available in ArrayList Class. The concept of "Clone" is same, be it an ArrayList or HashSet or a TreeSet.

• ← Previous
• Next →