TreeSet is a red-black tree data structure implementation of the NavigableSet interface. TreeSet is a part of the Java Collections Framework and 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
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 andtreeSet.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