TreeSet in Java

Java provides a vast set of data structures for efficiently working with element collections. One such data structure is TreeSet, an implementation of a red-black tree in Java. TreeSet maintains a sorted order for storing unique elements. Beginners may find using Java TreeSet class a bit challenging initially. In this article, we’re going to figure out how to use TreeSet, explaining its core concepts and providing code examples to help you start incorporating TreeSet in your Java projects.

TreeSet structure: Red-Black tree

As we mentioned before, Java TreeSet class structure is implemented as a self-balancing binary search tree known as a Red-Black tree. Let’s explain what this is... A Red-Black Tree represents a balanced binary search data structure commonly employed to store and organize sorted data. It derives its name from the properties that maintain its balance:

Each node in the tree is red or black.
The root of the Red-Black tree is always black.
All leaf nodes (NIL nodes or null links) are black.
If a node of the tree is red, then its children are black.
Every simple path from a node to its descendant nodes contains an equal number of black nodes.

Red-black trees exhibit efficient performance for insertion, deletion, and element lookup operations by ensuring balance. This guarantees that the height of the tree remains proportional to the logarithm of the number of nodes it contains, resulting in logarithmic time complexity for operations. Red-black trees find wide applications in various domains, including the implementation of balanced search trees in programming languages, databases (e.g., internal index structures), and other scenarios where efficient storage and operations on sorted data are necessary.

Features and weaknesses of TreeSet

TreeSet provides several key features that make it a valuable tool for managing collections of objects in a sorted manner. Advantages:

Automatic maintenance of elements in sorted order. When adding or removing elements, the tree structure adjusts to keep them sorted. This eliminates the need for manual sorting and provides efficient access in ascending or descending order.
Efficient search, insert, and delete operations. It utilizes a binary search tree structure, enabling these operations with a time complexity of O(log N). Here N is the number of elements.
TreeSet guarantees the uniqueness of elements by utilizing their natural ordering or a custom Comparator. This is useful when working with collections that require distinct elements.

Limitations:

Slightly slower than HashSet due to maintaining sorted order.
Does not allow null elements, as it relies on natural ordering or a custom Comparator for element comparison.

Java TreeSet: example of main operations

Now let’s demonstrate how to create a TreeSet in Java, obtain the size of the collection, add elements into it, remove them from and check if an element is in the TreeSet. These code examples demonstrate the main operations when working with TreeSet: creating an instance, adding elements, removing elements, checking for element presence, and obtaining the size of the TreeSet. Creating a TreeSet instance and adding elements:

// Creating a TreeSet of Integer type
TreeSet<Integer> numbers = new TreeSet<>();

// Adding elements to the TreeSet
numbers.add(18);
numbers.add(2);
numbers.add(7);
numbers.add(28);

System.out.println(numbers); // Output: [2, 7, 18, 28]

Here we use the add() method to add 4 numbers in our TreeSet. If we create a main method and run the program, the output will be in sorted order (2, 7, 18, 28). Removing elements from TreeSet:

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

names.add("Johnny");
names.add("Ivy");
names.add("David");
names.add("Ricky");

// Removing an element from the TreeSet
names.remove("David");

System.out.println(names); // Output: [Ivy, Johnny, Ricky]

Checking for the presence of an element in TreeSet:

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

musicalInstrument.add("Piano");
musicalInstrument.add("Drums");
musicalInstrumentfruits.add("Violin");
musicalInstrument.add("Double Bass");

// Checking if an element exists in the TreeSet
boolean containsPiano = musicalInstrument.contains("Piano");
boolean containsCello = musicalInstrument.contains("Cello");

System.out.println(containsPiano); // Output: true
System.out.println(containsCello); // Output: false

Obtaining the size of TreeSet:

TreeSet<Character> letters = new TreeSet<>();

letters.add('A');
letters.add('B');
letters.add('C');
letters.add('D');

// Getting the size of the TreeSet
int size = letters.size();

System.out.println(size); // Output: 4

Sorting and Iterating in TreeSet

