Java TreeSet class

by

The Java TreeSet class is a collection that represents a set of unique elements in a sorted order. It is implemented using a tree structure, specifically a Red-Black Tree, which ensures that elements are stored in a sorted order and that operations like adding, removing, and searching for elements can be performed in logarithmic time.

Here are some key features of the TreeSet class:

  1. Unique elements: The TreeSet class contains only unique elements. If you try to add a duplicate element, it will simply be ignored.
  2. Sorted order: The elements in a TreeSet are stored in a sorted order. You can specify a Comparator object when creating the TreeSet to define a custom sort order, or use the natural ordering of the elements if they implement the Comparable interface.
  3. Logarithmic time complexity: The TreeSet provides efficient performance for basic operations like add, remove, and contains, with a time complexity of O(log n).
  4. Not thread-safe: The TreeSet class is not thread-safe, meaning that it is not designed to be used by multiple threads concurrently without proper synchronization.

Here’s an example of how to use the TreeSet class to create a set of integers:

import java.util.*;

public class TreeSetExample {
    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>();
        set.add(5);
        set.add(3);
        set.add(9);
        System.out.println(set); // prints [3, 5, 9]
    }
}

In this example, we create a TreeSet of integers, add three elements to it, and then print the contents of the set. The output shows that the elements are stored in a sorted order.

Internal Working of The TreeSet Class:

The internal working of the TreeSet class is based on a self-balancing binary search tree data structure called a Red-Black Tree. This data structure guarantees that the operations on the TreeSet class, such as add, remove, and contains, have a time complexity of O(log n) on average.

When an element is added to the TreeSet, it is inserted into the tree according to the natural ordering of the elements or the order specified by the Comparator object passed to the TreeSet constructor. The Red-Black Tree algorithm then reorganizes the tree to maintain the tree’s balance and ensure the tree remains a valid binary search tree.

The Red-Black Tree has some specific rules that must be followed to maintain the balance of the tree:

  1. Each node is either red or black.
  2. The root node is always black.
  3. If a node is red, its children must be black.
  4. Every path from a given node to any of its descendant null nodes must contain the same number of black nodes.

By following these rules, the Red-Black Tree ensures that the tree remains balanced and has a height of O(log n), which is important for achieving the O(log n) time complexity of the TreeSet operations.

When searching for an element in the TreeSet, the algorithm starts at the root of the tree and traverses down the tree to find the element. Since the elements are sorted, the search can quickly determine whether the element is in the TreeSet by comparing the element with the current node and traversing down the appropriate branch of the tree.

Similarly, when removing an element from the TreeSet, the algorithm starts at the root of the tree and traverses down the tree to find the element. Once the element is found, it is removed from the tree and the Red-Black Tree algorithm is used to rebalance the tree if necessary.

In summary, the TreeSet class uses a Red-Black Tree data structure to maintain a sorted set of unique elements and provides efficient performance for operations like add, remove, and contains. The Red-Black Tree algorithm ensures that the TreeSet remains balanced, which allows for O(log n) time complexity on average.

Synchronization of The TreeSet Class:

The TreeSet class is not thread-safe by default, meaning that it is not designed to be used by multiple threads concurrently without proper synchronization. If multiple threads modify a TreeSet concurrently, the TreeSet may become corrupted, leading to unexpected behavior and potentially causing the program to crash.

To ensure thread safety when using a TreeSet in a concurrent environment, you can use one of the following approaches:

  1. Synchronize access to the TreeSet: You can synchronize access to the TreeSet by using the synchronized keyword or by using a synchronized block to ensure that only one thread can modify the TreeSet at a time. For example:
Set<String> synchronizedSet = Collections.synchronizedSet(new TreeSet<String>());

This creates a synchronized set based on a TreeSet that can be safely used in a concurrent environment.

  1. Use a concurrent set implementation: Alternatively, you can use a concurrent set implementation such as the ConcurrentSkipListSet or the CopyOnWriteArraySet, which are designed to be used in concurrent environments without requiring explicit synchronization. These classes use different data structures and algorithms to ensure thread safety.

Here is an example of using the ConcurrentSkipListSet class:

