TreeSet in Java | Methods, Example
A TreeSet in Java is another important implementation of the Set interface that is similar to the HashSet class, with one added improvement. It sorts elements in ascending order while HashSet does not maintain any order.
Java TreeSet implements SortedSet interface. It is a collection for storing a set of unique elements (objects) according to their natural ordering.
It creates a sorted collection that uses a tree structure for the storage of elements or objects. In simple words, elements are kept in sorted, ascending order in the tree set. For example, a set of books might be kept by height or alphabetically by title and author.
In Java TreeSet, access and retrieval of elements are quite fast because of using tree structure. Therefore, TreeSet is an excellent choice for quick and fast access to large amounts of sorted data.
The only restriction with using tree set is that we cannot add duplicate elements in the tree set.
TreeSet Class Declaration in Java
TreeSet is a generic class that is declared as:
class TreeSet<T>
In this syntax, T defines the type of objects or elements that the set will hold.
Hierarchy of TreeSet Class in Java
TreeSet class extends AbstractSet and implements NavigableSet interface. NavigableSet extends SortedSet to provide navigation methods.
Features of TreeSet class in Java
There are several important features of TreeSet class in java that must be kept in mind. They are as:
1. Java TreeSet contains unique elements similar to the HashSet. It does not allow the addition of a duplicate element.
[adinserter block=”5″]
2. The access and retrieval times are quite fast.
3. TreeSet does not allow inserting null element.
4. TreeSet class is non-synchronized. That means it is not thread-safe.
5. TreeSet maintains the ascending order. When we add elements into the collection in any order, the values are automatically presented in sorted, ascending order.
6. Java TreeSet internally uses a TreeMap for storing elements.
How to create TreeSet in Java?
TreeSet has the following constructors. We can create a TreeSet instance by using one of its four constructors.
1. TreeSet( ): This default constructor creates an empty TreeSet that will be sorted in ascending order according to the natural order of its elements.
2. TreeSet(Collection c): It creates a tree set and adds the elements from a collection c according to the natural ordering of its elements. All the elements added into the new set must implement Comparable interface.
If collection c’s elements do not implement Comparable interface or are not mutually comparable, this constructor throws ClassCastException.
If collection c contains null reference, this constructor throws NullPointerException.
3. TreeSet(Comparator comp): This constructor creates an empty tree set that will be sorted according to the comparator specified by comp.
All elements in the tree set are compared mutually by the specified comparator. A comparator is an interface that is used to implement the ordering of data.
4. TreeSet(SortedSet s): This constructor creates a tree set that contains the elements of sorted set s.
Important TreeSet Methods in Java
TreeSet class in java provides a variety of methods to perform different tasks. They are as follows:
1. boolean add(Object o): This method is used to add the specified element to this set if it is not already present.
2. boolean addAll(Collection c): This method is used to add all the elements of the specified collection to the set.
3. void clear(): It is used to remove all the elements from the set.
4. boolean isEmpty(): This method is used to check that the set has elements or not. It returns true if the set contains no elements otherwise returns false.
5. boolean remove(Object o): This method is used to remove the specified element from the set if it is present.
6. boolean contains(Object o): It returns true if the set has the specified element otherwise returns false.
7. int size(): This method is used to get the total number of elements in the set.
8. Iterator iterator(): The iterator() method is used to iterate the elements in ascending order.
[adinserter block=”2″]
9. Spliterator spliterator(): The splititerator() method is used to create a late-binding and fail-fast spliterator over the elements in the tree set.
10. Object clone(): The clone() method is used to get a shallow copy of this TreeSet instance.
11. Iterator descendingIterator(): It is used to iterate the elements in descending order.
Important Methods Defined by SortedSet Interface
Since Java TreeSet implements SortedSet interface, all the methods defined by SortedSet interface can be used while using TreeSet class. They are as:
1. Object first(): It is used to get the first (lowest) element currently in the sorted set.
2. Object last(): This method returns the last (highest) element currently in the sorted set.
3. Comparator comparator(): It returns comparator that is used to order elements in the set. If the TreeSet uses the natural ordering, this method returns null.
4. SortedSet headSet(Object toObject): This method returns the collection of elements that are less than the specified element.
5. SortedSet subSet(Object fromElement, Object toElement): It returns elements from the set that lie between the given range in which fromElement is included and toElement is excluded.
6. SortedSet tailSet(Object fromElement): It returns elements from the set that is greater than or equal to the specified element.
Important Methods Defined by NavigableSet Interface
Since Java TreeSet Class implements NavigableSet interface, therefore, all methods of this interface can be used while using tree set class. They are as:
1. Object ceiling(Object o): It returns the lowest element from the set equal to or greater than the specified element. If no such element is found, it returns null.
2. Object floor(Object o): It returns the greatest element from the set equal to or less than the specified element. If no such element is found, it returns null element.
3. Object lower(Object o): This method returns the largest element from the set strictly less than the specified element. If no such element is found, it will return null element.
4. Object higher(Object o): This method returns the smallest element from the set strictly greater than the specified element. If no such element is found, it will return null element.
5. Object pollFirst(): It is used to remove and retrieve the first element in the tree set.
6. Object pollLast(): It is used to remove and retrieve the last element in the tree set.
7. NavigableSet descendingSet(): This method returns elements in reverse order.
8. NavigableSet headSet(Object toObject, boolean inclusive): This method returns the collection of elements that are less than or equal to (if, inclusive is true) the specified element.
9. NavigableSet subSet(Object fromElement, boolean fromInclusive, Object toElement, boolean toInclusive): This method returns elements from the set that lie between the specified range.
10. NavigableSet tailSet(Object fromElement, boolean inclusive): It returns elements from the set that is greater than or equal to (if, inclusive is true) the specified element.
Java TreeSet Example Program
Let’s take some important example programs based on the above methods defined by TreeSet, SortedSet, and NavigableSet.
Let’s write a Java program to perform different operations such as adding, checking the size of TreeSet, and the set is empty or not. Look at the source code to understand better.
Program code 1:
import java.util.Set;
import java.util.TreeSet;
public class TreeSetEx1 {
public static void main(String[] args)
{
// Create a tree set.
Set<String> ts = new TreeSet<>();
// Check Set is empty or not.
boolean empty = ts.isEmpty();
System.out.println("Is TreeSet empty: " +empty);
// Checking the size of TreeSet before adding elements into it.
int size = ts.size();
System.out.println("Size of TreeSet: " +size);
// Adding elements into TreeSet.
ts.add("India"); // ts.size() is 1.
ts.add("USA"); // ts.size() is 2.
ts.add("Australia"); // ts.size() is 3.
ts.add("New zealand"); // ts.size() is 4.
ts.add("Switzerland"); // ts.size() is 5.
System.out.println("Sorted TreeSet: " +ts);
int size2 = ts.size();
System.out.println("Size of TreeSet after adding elements: " +size2);
}
}Output:
Is TreeSet empty: true
Size of TreeSet: 0
Sorted TreeSet: [Australia, India, New zealand, Switzerland, USA]
Size of TreeSet after adding elements: 5
Let’s take an example program where we will perform operations like removing an element and checking of a specific element.
Program code 2:
import java.util.TreeSet;
public class TreeSetEx2 {
public static void main(String[] args)
{
// Creating an TreeSet object of type String.
TreeSet<String> ts = new TreeSet<>();
// Adding string objects to tree set.
ts.add("India");
ts.add("USA");
ts.add("Australia");
ts.add("New zealand");
ts.add("Switzerland");
// Checking for a specific element in set.
boolean element = ts.contains("USA");
System.out.println("Is USA in TreeSet: " +element);
// Removing element from the tree set.
ts.remove("New zealand");
System.out.println("Sorted tree set: " +ts);
ts.clear();
System.out.println("Elements in tree set: " +ts);
}
}Output:
Is USA in TreeSet: true
Elements in tree set: [Australia, India, Switzerland, USA]
Elements in tree set: []
Let’s take an example program to perform different operations based on methods defined by the SortedSet interface. Look at the source code.
Program code 3:
import java.util.HashSet;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;
public class TreeSetEx3 {
public static void main(String[] args)
{
// Creating a set object and adding elements to it.
Set<String> s = new HashSet<>();
s.add("Delhi");
s.add("New York");
s.add("Paris");
s.add("London");
s.add("Delhi"); // Adding duplicate elements.
TreeSet<String> ts = new TreeSet<>(s);
System.out.println("Sorted TreeSet: " +ts);
// Using methods of SortedSet interface.
System.out.println("First Element: " +ts.first());
System.out.println("Last Element: " +ts.last());
System.out.println("HeadSet Elements: " +ts.headSet("London"));
System.out.println("TailSet Elements: " +ts.tailSet("London"));
SortedSet<String> subSet = ts.subSet("Delhi", "Paris");
System.out.println("SubSet Elements: " +subSet);
System.out.println("Sorted Set: " +ts.comparator()); // It will return null because natural ordering is used.
}
}Output:
Sorted TreeSet: [Delhi, London, New York, Paris]
First Element: Delhi
Last Element: Paris
HeadSet Elements: [Delhi]
TailSet Elements: [London, New York, Paris]
SubSet Elements: [Delhi, London, New York]
Sorted Set: nullLet’s take an example program where we will perform operations based on NavigableSet interface methods.
Program code 4:
import java.util.TreeSet;
public class TreeSetEx4 {
public static void main(String[] args)
{
// Creating TreeSet object and adding elements to it.
TreeSet<Integer> ts = new TreeSet<>();
ts.add(25);
ts.add(80);
ts.add(05);
ts.add(100);
ts.add(90);
ts.add(200);
ts.add(300);
System.out.println("Sorted TreeSet: " +ts);
// Using methods of NavigableSet interface.
System.out.println("Largest element less than 100: " +ts.lower(100));
System.out.println("Smallest element greater than 100: " +ts.higher(100));
System.out.println("Floor: " +ts.floor(85));
System.out.println("Ceiling: " +ts.ceiling(10));
System.out.println(ts.pollFirst()); // Remove and retrieve the first element from the set.
System.out.println(ts.pollLast()); // Remove and retrieve the last element from the set.
System.out.println("New Treeset: " +ts);
System.out.println("HeadSet: " +ts.headSet(90,true));
System.out.println("SubSet: " +ts.subSet(90, true, 200, true));
}
}Output:
Sorted TreeSet: [5, 25, 80, 90, 100, 200, 300]
Largest element less than 100: 90
Smallest element greater than 100: 200
Floor: 80
Ceiling: 25
5
300
New Treeset: [25, 80, 90, 100, 200]
HeadSet: [25, 80, 90]
SubSet: [90, 100, 200]How to Iterate TreeSet in Java?
In this section, we will iterate elements of TreeSet using iterator() method in ascending and descending order. Look at the following source code.
Program code 5:
import java.util.Iterator;
import java.util.TreeSet;
public class KeySetDemo {
public static void main(String[] args)
{
TreeSet<Integer> ts = new TreeSet<>();
ts.add(25);
ts.add(80);
ts.add(05);
ts.add(100);
ts.add(90);
System.out.println("Sorted TreeSet:");
// Traversing elements.
Iterator<Integer> itr = ts.iterator();
while(itr.hasNext())
{
System.out.println(itr.next());
}
System.out.println("Iterating elements through Iterator in descending order");
Iterator<Integer> it = ts.descendingIterator();
while(it.hasNext())
{
System.out.println(it.next());
}
}
}Output:
Sorted TreeSet:
5
25
80
90
100
Iterating elements through Iterator in descending order
100
90
80
25
5
How to sort TreeSet in Java | Ordering of Elements in TreeSet
A TreeSet in Java determines the order of elements in either of two ways:
1. A tree set sorts the natural ordering of elements when it implements java.lang.Comparable interface. The ordering produced by comparable interface is called natural ordering. The syntax is given below:
public interface Comparable {
public int compareTo(Object o); // Abstract method.
}The compareTo() method of this interface is implemented by TreeSet class to compare the current element with element passed in as a parameter for the order.
If the element argument is less than the current element, the method returns +ve integer, zero if they are equal, or a -ve integer if element argument is greater.
2. TreeSet in Java also determines the order of elements by implementing the Comparator interface. This technique is used when TreeSet class needs to impose a different sorting algorithm regardless of the natural ordering of elements.
The comparator interface provides two methods in which compare() method is more important. The syntax is as follows:
public interface Comparator {
public int Compare(Element e1, Element e2); // Abstract method.
public boolean equals(Element e); // Abstract methods.
}The compare() method of this interface accepts two objects (elements) arguments and returns an integer value that specifies their sort order.
This method returns a -ve value when the first element is less than second element, zero if they are equal, or +ve value if the first element is greater.
When to Use TreeSet?
TreeSet can be used when we want unique elements in sorted order.
Which is better to use: HashSet or TreeSet?
If you want to store unique elements in sorted order then use TreeSet, otherwise, use HashSet with no ordering of elements. This is because HashSet is much faster than TreeSet.
Key Points of TreeSet in Java
- TreeSet is a powerful data structure in Java that provides a way to store elements in a sorted order.
- It does not allow duplicate elements. If we try to add a duplicate element to the TreeSet, it will be ignored.
- TreeSet sorts elements in a natural order, depending on the type of elements present in it. For example, if the TreeSet contains string objects, the natural order is alphabetical.
- It is not synchronized, meaning that it is not thread-safe. Multiple threads can access the same TreeSet object concurrently.
- It provides various methods for accessing and manipulating elements. Some of these methods are add(), remove(), contains(), first(), last(), and size().
- TreeSet is faster than ArrayList and LinkedList when it comes to searching and retrieving elements.
- TreeSet is slower than ArrayList and LinkedList when it comes to inserting and deleting elements, especially when the size of the TreeSet is large.
In this tutorial, we have discussed the key points of Java TreeSet, including its definition, creation, and important methods. We also highlighted its pros and cons, which can help you decide when to use TreeSet in your Java programs. Hope that you will have understood all the basic points of TreeSet and its methods.
Thanks for reading!!
