TreeSet in Java is also one of the implementation of the Set interface like HashSet and LinkedHashSet. TreeSet 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 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
You may also like-
No comments:
Post a Comment