TreeSet Class in Java With Program Example

TreeSet is an implementation class of NavigableSet interface which is a child interface of SortedSet. It is a class in the collection framework that stores and manipulates elements in some sorting order. It represents self-balancing binary tree as its underlying data structure which makes it a good choice for search and retrieving operations.

Syntax:

Set<T> set = new TreeSet<T>();

It stores elements in natural sorting order using compareTo() method of Comparable interface. It also allows custom sorting order with the help of compare() method of Comparator interface.

It provides various methods that are inherited from Navigable,SortedSet and Set interface.

Point to remember:

1. It uses self balancing tree as its underlying data structure
2. It doesn’t allow Duplicate elements

3. It doesn’t preserve insertion order

4. It stores data in some sorting order
5. Only comparable or same type of elements are allowed

6. It is not thread safe

7. It provides non synchronised implementation of Set

TreeSet an implementation of Binary Search Tree

TreeSet class uses self balancing binary search tree as its underlying data structure which makes it one of the efficient implementations for storing large data set in ordered manner. It takes logarithmic average and worst case time when it comes to perform basic operations such as add, delete and search.

TreeSet is not Thread Safe

It is also important to know that TreeSet provides non synchornized implementation which allow multiple threads to access a tree set object concurrently. It can lead to uncertain behaviour as more than one threads can operate on that object at the same time. It is possible to make a tree set synchronized. With the help of Collection.synchronizedSortedSet() method we can encapsulate a set in a synchronized object or wrapper.

Syntax :

Set<T> treeSet = new TreeSet<>();
Set synchronized = Collections.synchronziedSet(treeSet);

TreeSet NULL Acceptance

If  a treeSet is non empty Set, then by default we are going to get null pointer exception while trying to insert null value. It occurs because of the comparison with other elements.

For empty TreeSet, null value can be accepted

Constructors of TreeSet Class

There are four constructors support by TreeSet class.

1) TreeSet()

A default constructor that creates an empty tree set object with default natural sorting order

TreeSet<T> t = new TreeSet<T>()

2) TreeSet(Comparator c)

It creates an empty tree set instance with custom specified order defined using Comparator .

TreeSet<T> t = new TreeSet(Comparator c);

3) TreeSet(Collection obj)

It creates a tree set instance with the elements present in the collection object and order them in nature order.

TreeSet<T> t = new TreeSet<>(Collection obj)

4) TreeSet(SortedSet obj)

Similar to previous constructor, the constructor accepts a collection object which is in this case, is SortedSet and creates an tree set instance with all the elements present in that collection in natural order.

TreeSet<T> t = new TreeSet<T>(Sorted obj)

Methods of TreeSet Class

Comparable Interface Vs Comparator Interface

If the empty tree set is created with default constructor, then the elements should be of same type and comparable, otherwise, ClassCastingException would be triggered by the Java compiler. Objects that implements Comparable interface are called comparable.

Comparable Interface

• It resides in Java.lang package
• It contains only single method, named compareTo()
• It returns int value, as it decides whether an element, greater, equal or smaller than other

obj1.compareTo(obj 2)

1. -ve obj1 should come before obj2
2. +ve obj1 should come after obj2
3. 0 both obj1 and obj2 are equal

Comparator Interface

If a custom implementation is required, we can use Comparator, not Comparable.

• It is used for customised sorting order
• It resides in Java.util packages
• It contains 2 methods, compare() and equals()
• compare() also returns int.
• It uses same comparison approach as compareTo() method
• It is compulsory to provide implementation of compare method but, equals() implementation is optional as it’s root class method
• Using Comparator, we can use non comparable objects in tree set

A tree set can have duplicate elements if we use Comparator to implement the sorting or insertion changes.

Java Program to arrange and print elements of TreeSet in descending order with the help of Comparator

Program:

import java.util.*;

public class SetExample implements Comparator<Integer>{
    public static void main(String[] args) {

        Set<Integer> treeSet = new TreeSet<>(new SetExample()); // creating a treeSet instance that holds integers

        // Adding elements to linked hash set
        treeSet.add(5);
        treeSet.add(1);

        treeSet.add(2);
        treeSet.add(100);
        treeSet.add(101);


        // Iterating using for each

        Iterator iterator = treeSet.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }

    }
    
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
}

Output:

101
100
5
2
1