Java TreeSet Class

Java TreeSet class implements the Set interface that uses a tree for storage. It inherits AbstractSet class and implements the NavigableSet interface. The objects of the TreeSet class are stored in ascending order.

The ordering is maintained automatically using a self-balancing tree structure, which makes the TreeSet particularly useful when sorted data is needed. TreeSet does not allow insertion of unordered or duplicate values, and any attempt to do so is simply ignored by the set.

Features of TreeSet Class

• Java TreeSet class contains unique elements only, just like HashSet.
• Java TreeSet class provides fast access and retrieval.
• Java TreeSet class does not allow null elements.
• Java TreeSet class is non-synchronized.
• Java TreeSet class maintains ascending order.
• TreeSet allows only those elements that are comparable (i.e., implement the Comparable interface).

Internal Working of TreeSet Class

TreeSet is implemented using a self-balancing binary search tree (like a Red-Black Tree). Because of this, operations like search, add, and remove take O(log N) time.

The tree automatically keeps itself balanced, so its height remains small. This makes TreeSet efficient for storing large amounts of sorted data and performing operations quickly.

Key Aspects of TreeSet Functionality

• Red-Black Tree Structure: TreeSet uses a special tree where each node is marked as red or black. It helps the tree stay balanced and keeps operations fast.
• Dynamic Rebalancing: When elements are added or removed, TreeSet automatically adjusts the tree. It always keeps the elements in sorted (ascending) order.
• Handling Duplicates: TreeSet stores only unique elements. If we try to add a duplicate value, it will be ignored.
• Order Determination: TreeSet sorts elements using their natural order or a custom comparator. It allows us to control how elements are arranged.

Synchronization of TreeSet Class

TreeSet is not synchronized. It means it is not safe to use directly when multiple threads are working on it at the same time.

If one thread is modifying the TreeSet while others are accessing it, then we need to handle synchronization manually.

We can do this by using synchronization techniques or by wrapping the TreeSet using the Collections.synchronizedSet() method. It is better to do this at the time of creation to avoid any issues.

TreeSet treeSet = new TreeSet(); 
Set syncrSet = Collections.synchronziedSet(treeSet);

Hierarchy of the TreeSet Class

As shown in the following diagram, the Java TreeSet class implements the NavigableSet interface.

The NavigableSet interface further extends the SortedSet, Set, Collection, and Iterable interfaces in hierarchical order.

Key Points about TreeSet Hierarchy

• SortedSet Interface: TreeSet implements the SortedSet interface, which extends the Set interface. It provides methods to maintain elements in sorted order.
• NavigableSet Interface: NavigableSet extends SortedSet and provides additional methods to navigate elements, such as finding elements before or after a given value.
• Efficiency: TreeSet is backed by a TreeMap and uses a Red-Black Tree structure. Because of this, operations like add, remove, and search take O(log N) time.

TreeSet Class Declaration

Let's see the declaration for java.util.TreeSet class.

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, Serializable  

Components of the Declaration

Here are the main components of the TreeSet class declaration:

1. TreeSet<E> Class: The TreeSet class is declared as public, meaning it can be accessed from anywhere class within any package.
   The <E> denotes that TreeSet is a generic class, capable of storing objects of any type, as specified by the user.
2. AbstractSet<E>: TreeSet class extends the AbstractSet interface that provides a skeletal implementation of the Set interface. It means that the TreeSet class inherits all the abstract methods from the AbstractSet interface.
3. NavigableSet<E>: By implementing NavigableSet, TreeSet gains() methods to navigate the set in relation to a given target element, such as higher, lower, ceiling, and floor. The interface extends SortedSet, which in turn extends Set, ensuring that TreeSet has all functionalities of a sorted and navigable set.
4. Cloneable: It indicates that TreeSet supports cloning, allowing it to be copied safely without affecting the original set.
5. Serializable: It ensures that a TreeSet can be serialized, meaning its state can be converted into a byte stream that can be reverted back into a copy of the TreeSet. Serialization is essential for saving the state of an object for later retrieval or transmission to a different processing environment.

Java TreeSet Class Constructors

Java TreeSet Class Methods

Java TreeSet Class Example

Example: Adding Elements in TreeSet