TreeSet in Java provides powerful features for sorting and iterating over collections of elements. In this section, we will explore various techniques for sorting elements, iterating over TreeSet, and performing range-based searches using subSet(), headSet(), and tailSet() methods. By default, TreeSet automatically maintains elements in sorted order. However, we can customize the sorting behavior by providing a Comparator during TreeSet creation. Let's see an example:

import java.util.Comparator;
import java.util.TreeSet;

public class TreeSetSortingExample {
  public static void main(String[] args) {
    // Create a TreeSet with custom sorting
    TreeSet<Integer> numbers = new TreeSet<>(Comparator.reverseOrder());

    // Add elements to the TreeSet
    numbers.add(5);
    numbers.add(3);
    numbers.add(7);
    numbers.add(1);

    System.out.println(numbers); // Output: [7, 5, 3, 1]
  }
}

In the above code, we create a TreeSet of Integer type and provide a custom Comparator using Comparator.reverseOrder() to sort the elements in descending order. The resulting TreeSet will contain elements [7, 5, 3, 1]. There are multiple ways to iterate over TreeSet. We can use an iterator or utilize the enhanced for-each loop. Let's see examples of both approaches:

import java.util.TreeSet;
import java.util.Iterator;

public class TreeSetIterationExample {
  public static void main(String[] args) {
    TreeSet<String> names = new TreeSet<>();

    names.add("Johnny");
    names.add("Ivy");
    names.add("Ricky");
    names.add("David");

    // Iterating using an iterator
    Iterator<String> iterator = names.iterator();
    while (iterator.hasNext()) {
      String name = iterator.next();
      System.out.println(name);
    }

    // Iterating using the enhanced for-each loop
    for (String name : names) {
      System.out.println(name);
    }
  }
}

In the above code, we create a TreeSet called names and add some elements. We then demonstrate two ways of iterating over the TreeSet: using an iterator and utilizing the enhanced for-each loop. TreeSet provides methods to perform range-based searches, allowing us to retrieve subsets of elements based on specific criteria. The three main methods for range-based searches are:

subSet(E fromElement, E toElement): Returns a subset of elements from fromElement (inclusive) to toElement (exclusive).
headSet(E toElement): Returns a subset of elements less than toElement.
tailSet(E fromElement): Returns a subset of elements greater than or equal to fromElement.

Let's see an example:

import java.util.TreeSet;

public class TreeSetRangeSearchExample {
  public static void main(String[] args) {
    TreeSet<Integer> numbers = new TreeSet<>();

    numbers.add(1);
    numbers.add(3);
    numbers.add(5);
    numbers.add(7);
    numbers.add(9);

    // Performing range-based search using subSet()
    TreeSet<Integer> subset = new TreeSet<>(numbers.subSet(3, 8));
    System.out.println(subset); // Output: [3, 5, 7]

    // Performing range-based search using headSet()
    TreeSet<Integer> headSet = new TreeSet<>(numbers.headSet(6));
    System.out.println(headSet); // Output: [1, 3, 5]

    // Performing range-based search using tailSet()
     TreeSet<Integer> tailSet = new TreeSet<>(numbers.tailSet(5));
    System.out.println(tailSet); // Output: [5, 7, 9]
  }
}

In the above code, we create a TreeSet called numbers and add some elements. We then demonstrate range-based searches using the subSet(), headSet(), and tailSet() methods.

The subset TreeSet contains elements between 3 (inclusive) and 8 (exclusive), which are [3, 5, 7].
The headSet TreeSet contains elements less than 6, which are [1, 3, 5].
The tailSet TreeSet contains elements greater than or equal to 5, which are [5, 7, 9].

These range-based search methods allow us to retrieve subsets of elements based on specific criteria, providing flexibility in working with sorted data.

Comparator in TreeSet: Sorting with Custom Criteria

Except for natural ordering, you can use a custom Comparator for sorting TreeSet. In this section, we will delve into the concept of a comparator and its role in TreeSet. We will explore how to create a TreeSet with a custom comparator and provide code examples to demonstrate sorting TreeSet based on specific criteria.

What is Comparator?

A Comparator is an interface in Java that allows custom sorting of objects. It provides a way to define the ordering of elements based on specific attributes or properties. By implementing the Comparator interface and overriding its compare() method, we can specify how elements should be sorted in a TreeSet.

