TreeSet is a red-black tree data structure implementation of the NavigableSet interface based on a TreeMap. TreeSet is a part of the Java Collections Framework

TreeSet has the following features

  • Provides value-ordered iteration

  • Provides contains(Object), add(Object) and remove(Object) operations in log-time performance

  • Duplicated elements are ignored. Null element is not permitted, NullPointerException will be thrown when adding a null element

  • Elements are ordered and compared using their Comparable natural ordering, or by a Comparator (irrespective of equals and hashCode) provided at creation time, depending on which constructor is used

  • Unsynchronized implementation. In multi-threading environment with at least one thread modifies the list, it must be synchronized externally

Lets walk through this tutorial to explore them in more details

The TreeSet class hierarchy

TreeSet implements the NavigableSet interface. NavigableSet extends from SortedSet, Set, Collection and Iterable interfaces hierarchically

TreeSet vs HashSet and LinkedHashSet

TreeSet provides value-ordered iteration. TreeSet can be used to sort a HashSet or LinkedHashSet

HashSet has no ordering guarantees and run faster than TreeSet (constant-time vs log-time for most operations)

LinkedHashSet provides insertion-ordered iteration and run nearly as fast as HashSet

Declare a TreeSet

As a result from the class hierarchy, a TreeSet can be declared as the following ways

@Test
public void declare() {  
    NavigableSet<Integer> treeSet1 = new TreeSet<>();
    assertThat(treeSet1).isInstanceOf(TreeSet.class);

    TreeSet<Integer> treeSet2 = new TreeSet<>();
}

Create and Initialize with Comparable and Comparator

  • The created TreeSets from TreeSet() and TreeSet(Collection) constructors use Comparable natural ordering of the underlying objects

    In the following example, the iteration order of treeSet1 and treeSet2 decided by the Comparable natural ordering of Integer objects (ascending order), regardless of the given collection iterator order

@Test
public void initWithComparable() {  
    NavigableSet<Integer> treeSet1 = new TreeSet<>(Set.of(3, 1, 2));
    assertThat(treeSet1).containsExactly(1, 2, 3);

    NavigableSet<Integer> treeSet2 = new TreeSet<>();
    treeSet2.add(1);
    treeSet2.add(1); // duplicated element is ignored
    treeSet2.addAll(treeSet1);
    assertThat(treeSet2).containsExactly(1, 2, 3);
}
  • The created TreeSet from the TreeSet(Comparator) constructor has the iteration order based on the given Comparator
@Test
public void initWithComparator() {  
    NavigableSet<Integer> treeSet = new TreeSet<>(Comparator.reverseOrder());
    treeSet.addAll(List.of(1, 2, 3));

    assertThat(treeSet).containsExactly(3, 2, 1);
}

Learn more about Comparable and Comparator

Iterate a TreeSet

  • You can iterate a TreeSet by using either forEach(Consumer), since Java 8, or for-each and other index-loops (while, do-while, for-index)
@@Test
public void iterateWithForEachConsumer() {  
    NavigableSet<Integer> treeSet = new TreeSet<>(Set.of(3, 1, 2));
    treeSet.forEach(e -> System.out.printf("%d ", e));
}
  • Use iterator() and descendingIterator() to iterate a TreeSet in natural and reverse order, respectively
@Test
public void iterateWithIterator() {  
    NavigableSet<Integer> treeSet = new TreeSet<>(Set.of(1, 2, 3));

    Iterator<Integer> iterator = treeSet.iterator();
    while (iterator.hasNext()) {
        System.out.printf("%d ", iterator.next());
    }

    Iterator<Integer> descendingIterator = treeSet.descendingIterator();
    while (descendingIterator.hasNext()) {
        System.out.printf("%d ", descendingIterator.next());
    }
}

Retrieve and Filter

  • Retrieve the first and the last element from a TreeSet by using first() and last() methods

    Retrieve the reverse order view of the elements contained in a TreeSet by using descendingSet()

@Test
public void retrieve() {  
    NavigableSet<Integer> treeSet = new TreeSet<>(Set.of(3, 1, 2));
    int first = treeSet.first();
    assertThat(first).isEqualTo(1);

    int last = treeSet.last();
    assertThat(last).isEqualTo(3);

    NavigableSet<Integer> descendingSet = treeSet.descendingSet();
    assertThat(descendingSet).containsExactly(3, 2, 1);
}
  • You can also use iterator or Stream API to retrieve elements from a TreeSet

    The following example uses Stream API to get the first element by using findFirst() and filter elements by using filter(Predicate)

