Java Treeset

The Java TreeSet class is an implementation of the Set interface that utilizes a tree structure for storage. It extends the AbstractSet class and also implements the NavigableSet interface. Objects within a TreeSet are organized in ascending order.

The important points about the Java TreeSet class are:

• ✅ Java TreeSet class contains unique elements only like HashSet.
• ✅ Java TreeSet class access and retrieval times are quite fast.
• ✅ Java TreeSet class doesn't allow null elements.
• ✅ Java TreeSet class is non-synchronized.
• ✅ Java TreeSet class maintains ascending order.
• ✅ The TreeSet can only allow those generic types that are comparable. For example, the Comparable interface is being implemented by the StringBuffer class.

Internal Working of The TreeSet Class

A TreeSet is constructed utilizing a self-balancing binary search tree, similar to a Red-Black Tree. As a result, tasks like searching, adding, and removing elements require O(log(N)) time complexity. This efficiency is achieved through the self-balancing nature of the tree, which prevents the height of the tree from exceeding O(log(N)) for all specified operations. Hence, TreeSet proves to be a highly effective data structure for maintaining and performing operations on large sorted datasets.

Key Aspects of TreeSet's Functionality

• ✅ Red-Black Tree Structure: Each node in this tree is assigned a color-either red or black-which plays a crucial role in maintaining the tree's balance. This strategic coloring helps prevent the tree from becoming lopsided, which enhances performance and ensures that operations are processed quickly and efficiently.
• ✅ Dynamic Rebalancing: Whenever elements are added or removed, TreeSet dynamically adjusts its internal structure. It ensures that the set's elements are always in ascending order, making it highly reliable for applications that require well-ordered data.
• ✅ Handling Duplicates: TreeSet is designed to store only unique elements. Attempts to add duplicates are gracefully handled by the set, ensuring that only distinct elements are maintained. It is crucial for data integrity and simplifies management of collections where uniqueness is a priority.
• ✅ Order Determination: The sorting of elements within TreeSet can follow the natural ordering of the elements or be defined by a custom comparator. This flexibility allows developers to control how elements are compared and ordered within the set.

Synchronization of The TreeSet Class

As previously stated, it's important to note that the TreeSet class lacks synchronization. This implies that when multiple threads access a tree set concurrently, and one of them intends to modify it, manual synchronization becomes necessary. Typically, this is achieved by applying object synchronization techniques to encapsulate the set. Alternatively, if no suitable object is available, the set can be enclosed using the Collections.synchronizedSet method. To prevent unsynchronized access to the set, it is recommended to employ this method during the set's creation process. Below is a code snippet demonstrating this approach.

Synchronization of The TreeSet Class

As noted earlier, the TreeSet class does not have built-in synchronization. When multiple threads access a tree set concurrently and one of them makes modifications, manual synchronization is required. This typically involves encapsulating the set within an object for synchronization. If such an object is not available, the set can be wrapped using the Collections.synchronizedSet method. It is recommended to apply this method during the set's creation to prevent unsynchronized access. Below is an example code snippet demonstrating this process.

TreeSet treeSet = new TreeSet(); 

Set syncrSet = Collections.synchronziedSet(treeSet);

Hierarchy of theTreeSet Class

Illustrated in the diagram above, the Java TreeSet class is an implementation of the NavigableSet interface. The NavigableSet interface expands upon the interfaces SortedSet, Set, Collection, and Iterable in a hierarchical manner.

The TreeSet class is an essential component of the Java Collections Framework, specifically created to maintain elements in a unique and sorted order, guaranteeing the absence of duplicates. Below are essential details regarding its hierarchical arrangement:

The TreeSet class implements the SortedSet interface, which is an extension of the Set interface. The SortedSet interface provides additional methods for managing element order and enabling range-view features, crucial for organized data handling.

The NavigableSet Interface, situated beneath the SortedSet, introduces enhanced navigation features. It empowers TreeSet to fetch elements according to their specific relationship with other elements in the set, thereby improving its effectiveness in conducting data retrieval and manipulation tasks.

Performance: TreeSet leverages a TreeMap implemented with a red-black tree design to execute essential tasks such as insertion, deletion, and element existence verification in logarithmic time complexity. This makes TreeSet well-suited for demanding applications that necessitate rapid data manipulation.

TreeSet Class Declaration

Let's examine the declaration syntax for the java.util.TreeSet class.

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

Components of the Declaration

• ✅ 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.
• ✅ 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.
• ✅ 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.
• ✅ Cloneable: It indicates that TreeSet supports cloning, allowing it to be copied safely without affecting the original set.
• ✅ 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.

Constructors of Java TreeSet Class

Methods of Java TreeSet Class

Java TreeSet Examples

Java TreeSet Example 1:

Let's see a simple example of Java TreeSet.