Creating TreeSet with a Custom Comparator

To create a TreeSet with a custom comparator, we need to provide the comparator as an argument when creating the TreeSet instance. Let's see an example:

import java.util.Comparator;
import java.util.TreeSet;

public class TreeSetComparatorExample {
  public static void main(String[] args) {
    // Create a TreeSet with a custom comparator
    TreeSet<String> names = new TreeSet<>(new LengthComparator());

    // Add elements to the TreeSet
    names.add("Johnny");
    names.add("Ivy");
    names.add("Rick");
    names.add("David");

    System.out.println(names); // Output: [Ivy, Johnny, David, Rick]
  }
}

class LengthComparator implements Comparator<String> {
  @Override
  public int compare(String s1, String s2) {
    return Integer.compare(s1.length(), s2.length());
  }
}

In the above code, we create a TreeSet called names with a custom comparator called LengthComparator. The LengthComparator compares the length of two strings and sorts them accordingly. As a result, the TreeSet is sorted based on the length of the strings, giving us the output [Ivy, Rick, David, Johnny].

Examples of Sorting TreeSet using a Comparator

Besides creating a TreeSet with a custom comparator, we can also use a comparator to sort a TreeSet temporarily without modifying its natural ordering. Let's see an example:

import java.util.Comparator;
import java.util.TreeSet;

  public class TreeSetTest {
    public static void main(String[] args) {
      TreeSet<String> names = new TreeSet<>();

      names.add("Johnny");
      names.add("Ivy");
      names.add("Ricky");
      names.add("David");

      // Sort TreeSet temporarily using a comparator
      TreeSet<String> sortedNames = new TreeSet<>(Comparator.reverseOrder());
      sortedNames.addAll(names);

      System.out.println(sortedNames); // Output: [Ricky, Johnny, Ivy, David]
      System.out.println(names); // Output: [David, Ivy, Johnny, Ricky]
    }
  }

In the above code, we create a TreeSet called names and add some elements. We then create a new TreeSet called sortedNames with a custom comparator Comparator.reverseOrder(). By adding all elements from the original names TreeSet to the sortedNames, we obtain a temporary sorted version of the TreeSet.

Comparing TreeSet with Other Data Structures

Comparing TreeSet with HashSet

Both TreeSet and HashSet are implementations of the Set interface in Java. However, there are significant differences between them. TreeSet: TreeSet stores unique elements in sorted order. It uses a self-balancing binary search tree (usually a Red-Black Tree) to maintain the sorted order, resulting in logarithmic time complexity for operations like insertion, deletion, and search. TreeSet is efficient for maintaining a sorted collection and performing range-based operations. However, it has higher memory overhead due to the tree structure and does not allow null elements. HashSet: HashSet stores unique elements in an unordered manner using hash codes and hashtable internally. It provides constant time complexity for basic operations like insertion, deletion, and search. HashSet is efficient for fast element lookup and does not impose any additional memory overhead for maintaining order. However, it does not guarantee any specific ordering of elements.

When to Use TreeSet:

When you need to maintain elements in a sorted order automatically.
When you require range-based operations or need to find elements within a specific range efficiently.
When duplicate elements are not allowed and uniqueness is essential.
When you are willing to trade off slightly higher memory usage for the benefits of automatic sorting and range operations.

Comparing TreeSet with ArrayList

ArrayList is a dynamic array implementation in Java. Here are the key differences between TreeSet and ArrayList:

TreeSet: TreeSet stores unique elements in sorted order, providing efficient operations for maintaining a sorted collection and performing range-based searches. It has logarithmic time complexity for operations. TreeSet is not suitable for random access or maintaining the order of insertion.
ArrayList: ArrayList stores elements in the order of insertion, providing fast random access to elements using indices. It has constant time complexity for most operations when accessing elements by index. However, it has linear time complexity for inserting or removing elements from the middle of the list, as it requires shifting elements.

When to Consider Other Data Structures

If maintaining elements in a sorted order is not required, and you need a fast element lookup or an unordered collection, HashSet might be a better choice.
If you require frequent random access to elements by index or need to maintain the order of insertion, ArrayList would be more suitable.