TreeSet class implements the Navigable Set Interface and It creates a collection that uses a tree for storage. Now lets understand some features of TreeSet below.
Features of TreeSet
1) TreeSet implements the Navigable Set Interface.
2) Underlying data structure of TreeSet is balanced tree.
3) Duplicate elements are not allowed.
4) Insertion order is not preserved.
5) Heterogeneous objects are not allowed.
6) Null values are allowed but only once as duplicate are not allowed for version 1.6 or below.
7) Null values are not allowed at all for TreeSet for Java version 1.7 or above.
8) TreeSet implements serializable and cloneable interface but not Random access interface.
9) All objects are inserted based on some sorting order ( can be any order – default or customize sorting order).
10) It creates a collection that uses a tree for storage.
TreeSet Constructors in Java
1) TreeSet( ) : It will create empty TreeSet object will be having default natural sorting of elements that is ascending order.
Example : – > TreeSetts = new TreeSet();
2) TreeSet(Comparator c) : It will create the empty TreeSet object where the elements will be inserted according to some customizing sorting order defined by comparator.
Example : – > TreeSetts = new TreeSet(Comparator c);
3) TreeSet(Collection c) : It will create the equivalent TreeSet object of the collection C.
Example :- > TreeSetts = new TreeSet(Collection c);
4) TreeSet(SortedSet ss) : It will create the equivalent TreeSet object of the SortedSet ss.
Example :- > TreeSetts = new TreeSet(SortedSetss);
Java program to demonstrate default searching order of TreeSet – All elements at the output will be in default ascending sorting order.
import java.util.TreeSet;
public class TreeSets {
public static void main(String[] args) {
// create empty Treeset with ascending order( default order )
TreeSet ts = new TreeSet();
ts.add(2); // add 1st element
ts.add(3); // add 2nd element
ts.add(8); // add 3rd element
ts.add(21); // add 4th element
System.out.println(ts);
// Output ->[2, 3, 8, 21]-> ascending order
}
}
Note :For using constructor in TreeSet objects should be “homogeneous” ( objects of similar type only like int and string cannot be added together ) and “comparable” else we get runtime exception “ClassCastException”.
Note :StringBuffer() object cannot be added via this constructor as StringBuffer() objects are not comparable. StringBuffer do not implements comparable interface and string class implements comparable interface.
Note : Comarable means : Any class that implements comparable interface , then its objects are called comparable.
Java Program adding StringBuffer in TreeSet
import java.util.TreeSet;
public class TreeSets {
public static void main(String[] args) {
// create empty Treeset with ascending order
TreeSet ts = new TreeSet();
ts.add(new StringBuffer("A")); // add 1st element
//getting Exception in thread "main"
//java.lang.ClassCastException: java.lang.StringBuffer cannot be cast to java.lang.Comparable
}
}
Null value acceptance rule for TreeSet:
- For non empty TreeSet if we trying to insert “null” value then we will get the “NullPointerException”
- For empty tree we can add the first element as “null” but we cannot insert any element after adding null as first element as “NullPointerException” will generate at run time.
- “Null” value is not allowed at all for java version 1.7 or above.
- For java version 1.6 or below version “null” value is allowed as a first element only.
Lets understand the comparable interface methods and concept to sort the elements in TreeSet.
Comparable Interface
Features of comparable Interface
1) It is present in Java.lang package.
2) It contains only one method ->CompareTo()
Method – > Public int compareTo(Object obj)
- Returns negative if object1 has lower value than object2.
- Returns positive if object1 has higher value than object2.
- Returns 0 if object1 and object2 are equal.
Java program to demonstrate comparable interface
public class TreeSets {
public static void main(String[] args) {
String object1 = "A";
String object2 = "B";
String object3 = "A";
// Case 1: object1 is less than object2
System.out.println(object1.compareTo(object2));
// output -> negative value (-1 or any )
// A comes before B or A is less than B
//Case 2 :object1 is more than object2
System.out.println(object2.compareTo(object1));
// output -> positive value (1 or any)
// A comes before B or A is less than B
// Case 3 : object1 is equal to object3
System.out.println(object1.compareTo(object3));
// output -> 0
// object1 is equal to object3
// Case 4 : null value is compared
System.out.println(object1.compareTo(null));
// output ->java.lang.NullPointerException
// Null cannot be compared
}
}
Output
Case 1 :object1.compareTo(object2) means “A” compared to “B” , now “A” comes before “B” so the result is negative.
Case 2 :object2.compareTo(object1) means “B” compared to “A” , now “B” comes after “A” so the result is positive.
Case 3 :object1.compareTo(object3) means “A” compared to “A” , now “A” is equal to “A” so the result is 0.
Case 4 :object1.compareTo(null) means “A” compared to “null” , Null value cannot be compared hence it will generate run time exception “java.lang.NullPointerException”.
Now come back to TreeSet
How TreeSet sort the elements internally ?
TreeSet uses comparable interface for the sorting purpose. Every element inserted into the TreeSet uses “compareTo()” method. While adding the element to TreeSet JVM calls compareTo() method.
TreeSet uses the “compareTo()” method of comparable interface to sort the elements for the default ascending sorting order.
Java program to demonstrate the default sorting of the TreeSet
import java.util.TreeSet;
public class TreeSets {
public static void main(String[] args) {
// create empty Treeset with ascending order
TreeSet ts = new TreeSet();
ts.add("B"); // add 1st element
ts.add("G"); // add 2nd element
ts.add("A"); // add 3rd element
ts.add("A"); // add 4th element
ts.add("Z"); // add 4th element
System.out.println(ts);
// output -> [A, B, G, Z] - ascending sorting order
}
}
Lets understand how this sorting is done.
Now JVM uses the compareTo() method for the sorting purpose by default if specific comparator is not defined.
Method used object1.compareTo(object2)
Here object1 is which is inserted in TreeSet and Object2 is which is already there in TreeSet and to whom with the comparison will be done.
1)Add 1st element ->B , “B” is added to TreeSet.
2) Add 2nd element ->G , “G” is first compared to B. Now here “G” is compared to “B” with method “G”.compareTo(“B”).
Here G comes after B hence it will return positive and it will add to right side of Tree as shown in diagram.
3)Add 3rd element -> A , “A” is first compared to “B”(Root Node).Now here “A” is compared to “B” with method “A”.compareTo(“B”).
Here A comes before B hence it will return negative and it will add to left side of Tree as shown in diagram.
4)Add 4th element “A”. “A” is first compared to “B”(Root Node).Now here “A” is compared to “B” with method “A”.compareTo(“B”).
Here A comes before B hence it will return negative and it will add to left side of Tree as shown in diagram. But at left there is one more element “A” is there , so “A” is now compared to “A”.Now here “A” is compared to “A” with method “A”.compareTo(“A”). both are equal hence it will return 0. Hence “A” is duplicate hence it will rejected.
Diagram Showing insertion of element
To sort the elements in some specific order we need to use the comparator interface. We will learn about comparator in next tutorial.
Note : Comparable is used for default sorting order and Comparator is used for customize sorting order.