ConcurrentSkipListSet<Integer> concurrentSet = new ConcurrentSkipListSet<>();
concurrentSet.add(5);
concurrentSet.add(3);
concurrentSet.add(9);
System.out.println(concurrentSet); // prints [3, 5, 9]

In this example, we create a ConcurrentSkipListSet of integers, add three elements to it, and then print the contents of the set. The output shows that the elements are stored in a sorted order.

In summary, to ensure thread safety when using a TreeSet in a concurrent environment, you can either synchronize access to the TreeSet or use a concurrent set implementation such as ConcurrentSkipListSet or CopyOnWriteArraySet.

Hierarchy of TreeSet class:

The TreeSet class is part of the Java Collections Framework and is located in the java.util package. It implements the SortedSet interface, which extends the Set interface and defines a set that maintains its elements in a sorted order.

Here is the hierarchy of the TreeSet class and its related interfaces and classes:

java.lang.Object
    |
    +--java.util.AbstractCollection
           |
           +--java.util.AbstractSet
                  |
                  +--java.util.TreeSet

As you can see, the TreeSet class extends the AbstractSet class, which in turn extends the AbstractCollection class. The AbstractSet class provides a skeletal implementation of the Set interface and the AbstractCollection class provides a skeletal implementation of the Collection interface.

The TreeSet class implements the NavigableSet interface, which extends the SortedSet interface and defines navigation methods for accessing elements in the set. The NavigableSet interface in turn extends the SortedSet interface, which extends the Set interface and defines a set that maintains its elements in a sorted order.

Here is the hierarchy of the interfaces implemented by the TreeSet class:

java.util.Set
    |
    +--java.util.SortedSet
          |
          +--java.util.NavigableSet
                |
                +--java.util.TreeSet

In summary, the TreeSet class implements the SortedSet and NavigableSet interfaces and extends the AbstractSet class. It provides a sorted set of unique elements and maintains its elements in a sorted order based on the natural ordering of the elements or the order specified by a Comparator object.

TreeSet Class Declaration:

The declaration of the TreeSet class in Java is as follows:

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

Let’s break down this declaration to understand what it means:

  • public: The access modifier specifies that the TreeSet class can be accessed from any other class in the same package or from a different package.
  • class: The keyword that indicates that this is a class definition.
  • TreeSet<E>: The name of the class, with a type parameter <E> that specifies the type of elements that the TreeSet can hold. The <E> is a generic type parameter that is replaced with an actual type when an instance of the class is created.
  • extends AbstractSet<E>: The TreeSet class extends the AbstractSet class, which provides a skeletal implementation of the Set interface.
  • implements NavigableSet<E>, Cloneable, Serializable: The TreeSet class implements the NavigableSet interface, which extends the SortedSet interface and provides navigation methods for accessing elements in the set. The TreeSet class also implements the Cloneable and Serializable interfaces, which allow the class to be cloned and serialized.

In summary, the TreeSet class is a generic class that extends the AbstractSet class and implements the NavigableSet interface along with the Cloneable and Serializable interfaces. It provides a sorted set of unique elements and maintains its elements in a sorted order based on the natural ordering of the elements or the order specified by a Comparator object.

Constructors of Java TreeSet Class:

The TreeSet class in Java provides several constructors to create TreeSet objects with different initial values and configurations. Here are the constructors of the TreeSet class:

  1. TreeSet(): Creates an empty TreeSet with natural ordering of elements.
  2. TreeSet(Collection<? extends E> c): Creates a TreeSet containing the elements of the specified collection c, sorted according to their natural ordering.
  3. TreeSet(Comparator<? super E> comparator): Creates an empty TreeSet with the specified Comparator to order its elements.
  4. TreeSet(SortedSet<E> s): Creates a TreeSet containing the same elements and using the same ordering as the specified SortedSet s.

Let’s see some code examples to understand the usage of these constructors:

// Example 1: Creating an empty TreeSet
TreeSet<String> treeSet1 = new TreeSet<String>();

// Example 2: Creating a TreeSet from a collection with natural ordering
List<Integer> list = Arrays.asList(5, 1, 3, 2, 4);
TreeSet<Integer> treeSet2 = new TreeSet<Integer>(list);

