HelloKoding

Practical coding guides

TreeSet in Java

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

Java TreeSet Hierarchy

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. A 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
  • TreeSet is not thread-safe as it is an unsynchronized implementation. In multi-threading environment with at least one thread modifies the list, it must be synchronized externally
  • Internally, TreeSet uses a TreeMap instance to store and retrieve its elements

Let’s walk through this tutorial to explore them in more details

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

TreeSetTest.java

package com.hellokoding.java.collections;

import org.junit.Test;

import java.util.*;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

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

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

    @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);
    }

    @Test
    public void initWithComparator() {
        NavigableSet<Integer> treeSet = new TreeSet<>(Comparator.reverseOrder());
        treeSet.addAll(List.of(1, 2, 3));

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

    @Test
    public void iterateWithForEachConsumer() {
        NavigableSet<Integer> treeSet = new TreeSet<>(Set.of(3, 1, 2));
        treeSet.forEach(e -> System.out.printf("%d ", e));
    }

    @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());
        }
    }

    @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);
    }

    @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);
    }

    @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);
    }

    @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);
    }

    @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);
        }
    }

    @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);
        }
    }
}
Follow HelloKoding