TreeSet in Java: A Comprehensive Guide

TreeSet is an implementation of the SortedSet interface in Java, which uses a tree-based data structure for storage. It is one of the most efficient data structures for storing large amounts of sorted data and performing operations on it. The ordering of the elements is maintained by a set using their natural ordering. This must be consistent with equals if it is to correctly implement the Set interface.

Working of TreeSet

The TreeSet uses a self-balancing binary search tree like Red-Black Tree for maintaining the elements in a sorted order. Therefore, the operations like add, remove, and search takes O(log(N)) time. In a self-balancing tree, it is made sure that the height of the tree is always O(log(N)) for all the operations.

Example 1:

Let's have a look at a code snippet to understand how to add, contain, and iterate through elements in TreeSet.

csharp
import java.util.*;

class TreeSetExample {

    public static void main(String[] args)
    { 
        TreeSet<String> s = new TreeSet<String>();
        s.add("gfg");
        s.add("courses");
        s.add("ide");
        System.out.println(s);
        System.out.println(s.contains("ide"));
        Iterator<String> i = s.iterator();
        while(i.hasNext())
            System.out.println(i.next());
    }
}

Output:

csharp
[courses, gfg, ide]
true
courses
gfg
ide

In the above example, we created an empty TreeSet, added some elements using the add() method, displayed the TreeSet in a sorted order, checked whether "ide" is present in the TreeSet or not, and used the iterator to traverse through the TreeSet.

Example 2:

Let's have a look at a code snippet to understand how to remove and traverse elements in TreeSet using the for-each loop.

csharp
import java.util.*;

class TreeSetExample {

    public static void main(String[] args)
    { 
        TreeSet<Integer> s = new TreeSet<Integer>();
        s.add(10);
        s.add(5);
        s.add(2);
        s.add(15);
        s.remove(5);
        for(Integer x:s)
            System.out.print(x + " ");
    }
}

Output:

2 10 15

In the above example, we created an empty TreeSet, added some elements using the add() method, removed 5 from the TreeSet, and traversed the TreeSet using the for-each loop.

Functions common to both TreeSet and HashSet:

Method	Description	Time Complexity
add(Object o)	This method will add the specified element according to the same sorting order mentioned during the creation of the TreeSet. Duplicate entires will not get added.	O(log n)
contains(Object o)	This method will return true if given element is present in TreeSet else it will return false.	O(log n)
remove(Object o)	This method is used to return a specific element from the set.	O(log n)
size()	This method is used to return the size of the set or the number of elements present in the set.	O(1)
isEmpty()	This method is used to return true if this set contains no elements or is empty and false for the opposite case.	O(1)
Iterator iterator()	Returns an iterator for iterating over the elements of the set.

Functions present only in TreeSet:

Method	Description	Time Complexity
lower(E e)	This method returns the greatest element in this set strictly less than the given element, or null if there is no such element.	O(log n)
higher(E e)	The higher(E e) method returns the least element in this set strictly greater than the given element, or null if there is no such element. This method has a time complexity of O(log n), where n is the size of the set.

Here's how it works:

1. If the set is empty, return null.
2. If the given element e is greater than or equal to the last element in the set, return null, because there is no element in the set that is strictly greater than e.
3. Otherwise, use the ceiling() method to find the least element in the set that is greater than or equal to e.
4. If the element returned by ceiling() is equal to e, use the higher() method recursively with the next element in the set. Otherwise, return the element returned by ceiling().

Here's the code:

kotlin
public E higher(E e) {
    if (isEmpty() || comparator.compare(e, last()) >= 0) {
        return null;
    }
    E ceiling = ceiling(e);
    if (ceiling != null && comparator.compare(ceiling, e) == 0) {
        return higher(ceiling);
    }
    return ceiling;
}

Note that this implementation uses the ceiling() method, which returns the least element in the set that is greater than or equal to the given element. The ceiling() method also has a time complexity of O(log n).