// Example 3: Creating a TreeSet with a custom Comparator
Comparator<String> comparator = new Comparator<String>() {
    public int compare(String s1, String s2) {
        return s1.length() - s2.length();
    }
};
TreeSet<String> treeSet3 = new TreeSet<String>(comparator);

// Example 4: Creating a TreeSet from a SortedSet
SortedSet<Double> sortedSet = new TreeSet<Double>(Arrays.asList(1.0, 3.0, 2.0));
TreeSet<Double> treeSet4 = new TreeSet<Double>(sortedSet);

In the first example, an empty TreeSet is created with natural ordering of elements. In the second example, a TreeSet is created from a collection of integers, and its elements are sorted based on their natural ordering. In the third example, a TreeSet is created with a custom Comparator that sorts elements based on their string length. In the fourth example, a TreeSet is created from a SortedSet with the same ordering.

In summary, the TreeSet class provides several constructors that allow you to create a TreeSet object with different initial values and configurations, including empty sets, sets containing specified elements, and sets with custom Comparators or with the same ordering as another SortedSet.

Methods of Java TreeSet Class:

The TreeSet class in Java provides a rich set of methods to manipulate the elements in the set and to perform various operations on the set. Here are the main methods provided by the TreeSet class:

  1. boolean add(E e): Adds the specified element to the set if it is not already present.
  2. boolean addAll(Collection<? extends E> c): Adds all of the elements in the specified collection to the set if they are not already present.
  3. void clear(): Removes all of the elements from the set.
  4. Object clone(): Returns a shallow copy of the set.
  5. Comparator<? super E> comparator(): Returns the Comparator used to order the elements in the set, or null if the set uses the natural ordering of its elements.
  6. boolean contains(Object o): Returns true if the set contains the specified element.
  7. Iterator<E> descendingIterator(): Returns an iterator over the elements in the set in descending order.
  8. NavigableSet<E> descendingSet(): Returns a NavigableSet containing the elements in the set in descending order.
  9. E first(): Returns the first (lowest) element in the set.
  10. E floor(E e): Returns the greatest element in the set less than or equal to the specified element, or null if there is no such element.
  11. SortedSet<E> headSet(E toElement): Returns a SortedSet containing the elements in the set that are strictly less than the specified element.
  12. NavigableSet<E> headSet(E toElement, boolean inclusive): Returns a NavigableSet containing the elements in the set that are less than (or equal to, if inclusive is true) the specified element.
  13. E higher(E e): Returns the least element in the set greater than the specified element, or null if there is no such element.
  14. boolean isEmpty(): Returns true if the set contains no elements.
  15. Iterator<E> iterator(): Returns an iterator over the elements in the set in ascending order.
  16. E last(): Returns the last (highest) element in the set.
  17. E lower(E e): Returns the greatest element in the set less than the specified element, or null if there is no such element.
  18. E pollFirst(): Removes and returns the first (lowest) element in the set, or returns null if the set is empty.
  19. E pollLast(): Removes and returns the last (highest) element in the set, or returns null if the set is empty.
  20. boolean remove(Object o): Removes the specified element from the set if it is present.
  21. int size(): Returns the number of elements in the set.
  22. SortedSet<E> subSet(E fromElement, E toElement): Returns a SortedSet containing the elements in the set that are greater than or equal to the specified fromElement and strictly less than the specified toElement.
  23. NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive): Returns a NavigableSet containing the elements in the set that are greater than (or equal to, if fromInclusive is true) the specified fromElement and less than (or equal to, if toInclusive is true) the specified toElement.
  24. SortedSet<E> tailSet(E fromElement): Returns a SortedSet containing the elements in the set that are greater than or equal to the specified element.
  25. NavigableSet<E> tailSet(E fromElement, boolean inclusive): Returns a NavigableSet

Java TreeSet Examples:

Here are some examples of using the TreeSet class in Java:

  1. Adding elements to a TreeSet and iterating over them in ascending order:
TreeSet<String> treeSet = new TreeSet<>();
treeSet.add("apple");
treeSet.add("banana");
treeSet.add("orange");

