In this tutorial, we will try to understand how TreeSet works and where we should use TreeSet in Java development.
The java.util.TreeSet is a class that extends the java.util.AbstractSet class and implements the java.util.NavigableSet, java.lang.Cloneable, and java.io.Serializable interfaces.
public class java.util.TreeSet<E> extends java.util.AbstractSet<E> implements java.util.NavigableSet<E>, java.lang.Cloneable, java.io.Serializable {
java.util.TreeSet(java.util.NavigableMap<E, java.lang.Object>);
public java.util.TreeSet();
public java.util.TreeSet(java.util.Comparator<? super E>);
public java.util.TreeSet(java.util.Collection<? extends E>);
public java.util.TreeSet(java.util.SortedSet<E>);
public java.util.Iterator<E> iterator();
public java.util.Iterator<E> descendingIterator();
public java.util.NavigableSet<E> descendingSet();
public int size();
public boolean isEmpty();
public boolean contains(java.lang.Object);
public boolean add(E);
public boolean remove(java.lang.Object);
public void clear();
public boolean addAll(java.util.Collection<? extends E>);
public java.util.NavigableSet<E> subSet(E, boolean, E, boolean);
public java.util.NavigableSet<E> headSet(E, boolean);
public java.util.NavigableSet<E> tailSet(E, boolean);
public java.util.SortedSet<E> subSet(E, E);
public java.util.SortedSet<E> headSet(E);
public java.util.SortedSet<E> tailSet(E);
public java.util.Comparator<? super E> comparator();
public E first();
public E last();
public E lower(E);
public E floor(E);
public E ceiling(E);
public E higher(E);
public E pollFirst();
public E pollLast();
public java.lang.Object clone();
public java.util.Spliterator<E> spliterator();
static {};
}
Here, in the API of the java.util.TreeSet class, we can observe that the java.util.TreeSet class does not explicitly implement the java.util.Set interface. This may raise the question of how the java.util.TreeSet class qualifies as a collection of the Set type.
The explanation lies in the fact that the java.util.TreeSet class implements the java.util.NavigableSet interface. Furthermore, the java.util.NavigableSet interface extends the java.util.SortedSet interface, and the java.util.SortedSet interface, in turn, extends the more general java.util.Set interface. Therefore, it becomes evident that java.util.TreeSet is indeed a type of Set collection, similar to HashSet and LinkedHashSet.
public interface java.util.NavigableSet<E> extends java.util.SortedSet<E> {
public abstract E lower(E);
public abstract E floor(E);
public abstract E ceiling(E);
public abstract E higher(E);
public abstract E pollFirst();
public abstract E pollLast();
public abstract java.util.Iterator<E> iterator();
public abstract java.util.NavigableSet<E> descendingSet();
public abstract java.util.Iterator<E> descendingIterator();
public abstract java.util.NavigableSet<E> subSet(E, boolean, E, boolean);
public abstract java.util.NavigableSet<E> headSet(E, boolean);
public abstract java.util.NavigableSet<E> tailSet(E, boolean);
public abstract java.util.SortedSet<E> subSet(E, E);
public abstract java.util.SortedSet<E> headSet(E);
public abstract java.util.SortedSet<E> tailSet(E);
}
public interface java.util.SortedSet<E> extends java.util.Set<E> {
public abstract java.util.Comparator<? super E> comparator();
public abstract java.util.SortedSet<E> subSet(E, E);
public abstract java.util.SortedSet<E> headSet(E);
public abstract java.util.SortedSet<E> tailSet(E);
public abstract E first();
public abstract E last();
public java.util.Spliterator<E> spliterator();
}
Important points of java.util.TreeSet:
1. TreeSet doesn’t store different types of data, unlike other Set-type collections such as HashSet and LinkedHashSet.
2. Duplicity is not allowed in TreeSet.
3. Null values cannot be stored in a TreeSet.
4. When we create an object of TreeSet, it internally creates a TreeMap and stores elements using natural sorting algorithms by default or using a user-defined comparator.
5. None of the members of the java.util.TreeSet class are synchronized, making TreeSet non-synchronized.
6. Because the java.util.TreeSet class implements the java.lang.Cloneable and java.io.Serializable interfaces, it is eligible for cloning and serialization.
Constructor of java.util.TreeSet class:
1. public java.util.TreeSet(): It creates an empty TreeSet that stores data and sorts it according to natural sorting. It's important to note that all elements added to the newly created empty TreeSet must implement the java.lang.Comparable interface. This interface is a functional interface containing an abstract method.
public abstract intcompareTo(Object);When creating a subclass of this interface, it is necessary to override the compareTo() method and provide an implementation based on the specific business logic.
In Java, the compareTo() method is commonly used to establish the natural sorting order for objects. For instance, in the java.lang.Integer class, the compareTo method is overridden to define natural sorting in ascending order based on the values of the class. A similar concept applies to the java.lang.String class, where the compareTo method is overridden to define natural sorting based on the ASCII values of the content.
Natural Sorting: - When items of a particular type are sorted in an array or collection, their natural ordering is the default order. The Java language provides the Comparable interface to allow us to specify a class's natural ordering. Here is how this interface is declared:
publicinterfaceComparable
publicintcompareTo(T object);
}
This interface is parameterized with generics, and it offers a single method called compareTo(). This method allows you to compare two objects of the same type. The crucial outcome of this comparison is an integer number returned by the method. It's important to keep in mind these guidelines:
• compare value = 0: two objects are equal.
• compare value > 0: the first object (the current object) is greater than the second one.
• compare value < 0: the first object is less than the second one.
Consider this scenario: when objects are being sorted, their compareTo() methods are invoked to compare with other objects. The sorting is then done based on the comparison values returned by these methods, arranging the objects according to their natural ordering.
The objects used in collections or arrays must implement the java.lang.Comparable interface to provide natural ordering of their objects. Otherwise, runtime errors may occur.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.TreeSet;
public class JTC {
public static void main(String[] args) {
// Creating empty TreeSet using default constructor with Natural Sorting
TreeSet t1 = new TreeSet();
t1.add(new Integer(2));
t1.add(new Integer(1));
t1.add(new Integer(4));
t1.add(new Integer(3));
System.out.println("t1 :- " + t1);
// Natural Sorting with Array using Arrays.sort() method
Integer ar1[] = {
10,
2,
5,
12,
67
};
Arrays.sort(ar1);
for (Integer i: ar1) {
System.out.print(i + " ");
}
// Natural Sorting with ArrayList using Collections.sort() method
ArrayList list1 = new ArrayList();
list1.add(101);
list1.add(23);
list1.add(-90);
list1.add(678);
Collections.sort(list1);
System.out.println("\nlist1 :- " + list1);
}
}
t1 :- [1, 2, 3, 4]
2 5 10 12 67
list1 :- [-90, 23, 101, 678]
In this example, we first create a TreeSet using the default constructor, which stores elements using natural sorting order. Since we are storing Integer class objects in the newly created TreeSet, the compareTo() method in the java.util.Integer class is overridden to define their natural sorting in ascending order. The result can be observed in the output: `t1 :- [1, 2, 3, 4].
In the next section, we create an array of type java.lang.Integer with elements and attempt to sort them using the Arrays.sort(array) method. It's crucial to note that the java.util.Arrays.sort(array) method can only sort arrays of types that implement java.lang.Comparable. Otherwise, a ClassCastException occurs at runtime.
Since the specified array is of type java.lang.Integer, the Arrays.sort(array) method sorts the elements according to the natural sorting order of the java.lang.Integer class, which is in ascending order.
The same concept applies to the Collections.sort() method, which sorts an ArrayList of type Integer using natural sorting, resulting in ascending order.
import java.util.TreeSet;
import java.util.Iterator;
class Student implements Comparable {
int sid;
String sname;
String scity;
float marks;
Student(int sid, String sname, String scity, float marks) {
this.sid = sid;
this.sname = sname;
this.scity = scity;
this.marks = marks;
}
@Override
public String toString() {
return "Student [sid=" + sid + ", sname=" + sname + ", scity=" + scity + ", marks=" + marks + "]\n";
}
public int compareTo(Object o) {
Student s = (Student) o;
if (this.marks == s.marks) {
return 0;
}
else if(this.marks > s.marks) {
return 1;
} else {
return -1;
}
}
}
public class JTC {
public static void main(String[] args) {
TreeSet set = new TreeSet();
set.add(new Student(101, "Vivek", "Noida", 89));
set.add(new Student(102, "Rahul", "Delhi", 78));
set.add(new Student(103, "Neha", "Kanpur", 123));
set.add(new Student(104, "Amit", "Nagpur", 789));
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}
Student [sid=102, sname=Rahul, scity=Delhi, marks=78.0]
Student [sid=101, sname=Vivek, scity=Noida, marks=89.0]
Student [sid=103, sname=Neha, scity=Kanpur, marks=123.0]
Student [sid=104, sname=Amit, scity=Nagpur, marks=789.0]
In the last example, we attempted to sort elements of type java.lang.Integer using TreeSet, the Arrays.sort() method for an array, and the Collections.sort() method for an ArrayList. The reason this worked seamlessly is that the java.lang.Integer class is already overridden to define its natural sorting order.
In this example, we are manually defining the natural sorting for the Student class. As seen here, the Student class contains four pieces of information about a student: sid, name, city, and marks.
And Student class is implementing java.lang.Cloneable interface and overriding the compareTo() method.
public int compareTo(Object o) {
Student s = (Student) o;
if(this.marks == s.marks)
return 0;
}else if(this.marks>s.marks) {
return 1;
}else {
return -1;
}
}
We can observe in the logic of the compareTo() method that we are comparing the marks of the current working object of the Student class with the marks of the argument object. Based on various conditions, we return 0, 1, or -1, as appropriate.
As we are aware, TreeSet stores data according to the natural sorting order defined in the Student class using the compareTo() method.
2. public java.util.TreeSet(java.util.Comparator): We use the java.util.TreeSet(java.util.Comparator) constructor to create an empty TreeSet that sorts elements according to the provided comparator.
There is the java.util.Comparator interface, which includes an abstract method: public abstract int compare(Object, Object). By overriding the compare(Object, Object) method, we can define a custom comparison algorithm based on the business logic.
import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;
class Student implements Comparable {
int sid;
String sname;
String scity;
float marks;
Student(int sid, String sname, String scity, float marks) {
this.sid = sid;
this.sname = sname;
this.scity = scity;
this.marks = marks;
}
@Override
public String toString() {
return "Student [sid=" + sid + ", sname=" + sname + ", scity=" + scity + ", marks=" + marks + "]";
}
public int compareTo(Object o) {
Student s = (Student) o;
if (this.marks == s.marks) {
return 0;
}
else if(this.marks > s.marks) {
return 1;
} else {
return -1;
}
}
}
// We are creating a Comparator in the basis of Student marks.
class StudentMarks implements Comparator {
public int compare(Object o1, Object o2) {
Student s1 = (Student) o1;
Student s2 = (Student) o2;
if (s1.marks > s2.marks) {
return 1;
}
else if(s1.marks == s2.marks) {
return 0;
} else {
return -1;
}
}
}
class StudentName implements Comparator {
public int compare(Object o1, Object o2) {
Student s1 = (Student) o1;
Student s2 = (Student) o2;
if (s1.sname.charAt(0) > s2.sname.charAt(0)) {
return 1;
}
else if(s1.sname.charAt(0) == s2.sname.charAt(0)) {
return 0;
} else {
return -1;
}
}
}
public class JTC {
public static void main(String[] args) {
// CreatingTreeSet with a comparator which stores the element on the basis of StudentMarksComparator
TreeSet set = new TreeSet(new StudentMarksComparator());
set.add(new Student(101, "Vivek", "Noida", 89));
set.add(new Student(102, "Rahul", "Delhi", 78));
set.add(new Student(103, "Neha", "Kanpur", 123));
set.add(new Student(104, "Amit", "Nagpur", 789));
System.err.println("----Student Details in Aecending Order on the basis of Student Marks----");
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
// CreatingTreeSet with a comparator which stores the element on the basis of StudentNameComparator
TreeSet set1 = new TreeSet(new StudentNameComparator());
set1.add(new Student(101, "Vivek", "Noida", 89));
set1.add(new Student(102, "Rahul", "Delhi", 78));
set1.add(new Student(103, "Neha", "Kanpur", 123));
set1.add(new Student(104, "Amit", "Nagpur", 789));
System.err.println("----Student Details in Aecending Order on the basis of Student Name First Letter ASCII CODE----");
Iterator iterator1 = set1.iterator();
while (iterator1.hasNext()) {
System.out.println(iterator1.next());
}
}
}
----Student Details in Aecending Order on the basis of Student Marks----
Student [sid=102, sname=Rahul, scity=Delhi, marks=78.0]
Student [sid=101, sname=Vivek, scity=Noida, marks=89.0]
Student [sid=103, sname=Neha, scity=Kanpur, marks=123.0]
Student [sid=104, sname=Amit, scity=Nagpur, marks=789.0]
----Student Details in Aecending Order on the basis of Student Name First Letter ASCII CODE----
Student [sid=104, sname=Amit, scity=Nagpur, marks=789.0]
Student [sid=103, sname=Neha, scity=Kanpur, marks=123.0]
Student [sid=102, sname=Rahul, scity=Delhi, marks=78.0]
Student [sid=101, sname=Vivek, scity=Noida, marks=89.0]
In this example, as depicted in the Student class, there are four distinct fields: sid, sname, scity, and marks.
In this example, we create two custom comparators, namely StudentMarksComparator and StudentNameComparator, by implementing the java.util.Comparator interface and overriding the compare(Object, Object) method.
StudentMarksComparatorcompare(object,object) method:
public int compare(Object o1,Object o2) {
Student s1 = (Student) o1;
Student s2 = (Student) o2;
if (s1.marks > s2.marks) {
return 1;
} elseif(s1.marks == s2.marks) {
return 0;
} else {
return -1;
}
}StudentNameComparatorcompare(object,object) method:
public int compare(Object o1, Object o2) {
Student s1 = (Student) o1;
Student s2 = (Student) o2;
if (s1.sname.charAt(0) > s2.sname.charAt(0)) {
return 1;
} elseif (s1.sname.charAt(0) == s2.sname.charAt(0)) {
return 0;
} else {
return -1;
}
}In the StudentMarksComparator class, the compare(Object, Object) method compares students based on their marks. In the StudentNameComparator class, the compare(Object, Object) method compares students based on the ASCII code of the first character in their names.
In the JTC class's main method, we create two TreeSet objects, set and set1, using their constructors with the java.util.Comparator (comparator) parameter. These sets store elements based on the specified comparators.
Ques:-What is the difference between sorting along with java.lang.Comparable.compareTo(object) and java.util.Comparator.compare(object) :