@Test
public void retrieveWithStreamAPI() {  
    NavigableSet<Integer> treeSet = new TreeSet<>(List.of(1, 2, 3));
    Integer firstElement = treeSet.stream().findFirst().orElse(null);
    assertThat(firstElement).isEqualTo(1);

    Integer[] elements = treeSet.stream().filter(e -> e >= 2).toArray(Integer[]::new);
    assertThat(elements).contains(2, 3);
}

Examine, Add, and Remove

  • TreeSet provides contains(Object), add(Object) and remove(Object) methods in log-time performance to examine if a TreeSet contains the specified element, add an element, and remove an element respectively
@Test
public void containsAddRemoveSingleElement() {  
    NavigableSet<Integer> treeSet = new TreeSet<>(Set.of(3, 1, 2));
    Boolean contained = treeSet.contains(3);
    assertThat(contained).isTrue();

    treeSet.add(4);
    treeSet.add(4);
    assertThatThrownBy(() -> treeSet.add(null)).isInstanceOf(NullPointerException.class);
    assertThat(treeSet).containsExactly(1, 2, 3, 4);

    treeSet.remove(3);
    assertThat(treeSet).containsExactly(1, 2, 4);
}
  • Bulk operations are also supported with containsAll, addAll, removeAll, Java 8+ removeIf
@Test
public void containsAddRemoveMultipleElements() {  
    NavigableSet<Integer> treeSet = new TreeSet<>(Set.of(3, 1, 2));
    Boolean contained = treeSet.containsAll(Set.of(1, 2));
    assertThat(contained).isTrue();

    treeSet.addAll(Set.of(3, 4, 5));
    assertThat(treeSet).containsExactly(1, 2, 3, 4, 5);

    treeSet.removeAll(Set.of(1, 2, 6));
    assertThat(treeSet).containsExactly(3, 4, 5);

    treeSet.removeIf(e -> e >= 4);
    assertThat(treeSet).contains(3);
}

Objects comparing in TreeSet

  • Internally, TreeSet basic operations such as contains, add and remove compare objects based on their Comparable or Comparator, regardless of their equals and hashCode, depending on which TreeSet constructor is used at the creation time

    In the following example, treeSet.contains(new Book(2, "a")) should return false but true, treeSet.add(new Book(2, "a")) should success but not and treeSet.remove(new Book(2, "a")) should not but success , due to the compareTo method of Book instances only compare title

@Test
public void objectsComparingProblem(){  
    TreeSet<Book> treeSet = new TreeSet<>();
    treeSet.add(new Book(1, "a"));

    Boolean contained = treeSet.contains(new Book(2, "a"));
    assertThat(contained).isTrue();

    treeSet.add(new Book(2, "a"));
    assertThat(treeSet).hasSize(1);

    treeSet.remove(new Book(2, "a"));
    assertThat(treeSet).isEmpty();
}

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

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

    int getId() {
        return id;
    }

    String getTitle() {
        return title;
    }

    @Override
    public int compareTo(Book o) {
        return CharSequence.compare(this.title, o.title);
    }
}
  • You can fix the above problem by comparing both id and title in compareTo as the below example
@Test
public void objectsComparingFixed(){  
    TreeSet<BookFixed> treeSet = new TreeSet<>();
    treeSet.add(new BookFixed(1, "a"));

    Boolean contained = treeSet.contains(new BookFixed(2, "a"));
    assertThat(contained).isFalse();

    treeSet.add(new BookFixed(2, "a"));
    assertThat(treeSet).hasSize(2);

    treeSet.remove(new BookFixed(2, "a"));
    assertThat(treeSet).hasSize(1);
}

static class BookFixed implements Comparable<BookFixed> {  
    int id;
    String title;

    BookFixed(int id, String title) {
        this.id = id;
        this.title = title;
    }

    int getId() {
        return id;
    }

    String getTitle() {
        return title;
    }

    @Override
    public int compareTo(BookFixed o) {
        return Comparator.comparing(BookFixed::getId)
            .thenComparing(BookFixed::getTitle)
            .compare(this, o);
    }
}

Conclusion

In this tutorial, we learned about TreeSet features, class hierarchy and operations. You can find below the full source code