for (String fruit : treeSet) {
    System.out.println(fruit);
}

Output:

apple
banana
orange
  1. Creating a TreeSet with a custom comparator to sort elements in descending order:
TreeSet<Integer> treeSet = new TreeSet<>(Collections.reverseOrder());
treeSet.add(3);
treeSet.add(1);
treeSet.add(2);

for (int num : treeSet) {
    System.out.println(num);
}

Output:

3
2
1
  1. Using the subSet method to get a subset of a TreeSet:
TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(1);
treeSet.add(2);
treeSet.add(3);
treeSet.add(4);
treeSet.add(5);

SortedSet<Integer> subset = treeSet.subSet(2, 4);
System.out.println(subset);

Output:

[2, 3]
  1. Removing an element from a TreeSet:
TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(1);
treeSet.add(2);
treeSet.add(3);

treeSet.remove(2);

System.out.println(treeSet);

Output:

[1, 3]

Java TreeSet Example: Book

Here’s an example of using the TreeSet class in Java to create a collection of Book objects and sorting them based on their titles:

import java.util.*;

class Book implements Comparable<Book> {
    private int id;
    private String title;
    private String author;

    public Book(int id, String title, String author) {
        this.id = id;
        this.title = title;
        this.author = author;
    }

    public int getId() {
        return id;
    }

    public String getTitle() {
        return title;
    }

    public String getAuthor() {
        return author;
    }

    @Override
    public int compareTo(Book other) {
        return title.compareTo(other.title);
    }

    @Override
    public String toString() {
        return "Book [id=" + id + ", title=" + title + ", author=" + author + "]";
    }
}

public class TreeSetExample {
    public static void main(String[] args) {
        TreeSet<Book> books = new TreeSet<>();
        books.add(new Book(1, "To Kill a Mockingbird", "Harper Lee"));
        books.add(new Book(2, "The Great Gatsby", "F. Scott Fitzgerald"));
        books.add(new Book(3, "One Hundred Years of Solitude", "Gabriel Garcia Marquez"));
        books.add(new Book(4, "1984", "George Orwell"));
        books.add(new Book(5, "Brave New World", "Aldous Huxley"));
        books.add(new Book(6, "Pride and Prejudice", "Jane Austen"));

        for (Book book : books) {
            System.out.println(book);
        }
    }
}

Output:

Book [id=5, title=Brave New World, author=Aldous Huxley]
Book [id=1, title=To Kill a Mockingbird, author=Harper Lee]
Book [id=6, title=Pride and Prejudice, author=Jane Austen]
Book [id=4, title=1984, author=George Orwell]
Book [id=2, title=The Great Gatsby, author=F. Scott Fitzgerald]
Book [id=3, title=One Hundred Years of Solitude, author=Gabriel Garcia Marquez]

As you can see, the books are sorted based on their titles in ascending order. The Book class implements the Comparable interface and overrides the compareTo method to specify the sorting order based on the title of the books. The TreeSet class uses this method to maintain the elements in sorted order.

ClassCast Exception in TreeSet:

A ClassCastException in a TreeSet occurs when you try to add elements of incompatible types to the TreeSet, or when you try to retrieve an element from the TreeSet and cast it to a type that is not compatible with the actual type of the element.

For example, let’s say you have a TreeSet of Integers and you try to add a String object to it:

TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(1);
treeSet.add("two"); // This line will cause a ClassCastException

This will result in a ClassCastException at runtime, since the TreeSet is expecting elements of type Integer, but you’re trying to add a String object.

Similarly, if you try to retrieve an element from the TreeSet and cast it to a type that is not compatible with the actual type of the element, you’ll get a ClassCastException. For example:

TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(1);
treeSet.add(2);
treeSet.add(3);

String str = (String) treeSet.first(); // This line will cause a ClassCastException

In this case, we’re trying to retrieve the first element from the TreeSet and cast it to a String, but the actual type of the first element is Integer. This will result in a ClassCastException at runtime.

To avoid ClassCastException in TreeSet, make sure that you only add elements of the same type to the TreeSet, and be careful when retrieving elements and casting them to a different type.