Thursday, March 15, 2018

TreeSet in Java With Examples

TreeSet in Java is also one of the implementation of the Set interface like HashSet and LinkedHashSet. TreeSet class implements the NavigableSet interface and extends the AbstractSet class.

Just like other implementations of the Set interface HashSet and LinkedHashSet, TreeSet also stores unique elements. How TreeSet in Java differs from other Set implementations is that TreeSet stores its elements in sorted order. The elements are ordered using their natural ordering or a comparator can be provided at set creation time to provide custom ordering (We'll see an example a little later).


How TreeSet is implemented in Java

TreeSet in Java uses a tree data structure to store its elements thus providing guaranteed log(n) time cost for the basic operations (add, remove and contains).

As we have seen while discussing HashSet and LinkedHashSet internally these implementations use their map counterparts i.e. HashMap and LinkedHashMap respectively. Same way TreeSet also uses TreeMap internally to store its elements.

Some of the important points about TreeSet in Java are as follows-
  • TreeSet only stores unique elements, no duplicates.
  • TreeSet stores its elements in sorted order. The elements are sorted as per their natural ordering or a Comparator can be provided at set creation time to provide custom ordering.
  • TreeSet doesn't allow null element to be added.
  • Internally TreeSet uses TreeMap to store its elements.
  • TreeSet implementation is not synchronized hence not thread safe. If TreeSet is to be used in a multi-threaded environment where it is accessed and modified concurrently then it must be synchronized externally. That can be done by wrapping the set with in Collections.synchronizedSet method.
  • The iterators returned by TreeSet 's iterator method are fail-fast: 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()- 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<E> s)- Constructs a new tree set containing the same elements and using the same ordering as the specified sorted set.

Java TreeSet creation example

This simple example shows how to create TreeSet in Java and insert elements in the TreeSet.

public class TreeSetDemo {

    public static void main(String[] args) {
        Set<String> citySet = new TreeSet<String>();
        
        citySet.add("Delhi");
        citySet.add("Mumbai");
        citySet.add("Bangalore");
        citySet.add("Delhi");
        citySet.add("Chennai");
        citySet.add("Hyderabad");
        
        // Iterating the Set
        for(String str : citySet){
            System.out.println("City Name - " + str);
        }
        
        Set<Integer> numberSet = new TreeSet<Integer>();
        numberSet.add(6);
        numberSet.add(76);
        numberSet.add(1);
        numberSet.add(45);
        numberSet.add(89);
        numberSet.add(8);
        
        // Iterating the Set
        for(Integer num : numberSet){
            System.out.println("Number - " + num);
        }
    }
}

Output

City Name - Bangalore
City Name - Chennai
City Name - Delhi
City Name - Hyderabad
City Name - Mumbai
Number - 1
Number - 6
Number - 8
Number - 45
Number - 76
Number - 89

Here I have created 2 TreeSets, one stores Strings and another Integers. It can be seen that the TreeSet sorts the elements using their natural ordering which is ascending for both String and Integer. Also note that though Delhi is added twice but it is stored only once, so uniqueness is maintained.

TreeSet in Java doesn't allow null

Though HashSet and LinkedHashSet allow one null, TreeSet doesn't allow null as element. Any attempt to add null in a TreeSet will result in a NullPointerException.

public class TreeSetDemo {

    public static void main(String[] args) {
        Set<String> citySet = new TreeSet<String>();
        
        citySet.add("Delhi");
        citySet.add("Mumbai");
        citySet.add(null);
        citySet.add("Delhi");
        citySet.add("Chennai");
        citySet.add("Hyderabad");
        
        // Iterating the Set
        for(String str : citySet){
            System.out.println("City Name - " + str);
        }
    }
}

Output

Exception in thread "main" java.lang.NullPointerException
 at java.util.TreeMap.put(Unknown Source)
 at java.util.TreeSet.add(Unknown Source)
 at org.netjs.prog.TreeSetDemo.main(TreeSetDemo.java:14)

Sorting elements in different order in TreeSet

As already mentioned elements are stored using natural ordering in TreeSet by default. If you want to sort using different order then you need to provide your own comparator at set creation time. Let's see an example where we sort the Strings in descending order.

public class TreeSetDemo {

    public static void main(String[] args) {
        // Providing custom compartor
        Set<String> citySet = new TreeSet<String>(new CityComparator());
        
        citySet.add("Delhi");
        citySet.add("Mumbai");
        citySet.add("Bangalore");
        citySet.add("Chennai");
        citySet.add("Hyderabad");
        
        // Iterating the Set
        for(String str : citySet){
            System.out.println("City Name - " + str);
        }
    }
}

// Comparator class
class CityComparator implements Comparator<String>{
    @Override
    public int compare(String str1, String str2) {
        return str2.compareTo(str1);
    }    
}

Output

City Name - Mumbai
City Name - Hyderabad
City Name - Delhi
City Name - Chennai
City Name - Bangalore

Here note that a comparator is provided which reverses the sorting order. That comparator is provided at the set creation time in a constructor.

TreeSet navigation examples

TreeSet in Java implements the NavigableSet interface which means TreeSet class has navigation methods reporting closest matches for given search targets.

This example shows the usage of some of these navigation methods.
  • 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.
  • 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.
  • lower(E e)- Returns the greatest element in this set strictly less than the given element, or null if there is no such element.
public class TreeSetNavigation {

    public static void main(String[] args) {
        NavigableSet<Integer> numberSet = new TreeSet<Integer>();
        numberSet.add(6);
        numberSet.add(76);
        numberSet.add(1);
        numberSet.add(45);
        numberSet.add(89);
        numberSet.add(8);
        
        System.out.println("Nearest value greater than 70 in the Set- " 
              + numberSet.ceiling(70));        
        System.out.println("Nearest value less than 50 in the Set- " 
              + numberSet.floor(50));        
        System.out.println("Nearest value greater than 76 in the Set- " 
              + numberSet.higher(76));        
        System.out.println("Nearest value less than 8 in the Set- " 
              + numberSet.lower(8));
    }
}

Output

Nearest value greater than 70 in the Set- 76
Nearest value less than 50 in the Set- 45
Nearest value greater than 76 in the Set- 89
Nearest value less than 8 in the Set- 6

TreeSet is not synchronized

TreeSet in Java is not thread safe. In case we need to Synchronize it, it should be synchronized externally. That can be done using the Collections.synchronizedSortedSet method.

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

TreeSet class's iterator is fail-fast

The iterator returned by TreeSet is fail-fast, 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 will throw a ConcurrentModificationException.

That's all for this topic TreeSet in Java With Examples. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. HashSet Vs LinkedHashSet Vs TreeSet in Java
  2. How HashSet Works Internally in Java
  3. EnumSet in Java
  4. How to Sort HashSet in Java
  5. Java Collections Interview Questions

You may also like-

  1. How HashMap Internally Works in Java
  2. Fail-Fast Vs Fail-Safe Iterator in Java
  3. Difference between ArrayList and LinkedList in Java
  4. ConcurrentSkipListSet in Java
  5. Difference Between Checked & Unchecked Exception in Java
  6. Lambda expression examples in Java 8
  7. finalize method in Java
  8. What is Dependency Injection in Spring

No comments:

Post a Comment