Java TreeSet and SortedSet Interface

Java TreeSet & SortedSet Explained

1. Java TreeSet Class and SortedSet Interface Overview

The Java TreeSet class implements the SortedSet Interface. Before we move on to the TreeSet Collection class, we will study about the SortedSet interface and functionality it offers. Set interface is base for SortedSet interface, and a SortedSet gives all the functionality of the Set interface. We once saw the Set interface when we leant about the HashSet in HashSet Example. On top of the Set’s unique items claim, the SortedSet claims for Element Ordering.

Since SortedSet perform sorting, it needs to know how to compare two elements and say which one is big. Java types String and Boxed types Integer, Double etc. provide these comparisons via the Comparable Interface.

2. SortedSet Interface Methods

In this example, we are going to try Java TreeSet which implements SortedSet. So, first we will learn the frequently used methods in the SortedSet Interface. The below table lists those methods along with the description:

MethodDescription
E first()Returns First Element in the SortedSet.
E last()Returns Last Element in the SortedSet.
SortedSet<E> HeadSet(E to)Returns SortedSet in which all elements are lesser than the ‘to’ element.
SortedSet<E> TailSet(E from)Returns SortedSet in which all elements are higher than the ‘from’ element or equal to ‘from’ element.
SortedSet<E> SubSet(E from, E to)Returns SortedSet which is between ‘from’ & ‘to’.
SortedSet Interface Methods (Most Used)
Java TreeSet and SortedSet Interface
Java TreeSet and SortedSet Interface

3. Java TreeSet Collection Class

Java’s TreeSet class implements both Set and SortedSet interfaces. The Set interface make sure the items are unique in the TreeSet. Whereas, the SortedSet signifies that the collection items are sorted in either ascending or descending order. In TreeSet searching an item is highly efficient with Log(n) response time. Here, ‘n’ stands for the number of items kept in the TreeSet.

While storing the item TreeSet makes use of the Binary Tree data structure. It also makes sure the Binary Tree is balanced. We will learn the Binary Tree & how TreeSet balances it in a special example. Here in this example, we learn the basic operations on the TreeSet Java Class. Now, we will create our example.

4. Java TreeSet Example

4.1 Create TreeSet & Print Via Iterator

First, we create the TreeSet (Line 7) instance and store the reference as SortedSet type. This means we will operate our TreeSet as Sorted Collection. After creating the TreeSet, we add items to it. Here, each item is a standard integer data type. Below is the code:

Next, we write a function called printTree which iterates through our TreeSet and prints each element in it. At line no 3, we retrieve the Iterator over the TreeSet and loop through each element through it. Since TreeSet keeps its collection items in Binary Tree format, retrieving the element requires binary tree traversal. But this complexity is hidden behind the Iterator instance itr. For us, it is a simple loop which uses the hasNext and next methods of the iterator. In the program main (Line 10), we call this custom printTree function.

4.2 First and Last Items

We can get first and last element from the TreeSet using first and last methods. Recall, TreeSet represents the items in the sorted order. Let us say the TreeSet is sorting the items in ascending order. Then the first method will return the smallest item, and last method will return the largest item. The code is below:

4.3 headSet, tailSet & subSet

There are three functions to retrieve the sub-set. These subsets we get are a TreeSet and we can use the same printTree method to iterate through it.

These methods are:

  • headSet
  • tailSet
  • subset

All the above method takes a collection item and returns a subset. In Section 4.1, we added some integers randomly and they will be kept in a sorted order as here: 0,1,2,3,4,5,6,8,9. Note: 7 we missed for a reason. You can also note the TreeSet is ordering these items in ascending order.

When we pass 5 to the headSet method, it returns a sub-tree set which represents all the items lesser than 5. The same way we can call tailSet to get all elements greater than 5. The subset call is slightly different. It takes two arguments. For example, if we pass 3,8 to it, we get sub-tree representing all the items in between 3-8. The below code example makes a call to all these functions to see how it works.

4.4 Search for a Specific Element – contains

The real beauty of TreeSet is searching for a specific element. The binary tree formation greatly reduces the search time. We will study about the search in a separate article. Below is the usage of contains method which search for a specific element in the TreeSet:

5. Watch TreetSet Example as YouTube Demo

6. TreetSet Complete Code Example

TreeSetNumber.java

Do you like this Example? Please comment about it for others!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.