The TreeSet Class – Collections: Part II

The TreeSet<E> Class

The TreeSet<E> class implements the NavigableSet<E> interface and thereby the SortedSet<E> interface. By default, operations on a sorted set rely on the natural ordering of the elements. However, a total ordering can be specified by passing a customized comparator to the constructor.

The TreeSet<E> class maintains non-null elements in sort order, and iteration is also in the same sort order.

The TreeSet<E> implementation uses balanced trees, which deliver excellent (logarithmic) performance for all operations. However, searching in a HashSet<E> can be faster than in a TreeSet<E> because hashing algorithms usually offer better performance than the search algorithms for balanced trees. The TreeSet<E> class is preferred if elements are to be maintained in sort order and if fast insertion and retrieval of individual elements is desired.

The TreeSet<E> class provides four constructors:

TreeSet()

The default constructor that creates a new, empty sorted set, according to the natural ordering of the elements.

Click here to view code image

TreeSet(Comparator<? super E> comparator)

A constructor that takes an explicit comparator for specific total ordering of the elements.

Click here to view code image

TreeSet(Collection<? extends E> collection)

A constructor that creates a sorted set based on a collection, according to the natural ordering of the elements.

TreeSet(SortedSet<E> set)

A constructor that creates a new set containing the same elements as the specified sorted set, with the same ordering.

Example 15.6 illustrates some selected navigation operations on a TreeSet<E>. Keep in mind that the Unicode values of uppercase letters are less than the Unicode values of lowercase letters—that is, the former occur before the latter in the Unicode standard.

The set is created at (1), and populated by calling the Collections.addAll() method at (2). The elements are maintained according to the natural ordering for Strings— that is, the one defined by the compareTo() method of the Comparable<String> interface implemented by the String class. The subset-view operations at (3) show how the bounds can be inclusive or exclusive. Note also how the closest-match methods at (4) behave. A sorted set with the reverse order corresponding to the natural ordering is created at (5). The methods pollFirst() and pollLast() remove the element that is retrieved—that is, they change the set structurally.

The following code shows how we can create a sorted set with a specific total ordering, by supplying a comparator in the constructor call:

Click here to view code image

  NavigableSet<String> strSetB = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
  Collections.addAll(strSetB, “strictly”, “dancing”, “Java”, “Ballroom”);
  System.out.println(strSetB);          // [Ballroom, dancing, Java, strictly]

Example 15.6 Using Navigable Sets

Click here to view code image

import java.util.Collections;
import java.util.NavigableSet;
import java.util.TreeSet;
import static java.lang.System.out;
public class SetNavigation {
  public static void main(String[] args) {
    NavigableSet<String> strSetA = new TreeSet<>();                         // (1)
    Collections.addAll(strSetA, “Strictly”, “Java”, “dancing”, “ballroom”); // (2)
    out.println(“Before: ” + strSetA);      // [Java, Strictly, ballroom, dancing]
    out.println(“\nSubset-views:”);                  // (3)
    out.println(strSetA.headSet(“ballroom”, true));  // [Java, Strictly, ballroom]
    out.println(strSetA.headSet(“ballroom”, false)); // [Java, Strictly]
    out.println(strSetA.tailSet(“Strictly”, true));  // [Strictly, ballroom,
                                                     //  dancing]
    out.println(strSetA.tailSet(“Strictly”, false)); // [ballroom, dancing]
    out.println(strSetA.subSet(“A”, false, “Z”, false )); // [Java, Strictly]
    out.println(strSetA.subSet(“a”, false, “z”, false )); // [ballroom, dancing]
    out.println(“\nClosest-matches:”);               // (4)
    out.println(strSetA.ceiling(“ball”));            // ballroom
    out.println(strSetA.floor(“ball”));              // Strictly
    out.println(strSetA.higher(“ballroom”));         // dancing
    out.println(strSetA.lower(“ballroom”));          // Strictly
    out.println(“\nReverse order:”);                 // (5)
    out.println(strSetA.descendingSet());   // [dancing, ballroom, Strictly, Java]
    out.println(“\nFirst-last elements:”);
    out.println(strSetA.pollFirst());                // Java
    out.println(strSetA.pollLast());                 // dancing

    out.println(“\nAfter: ” + strSetA);              // [Strictly, ballroom]
  }
}

Output from the program:

Click here to view code image

Before: [Java, Strictly, ballroom, dancing]
Subset-views:
[Java, Strictly, ballroom]
[Java, Strictly]
[Strictly, ballroom, dancing]
[ballroom, dancing]
[Java, Strictly]
[ballroom, dancing]
Closest-matches:
ballroom
Strictly
dancing
Strictly
Reverse order:
[dancing, ballroom, Strictly, Java]
First-last elements:
Java
dancing
After: [Strictly, ballroom]