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:
| Method | Description |
| 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’. |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
//Sample 01: Package Required import java.util.Iterator; import java.util.SortedSet; import java.util.TreeSet; //Sample 02: Create Set SortedSet<Integer> set = new TreeSet<Integer>(); //Insertion Order is Not Maintained set.add(4); set.add(5); set.add(8); set.add(9); set.add(2); set.add(3); set.add(6); set.add(0); set.add(1); |
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.
|
1 2 3 4 5 6 7 8 9 10 |
//Sample 03: Traverse and Print the the Tree private static void printTree(SortedSet<Integer> set) { Iterator<Integer> itr = set.iterator(); while (itr.hasNext()) System.out.print(itr.next() + ","); System.out.println(); } //Sample 04: Print the Tree printTree(set); |
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:
|
1 2 3 |
//Sample 05: Get First and Last Element in the Tree System.out.println("First Element: " + set.first()); System.out.println("Last Element: " + set.last()); |
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.
|
1 2 3 4 5 6 7 8 9 10 11 |
//Sample 06: Elements less than 5 SortedSet<Integer> HeadSet = set.headSet(5); printTree(HeadSet); //Sample 07: Element bigger than 5 SortedSet<Integer> TailSet = set.tailSet(5); printTree(TailSet); //Sample 08: Elements between 3 & 8 SortedSet<Integer> SubSet = set.subSet(3, 8); printTree(SubSet); |
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:
|
1 2 3 4 5 6 7 8 9 |
//Sample 09: Check an Element Present //[More Efficient. We will see it in separate video] System.out.println("Is Element 5 Present: " + set.contains(5)); System.out.println("Is Element 7 Present: " + set.contains(7)); //Sample 10: Clear All the Elements set.clear(); |
5. Watch TreetSet Example as YouTube Demo
6. TreetSet Complete Code Example
TreeSetNumber.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
//Sample 01: Package Required import java.util.Iterator; import java.util.SortedSet; import java.util.TreeSet; public class TreeSetNumber { public static void main(String[] args) { //Sample 02: Create Set SortedSet<Integer> set = new TreeSet<Integer>(); //Insertion Order is Not Maintained set.add(4); set.add(5); set.add(8); set.add(9); set.add(2); set.add(3); set.add(6); set.add(0); set.add(1); //Sample 03: Print the Tree printTree(set); //Sample 04: Get First and Last Element in the Tree System.out.println("First Element: " + set.first()); System.out.println("Last Element: " + set.last()); //Sample 05: Elements less than 5 SortedSet<Integer> HeadSet = set.headSet(5); printTree(HeadSet); //Sample 06: Element bigger than 5 SortedSet<Integer> TailSet = set.tailSet(5); printTree(TailSet); //Sample 07: Elements between 3 & 8 SortedSet<Integer> SubSet = set.subSet(3, 8); printTree(SubSet); //Sample 08: Check an Element Present //[More Efficient. We will see it in separate video] System.out.println("Is Element 5 Present: " + set.contains(5)); System.out.println("Is Element 7 Present: " + set.contains(7)); //Sample 09: Clear All the Elements set.clear(); } //Sample 02: Traverse and Print the the Tree private static void printTree(SortedSet<Integer> set) { Iterator<Integer> itr = set.iterator(); while (itr.hasNext()) System.out.print(itr.next() + ","); System.out.println(); } } |
Categories: Java
Tags: contains, first, headSet, last, SortedSet, subSet, tailSet, TreeSet
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.