TreeSet in Java

In Java, the TreeSet class is a part of the java.util package and implements the Set interface, which means it does not allow duplicate elements. It is a collection that stores unique elements in a sorted order, based on their natural ordering or a specified comparator. The underlying data structure that makes the TreeSet class work is a Red-Black Tree, which is a balanced binary search tree. This tree structure ensures that the elements are always sorted and provides efficient operations for insertion, deletion, and retrieval of elements. TreeSet in Java offers a sorted, unique collection with fast search and navigation, ideal for managing ordered data efficiently for modern tasks

In this article, we will explore the definition, constructors, internal workings, methods, performance characteristics, and user-defined TreeSets in Java.

Definition of TreeSet

The TreeSet class is a NavigableSet that extends the AbstractSet class and implements the Set interface. It does not allow duplicates and stores elements in a sorted order, meaning that when you iterate over a TreeSet, the elements are returned in ascending order (by default). A TreeSet can also be customized to use a specific sorting order by providing a Comparator during the creation of the set.

A TreeSet is particularly useful when you need to maintain a sorted collection of unique elements, and when operations such as searching, adding, and removing elements need to be efficient.

Constructors of TreeSet

The TreeSet class provides several constructors, allowing for different initialization options. Here are the main constructors:

1. 1. TreeSet()
   This constructor creates an empty TreeSet that uses the natural ordering of its elements (i.e., elements must be Comparable).
2. 2. TreeSet<Integer> treeSet = new TreeSet<>();
3. 3. TreeSet(Comparator<? super E> comparator)
   This constructor creates a TreeSet that uses the specified comparator for ordering the elements.
4. 4. TreeSet<Integer> treeSet = new TreeSet<>(Comparator.reverseOrder());
5. 5. TreeSet(Collection<? extends E> c)
   This constructor creates a TreeSet initialized with the elements of the specified collection. The elements are sorted according to their natural ordering or by a comparator, if provided.
6. 6. List<Integer> list = Arrays.asList(1, 2, 3);
7. 7. TreeSet<Integer> treeSet = new TreeSet<>(list);
8. 8. TreeSet(SortedSet<E> s)
   This constructor creates a TreeSet that contains the elements of the specified SortedSet and maintains their order.
9. 9. SortedSet<Integer> sortedSet = new TreeSet<>();
10. 10. TreeSet<Integer> treeSet = new TreeSet<>(sortedSet);

Internal Working of TreeSet

Internally, a TreeSet uses a Red-Black Tree to store its elements. The Red-Black Tree is a balanced binary search tree that ensures that the tree remains balanced after every insertion and deletion operation. This helps guarantee logarithmic time complexity for most operations, such as adding, removing, and searching for elements.

A Red-Black Tree maintains the following properties:

• • Every node is either red or black.
• • The root is always black.
• • Every leaf (NIL) is black.
• • No two red nodes can be next to each other; hence, any offspring of a red node must be black. 
• • The number of black nodes on each path from a node to its descendant leaves is the same.

These properties ensure that the height of the tree is always O(log n), leading to efficient time complexity for operations such as adding, deleting, and searching elements.

When an element is added to the TreeSet, it is inserted into the Red-Black Tree according to its ordering, and the tree is adjusted to maintain the balance. The sorting of the elements is based on their natural order or a comparator provided during the initialization of the TreeSet.

TreeSet Methods

The TreeSet class provides a rich set of methods that help in performing various operations. Some of the commonly used methods are:

1. 1. add(E e)
       If the given element is not already in the set, it is added.  The element is inserted in a sorted order.

treeSet.add(10);

1. 2. remove(Object o)
   Removes the specified element from the set if it exists.

treeSet.remove(10);

1. 3. contains(Object o)
   Returns true if the given element is present in the set.
2. boolean isPresent = treeSet.contains(10);
3.  
4. 4. size()
   Returns the number of elements in the set.