FileName: TreeSet1.java

import java.util.*;

class TreeSet1{

 public static void main(String args[]){

  //Creating and adding elements

  TreeSet<String> al=new TreeSet<String>();

  al.add("Ravi");

  al.add("Vijay");

  al.add("Ravi");

  al.add("Ajay");

  //Traversing elements

  Iterator<String> itr=al.iterator();

  while(itr.hasNext()){

   System.out.println(itr.next());

  }

 }

}

Output:

Ajay

Ravi

Vijay

Java TreeSet Example 2:

Let's explore an instance of iterating through elements in a reverse order.

FileName: TreeSet2.java

import java.util.*;

class TreeSet2{

 public static void main(String args[]){

 TreeSet<String> set=new TreeSet<String>();

		 set.add("Ravi");

		 set.add("Vijay");

		 set.add("Ajay");

		 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

Vijay

Ravi

Ajay

Traversing element through NavigableSet in descending order

Vijay

Ravi

Ajay

Java TreeSet Example 3:

Let's consider an example demonstrating how to extract and eliminate the maximum and minimum values.

FileName: TreeSet3.java

import java.util.*;  

class TreeSet3{  

 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

Java TreeSet Example 4:

In this instance, we demonstrate a range of operations on a NavigableSet.

FileName: TreeSet4.java

import java.util.*;

class TreeSet4{

 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]

Java TreeSet Example 5:

In this instance, we demonstrate a range of operations on a SortedSetSet.

FileName: TreeSet5.java

import java.util.*;

class TreeSet5{

 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]

Java TreeSet Example: Book

Consider an example using a TreeSet to store a collection of books and then displaying all the books in the set. It is important to note that the elements in a TreeSet must be of a Comparable type. By default, String and Wrapper classes are Comparable. However, if you want to add custom objects to a TreeSet, you must implement the Comparable interface.

FileName: TreeSetExample.java

import java.util.*;  

class Book implements Comparable<Book>{  

int id;  

String name,author,publisher;  

int quantity;  

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;  

}  

// implementing the abstract method

public int compareTo(Book b) {  

    if(id>b.id){  

        return 1;  

    }else if(id<b.id){  

        return -1;  

    }else{  

    return 0;  

    }  

}  

}  

public class TreeSetExample {  

public static void main(String[] args) {  

    Set<Book> set=new TreeSet<Book>();  

    //Creating Books  

    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 Communications & Networking","Forouzan","Mc Graw Hill",4);  

    //Adding Books to TreeSet  

    set.add(b1);  

    set.add(b2);  

    set.add(b3);  

    //Traversing TreeSet  

    for(Book b:set){  

    System.out.println(b.id+" "+b.name+" "+b.author+" "+b.publisher+" "+b.quantity);  

    }  

}  

}

Output:

101 Data Communications & Networking Forouzan Mc Graw Hill 4

121 Let us C Yashwant Kanetkar BPB 8

233 Operating System Galvin Wiley 6

ClassCast Exception in TreeSet

When an object of a class that does not implement the Comparable interface is added, it will result in a ClassCastException. Consider the code snippet below.

FileName: ClassCastExceptionTreeSet.java

// important import statement

import java.util.*;



class Employee

{

    

int empId;

String name;



// getting the name of the employee

String getName()

{

    return this.name;

}



// setting the name of the employee

void setName(String name)

{

this.name = name;

}



// setting the employee id 

// of the employee

void setId(int a)

{

this.empId = a;

}



// retrieving the employee id of

// the employee

int getId()

{

return this.empId;

}



}



public class ClassCastExceptionTreeSet

{



// main method

public static void main(String[] argvs)

{

// creating objects of the class Employee

Employee obj1 = new Employee();



Employee obj2 = new Employee();



TreeSet<Employee> ts =  new TreeSet<Employee>();



// adding the employee objects to 

// the TreeSet class

ts.add(obj1);

ts.add(obj2);



System.out.println("The program has been executed successfully.");



}

}

Output:

Exception in thread "main" java.lang.ClassCastException: class Employee cannot be cast to class java.lang.Comparable (Employee is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')

	at java.base/java.util.TreeMap.compare(TreeMap.java:1569)

	at java.base/java.util.TreeMap.addEntryToEmptyMap(TreeMap.java:776)

	at java.base/java.util.TreeMap.put(TreeMap.java:785)

	at java.base/java.util.TreeMap.put(TreeMap.java:534)

	at java.base/java.util.TreeSet.add(TreeSet.java:255)

	at ClassCastExceptionTreeSet.main(ClassCastExceptionTreeSet.java:52)

In the program mentioned above, implementing the Comparable interface is necessary. This is because TreeSet organizes elements in a specific order, requiring a way to compare the objects being added to it. This comparison is achieved by implementing the Comparable interface.

TreeSet Vs. HashSet