import java.util.*;  
class Main {  
 public static void main(String args[]){  
  //Creating and adding elements  
  TreeSet<String> al=new TreeSet<String>();  
  al.add("Robert");  
  al.add("David");  
  al.add("Maria");  
  al.add("Mary");  
  //Traversing elements  
  Iterator<String> itr=al.iterator();  
  while(itr.hasNext()){  
   System.out.println(itr.next());  
  }  
 }  
}  

Output:

David
Maria
Mary
Robert

Example: Traversing in Descending Order

In this example, we are traversing the TreeSet in descending order using descendingIterator().

import java.util.*;  
class Main {  
 public static void main(String args[]){  
 TreeSet<String> set=new TreeSet<String>();  
         set.add("John");  
         set.add("William");  
         set.add("Michael");  
         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
William
Michael
John

Example: Retrieve and Remove Highest and Lowest Values

In this example, we are retrieving and removing the lowest and highest elements.

import java.util.*;    
class Main
{    
 public static void main(String args[]){    
 TreeSet<Integer> set=new TreeSet<Integer>();    
         set.add(24);    
         set.add(66);    
         set.add(12);    
         set.add(15);    
         System.out.println("Lowest Value: "+set.pollFirst());    
         System.out.println("Highest Value: "+set.pollLast());    
 }    
}    

Output:

Lowest Value: 12
Highest Value: 66

Example: NavigableSet Operations

In this example, we are performing different NavigableSet operations on TreeSet.

import java.util.*;  
class Main {  
 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]

Example: SortedSet Operations

In this example, we are performing SortedSet operations like headSet(), subSet(), and tailSet().

import java.util.*;  
class Main
{  
 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("Intial Set: "+set);  
         System.out.println("Head Set: "+set.headSet("C"));  
         System.out.println("SubSet: "+set.subSet("A", "E"));  
         System.out.println("TailSet: "+set.tailSet("C"));  
 }  
}  

Output:

Intial Set: [A, B, C, D, E]
Head Set: [A, B]
SubSet: [A, B, C, D]
TailSet: [C, D, E]

Example: TreeSet with User-defined Objects

In this example, we are storing user-defined objects in TreeSet using the Comparable interface.

import java.util.*;    
// Defining the Book class that implements Comparable interface to allow sorting by id
class Book implements Comparable<Book> {    
 int id;               // Book ID
 String name;          // Book Name
 String author;        // Author Name
 String publisher;     // Publisher Name
 int quantity;         // Quantity of books
 // Constructor to initialize Book object
 public Book(int id, String name, String author, String publisher, int quantity) {    
  this.id = id;    
  this.name = name;    
  this.author = author;    
  this.publisher = publisher;    
  this.quantity = quantity;    
 }    
 // compareTo method overridden to sort books by id in ascending order
 public int compareTo(Book b) {    
  return Integer.compare(this.id, b.id);  // more concise and safe comparison
 }    
}    
public class Main {    
 // main method to execute the program
 public static void main(String[] args) {    
  // Creating a TreeSet of Book. TreeSet will maintain elements in sorted order based on Book ID.
  Set<Book> set = new TreeSet<Book>();    
  // Creating Book objects
  Book b1 = new Book(121, "Let us C", "Yashwant Kanetkar", "BPB", 8);    
  Book b2 = new Book(233, "Operating System", "Galvin", "Wiley", 6);    
  Book b3 = new Book(101, "Data Comm", "Forouzan", "Mc Graw Hill", 4);    
  // Adding Book objects to TreeSet
  set.add(b1);    
  set.add(b2);    
  set.add(b3);    
  // Iterating over the TreeSet
  // The books will be printed in order based on their IDs (101, 121, 233)
  for (Book b : set) {    
   System.out.println(b.id + " " + b.name + " " + b.author + " " + b.publisher + " " + b.quantity);    
  }    
 }    
}  

Output:

101 Data Comm Forouzan Mc Graw Hill 4
121 Let us C Yashwant Kanetkar BPB 8
233 Operating System Galvin Wiley 6

Example: ClassCastException in TreeSet

In this example, we are adding objects that do not implement Comparable, which causes an exception.

import java.util.*;    
class Employee {    
 int empId;    
 String name;    
}    
class Main {    
 public static void main(String[] args){    
  TreeSet<Employee> set = new TreeSet<Employee>();    
  set.add(new Employee());    
  set.add(new Employee());    
 }    
}  

Output:

ClassCastException

TreeSet Vs. HashSet

The following table shows the difference between TreeSet and HashSet: