TreeSet isΒ very important implementations of the SortedSet interface . TreeSet implements NavigableSet and SortedSet interfaces.
TreeSet internally uses TreeMap to store elements. The elements of TreeSet are sorted as per their natural order. We can also provide the custom comparator in TreeSet during the Object creation of TreeSet for sorting the contents of basis on the given comparator.
Because theΒ TreeSet
Β implementsΒ NavigableSet
Β interface, it has functionalities ofΒ Β NavigableSet
Β andΒ Β SortedSet
Β both. Therefore we can navigate in TreeSet on any element.
The important points about Java TreeSet are:
- Java TreeSet class contains unique elements.
- Elements in the TreeSet are stored in a sorted and ascending order.
- TreeSet cannot containΒ
null
Β value. - It does not preserve the insertion order of elements instead elements are sorted by keys.
- TreeSet class is not thread-safe. You shouldΒ synchronize concurrent access to a TreeSet in a multi-threaded environment.
- TreeSet class is implementation of aΒ binary search tree like Red-Black Tree.
Simple TreeSet Example
The following example shows how to create a TreeSetΒ class and add new elements in it. The TreeSet will be sorted based on the natural ordering of the elements –
import java.util.SortedSet; import java.util.TreeSet; public class TreeSetExample { public static void main(String[] args) { // Creating a TreeSet SortedSet<String> games = new TreeSet<>(); // Adding new elements to a TreeSet games.add("Cricket"); games.add("BasketBall"); games.add("Hockey"); games.add("Chess"); System.out.println("Games Set : " + games); // Duplicate elements are ignored games.add("Cricket"); System.out.println("After adding duplicate element \"Cricket\" : " + games); // This will be allowed because it's in lowercase. games.add("chess"); System.out.println("After adding \"chess\" : " + games); } }Output :- Games Set : [BasketBall, Chess, Cricket, Hockey] After adding duplicate element "Cricket" : [BasketBall, Chess, Cricket, Hockey] After adding "chess" : [BasketBall, Chess, Cricket, Hockey, chess]
TreeSet with a custom comparator
This example shows how to create a TreeSet with a custom comparator which sorts the elements.
import java.util.Comparator; import java.util.SortedSet; import java.util.TreeSet; public class TreeSetDescendingOrderEx { public static void main(String[] args) { // Creating a TreeSet with a custom Comparator (Descending Order) SortedSet<String> games = new TreeSet<>(Comparator.reverseOrder()); /* The above TreeSet with the custom Comparator is the concise form of the following: SortedSet<String> fruits = new TreeSet<>(new Comparator<String>() { @Override public int compare(String s1, String s2) { return s2.compareTo(s1); } }); */ // Adding new elements to a TreeSet games.add("Cricket"); games.add("Hocket"); games.add("Chess"); games.add("Carom"); System.out.println("Games Set : " + games); } } Output:- Games Set : [Hocket, Cricket, Chess, Carom]
TreeSet with user defined objects
Because the TreeSet class has to keep the objects sorted, we must either implement theΒ ComparableΒ interface in the user defined class and give the implementation for theΒ compareTo()
Β function, or give a customΒ ComparatorΒ during creation of the TreeSet.
import java.util.Comparator; import java.util.Objects; import java.util.SortedSet; import java.util.TreeSet; class Employee implements Comparable<Employee> { private int id; private String name; public Employee(int id, String name) { this.id = id; this.name = name; } public int getId() { return id; } public void setId(int id) { this.id = id; } public String getName() { return name; } public void setName(String name) { this.name = name; } // Two Employees are equal if their IDs are equal @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Employee employee = (Employee) o; return id == employee.id; } @Override public int hashCode() { return Objects.hash(id); } // Compare employees based on their IDs @Override public int compareTo(Employee employee) { return this.getId() - employee.getId(); } @Override public String toString() { return "Employee{" + "id=" + id + ", name='" + name + '\'' + '}'; } } import java.util.Comparator; import java.util.SortedSet; import java.util.TreeSet; public class TreeSetUserDefinedObjectExample { public static void main(String[] args) { // Creating a TreeSet of User Defined Objects. /* The requirement for a TreeSet of user defined objects is that 1. Either the class should implement the Comparable interface and provide the implementation for the compareTo() function. 2. Or you should provide a custom Comparator while creating the TreeSet. */ SortedSet<Employee> employees = new TreeSet<>(); // TreeSet uses the compareTo() method of the Employee class to compare two employees and sort them employees.add(new Employee(101, "Ashish")); employees.add(new Employee(105, "Swapnil")); employees.add(new Employee(108, "Rahul")); employees.add(new Employee(106, "Anuj")); System.out.println("Employees (sorted based on Employee class's compareTo() function)"); System.out.println(employees); // Providing a Custom Comparator (This comparator compares the employees based on their Name) employees = new TreeSet<>(Comparator.comparing(Employee::getName)); employees.add(new Employee(109, "Ashish")); employees.add(new Employee(107, "Rahul")); employees.add(new Employee(106, "Pradeep")); System.out.println("\nEmployees (sorted based on the supplied Comparator)"); System.out.println(employees); } } Output: - Employees (sorted based on Employee class's compareTo() function) [Employee{id=101, name='Ashish'}, Employee{id=105, name='Swapnil'}, Employee{id=106, name='Anuj'}, Employee{id=108, name='Rahul'}] Employees (sorted based on the supplied Comparator) [Employee{id=109, name='Ashish'}, Employee{id=106, name='Pradeep'}, Employee{id=107, name='Rahul'}]
Various NavigableSet operations
In this example we will perform various NavigableSet operations.
import java.util.*; class NavigableSetExample{ public static void main(String args[]){ TreeSet<String> set=new TreeSet<String>(); set.add("A"); set.add("B"); set.add("C"); set.add("D"); set.add("E"); System.out.println("Initial Set: "+set); System.out.println("Reverse Set: "+set.descendingSet()); System.out.println("Head Set: "+set.headSet("C", true)); System.out.println("SubSet: "+set.subSet("A", false, "E", true)); System.out.println("TailSet: "+set.tailSet("C", false)); } } Output:- Initial Set: [A, B, C, D, E] Reverse Set: [E, D, C, B, A] Head Set: [A, B, C] SubSet: [B, C, D, E] TailSet: [D, E]
Retrieve and Remove the highest and lowest Value
Here in this example we will look at how to retrieve and remove the highest and lowest value.
import java.util.*; class RetreiveTreeSetExample { public static void main(String args[]){ TreeSet<Integer> set=new TreeSet<Integer>(); set.add(20); set.add(62); set.add(11); set.add(18); System.out.println("Highest Value: "+set.pollFirst()); System.out.println("Lowest Value: "+set.pollLast()); } } Output:- Highest Value: 11 Lowest Value: 62
Traversing elements in Descending order
Let’s look at this example of TreeSet traversing elements in descending order.
import java.util.*; class TraverseDescTreeSet{ public static void main(String args[]){ TreeSet<String> set=new TreeSet<String>(); set.add("Ashish"); set.add("Swapnil"); set.add("Ajay"); set.add("Yash"); System.out.println("Traversing element through Iterator in descending order"); Iterator i=set.descendingIterator(); while(i.hasNext()) { System.out.println(i.next()); } } } Output:- Traversing element through Iterator in descending order Yash Swapnil Ashish Ajay
Conclusion
Congratulations Readers!Β In this article you have learned about what is TreeSet, how to Create a TreeSet object. Its implements using comparator and user defined objects. How to access the elements of TreeSet. Traversing in descending order.