int size = treeSet.size();

1. 5. isEmpty()
   Returns true if the set contains no elements.

boolean isEmpty = treeSet.isEmpty();

1. 6. clear()
   Removes all elements from the set.

treeSet.clear();

1. 7. first()
   Returns the first (lowest) element in the set.

Integer firstElement = treeSet.first();

1. 8. last()
   Returns the last (highest) element in the set.

Integer lastElement = treeSet.last();

1. 9. pollFirst()
   Removes and returns the first (lowest) element in the set.

Integer first = treeSet.pollFirst();

1. 10. pollLast()
   Removes and returns the last (highest) element in the set.

Integer last = treeSet.pollLast();

1. 11. subSet(E fromElement, E toElement)
   Returns a view of the portion of this set whose elements range from fromElement to toElement, excluding the element toElement.

SortedSet<Integer> subset = treeSet.subSet(10, 20);

1. 12. headSet(E toElement)
   Returns a view of the portion of this set whose elements are less than toElement.

SortedSet<Integer> headSet = treeSet.headSet(20);

1. 13. tailSet(E fromElement)
   Returns a view of the portion of this set whose elements are greater than or equal to fromElement.

SortedSet<Integer> tailSet = treeSet.tailSet(10);

1. 14. iterator()
   Returns an iterator over the elements in the set in ascending order.

       Iterator<Integer> iterator = treeSet.iterator();

User-Defined TreeSet Example with Custom Class (Actor)

import java.util.*;

// User-defined class

class Actor {

    int id;

    String name;

    String movie;

    public Actor(int id, String name, String movie) {

        this.id = id;

        this.name = name;

        this.movie = movie;

    }

    @Override

    public String toString() {

        return "Actor{id=" + id + ", name='" + name + "', movie='" + movie + "'}";

    }

}

public class TreeSetActorExample {

    public static void main(String[] args) {

        // Comparator to sort Actors by ID

        Comparator<Actor> sortById = new Comparator<Actor>() {

            @Override

            public int compare(Actor a1, Actor a2) {

                return Integer.compare(a1.id, a2.id);

            }

        };

        // Creating TreeSet of Actor with custom Comparator

        TreeSet<Actor> actorSet = new TreeSet<>(sortById);

        actorSet.add(new Actor(3, "Vijay", "Leo"));

        actorSet.add(new Actor(1, "Prabhas", "Salaar"));

        actorSet.add(new Actor(2, "Yash", "KGF"));

        actorSet.add(new Actor(4, "Rajinikanth", "Jailer"));

        // Display TreeSet

        for (Actor a : actorSet) {

            System.out.println(a);

        }

    }

}

Performance of TreeSet

The performance of TreeSet is largely influenced by the underlying Red-Black Tree data structure. Since the Red-Black Tree maintains a balanced structure, most operations on the TreeSet have a time complexity of O(log n), where n is the number of elements in the set. This includes:

• • Insertion (add(E e))
• • Deletion (remove(Object o))
• • Searching (contains(Object o))

However, operations that require traversal, such as iterating over the set or getting subsets, will typically involve visiting all elements, which has a time complexity of O(n) in the worst case.

Key Performance Characteristics:

• • Insertion: O(log n)
• • Deletion: O(log n)
• • Search (Contains): O(log n)
• • Accessing elements: O(n) for iterating
• • Memory Complexity: O(n) for storing n elements

Conclusion

The TreeSet class in Java is a powerful and efficient collection for managing unique elements in a sorted order. It ensures that the elements are sorted either by their natural order or by a custom comparator, providing flexibility. The underlying Red-Black Tree structure guarantees efficient operations, with most operations having a time complexity of O(log n). The TreeSet is ideal for scenarios where ordering and uniqueness are essential, and its ability to offer efficient search, insertion, and removal operations makes it a valuable tool in Java development.

Do visit our channel to explore more:  SevenMentor