Java provides a vast set of data structures for efficiently working with element collections. One such data structure is TreeSet, an implementation of a red-black tree in Java. TreeSet maintains a sorted order for storing unique elements.
Beginners may find using Java TreeSet class a bit challenging initially. In this article, we’re going to figure out how to use TreeSet, explaining its core concepts and providing code examples to help you start incorporating TreeSet in your Java projects.
TreeSet structure: Red-Black tree
As we mentioned before, Java TreeSet class structure is implemented as a self-balancing binary search tree known as a Red-Black tree. Let’s explain what this is...
A Red-Black Tree represents a balanced binary search data structure commonly employed to store and organize sorted data. It derives its name from the properties that maintain its balance:
Each node in the tree is red or black.
The root of the Red-Black tree is always black.
All leaf nodes (NIL nodes or null links) are black.
If a node of the tree is red, then its children are black.
Every simple path from a node to its descendant nodes contains an equal number of black nodes.
Red-black trees exhibit efficient performance for insertion, deletion, and element lookup operations by ensuring balance. This guarantees that the height of the tree remains proportional to the logarithm of the number of nodes it contains, resulting in logarithmic time complexity for operations.
Red-black trees find wide applications in various domains, including the implementation of balanced search trees in programming languages, databases (e.g., internal index structures), and other scenarios where efficient storage and operations on sorted data are necessary.
Features and weaknesses of TreeSet
TreeSet provides several key features that make it a valuable tool for managing collections of objects in a sorted manner.
Advantages:
Automatic maintenance of elements in sorted order. When adding or removing elements, the tree structure adjusts to keep them sorted. This eliminates the need for manual sorting and provides efficient access in ascending or descending order.
Efficient search, insert, and delete operations. It utilizes a binary search tree structure, enabling these operations with a time complexity of O(log N). Here N is the number of elements.
TreeSet guarantees the uniqueness of elements by utilizing their natural ordering or a custom Comparator. This is useful when working with collections that require distinct elements.
Limitations:
Slightly slower than HashSet due to maintaining sorted order.
Does not allow null elements, as it relies on natural ordering or a custom Comparator for element comparison.
Java TreeSet: example of main operations
Now let’s demonstrate how to create a TreeSet in Java, obtain the size of the collection, add elements into it, remove them from and check if an element is in the TreeSet. These code examples demonstrate the main operations when working with TreeSet: creating an instance, adding elements, removing elements, checking for element presence, and obtaining the size of the TreeSet.
Creating a TreeSet instance and adding elements:
// Creating a TreeSet of Integer type
TreeSet<Integer> numbers = new TreeSet<>();
// Adding elements to the TreeSet
numbers.add(18);
numbers.add(2);
numbers.add(7);
numbers.add(28);
System.out.println(numbers); // Output: [2, 7, 18, 28]
Here we use the add() method to add 4 numbers in our TreeSet. If we create a main method and run the program, the output will be in sorted order (2, 7, 18, 28).
Removing elements from TreeSet:
TreeSet<String> names = new TreeSet<>();
names.add("Johnny");
names.add("Ivy");
names.add("David");
names.add("Ricky");
// Removing an element from the TreeSet
names.remove("David");
System.out.println(names); // Output: [Ivy, Johnny, Ricky]
Checking for the presence of an element in TreeSet:
TreeSet<String> musicalInstrument = new TreeSet<>();
musicalInstrument.add("Piano");
musicalInstrument.add("Drums");
musicalInstrumentfruits.add("Violin");
musicalInstrument.add("Double Bass");
// Checking if an element exists in the TreeSet
boolean containsPiano = musicalInstrument.contains("Piano");
boolean containsCello = musicalInstrument.contains("Cello");
System.out.println(containsPiano); // Output: true
System.out.println(containsCello); // Output: false
Obtaining the size of TreeSet:
TreeSet<Character> letters = new TreeSet<>();
letters.add('A');
letters.add('B');
letters.add('C');
letters.add('D');
// Getting the size of the TreeSet
int size = letters.size();
System.out.println(size); // Output: 4
Sorting and Iterating in TreeSet
TreeSet in Java provides powerful features for sorting and iterating over collections of elements. In this section, we will explore various techniques for sorting elements, iterating over TreeSet, and performing range-based searches using subSet(), headSet(), and tailSet() methods.
By default, TreeSet automatically maintains elements in sorted order. However, we can customize the sorting behavior by providing a Comparator during TreeSet creation. Let's see an example:
import java.util.Comparator;
import java.util.TreeSet;
public class TreeSetSortingExample {
public static void main(String[] args) {
// Create a TreeSet with custom sorting
TreeSet<Integer> numbers = new TreeSet<>(Comparator.reverseOrder());
// Add elements to the TreeSet
numbers.add(5);
numbers.add(3);
numbers.add(7);
numbers.add(1);
System.out.println(numbers); // Output: [7, 5, 3, 1]
}
}
In the above code, we create a TreeSet of Integer type and provide a custom Comparator using Comparator.reverseOrder() to sort the elements in descending order. The resulting TreeSet will contain elements [7, 5, 3, 1].
There are multiple ways to iterate over TreeSet. We can use an iterator or utilize the enhanced for-each loop. Let's see examples of both approaches:
import java.util.TreeSet;
import java.util.Iterator;
public class TreeSetIterationExample {
public static void main(String[] args) {
TreeSet<String> names = new TreeSet<>();
names.add("Johnny");
names.add("Ivy");
names.add("Ricky");
names.add("David");
// Iterating using an iterator
Iterator<String> iterator = names.iterator();
while (iterator.hasNext()) {
String name = iterator.next();
System.out.println(name);
}
// Iterating using the enhanced for-each loop
for (String name : names) {
System.out.println(name);
}
}
}
In the above code, we create a TreeSet called names and add some elements. We then demonstrate two ways of iterating over the TreeSet: using an iterator and utilizing the enhanced for-each loop.
TreeSet provides methods to perform range-based searches, allowing us to retrieve subsets of elements based on specific criteria. The three main methods for range-based searches are:
subSet(E fromElement, E toElement): Returns a subset of elements from fromElement (inclusive) to toElement (exclusive).
headSet(E toElement): Returns a subset of elements less than toElement.
tailSet(E fromElement): Returns a subset of elements greater than or equal to fromElement.
Let's see an example:
import java.util.TreeSet;
public class TreeSetRangeSearchExample {
public static void main(String[] args) {
TreeSet<Integer> numbers = new TreeSet<>();
numbers.add(1);
numbers.add(3);
numbers.add(5);
numbers.add(7);
numbers.add(9);
// Performing range-based search using subSet()
TreeSet<Integer> subset = new TreeSet<>(numbers.subSet(3, 8));
System.out.println(subset); // Output: [3, 5, 7]
// Performing range-based search using headSet()
TreeSet<Integer> headSet = new TreeSet<>(numbers.headSet(6));
System.out.println(headSet); // Output: [1, 3, 5]
// Performing range-based search using tailSet()
TreeSet<Integer> tailSet = new TreeSet<>(numbers.tailSet(5));
System.out.println(tailSet); // Output: [5, 7, 9]
}
}
In the above code, we create a TreeSet called numbers and add some elements. We then demonstrate range-based searches using the subSet(), headSet(), and tailSet() methods.
The subsetTreeSet contains elements between 3 (inclusive) and 8 (exclusive), which are [3, 5, 7].
The headSetTreeSet contains elements less than 6, which are [1, 3, 5].
The tailSetTreeSet contains elements greater than or equal to 5, which are [5, 7, 9].
These range-based search methods allow us to retrieve subsets of elements based on specific criteria, providing flexibility in working with sorted data.
Methods for Navigation
You’ve learned the basics of using TreeSet to store and retrieve elements in sorted order. But did you know TreeSet has some very handy navigation methods to find elements quickly without iterating over the entire set? Let’s dive into these methods and see them in action.
Getting the First and Last Elements
The first() method returns the smallest (or “lowest”) element in the TreeSet, while last() returns the largest (or “highest”). Perfect for when you want to grab boundary elements instantly.
import java.util.TreeSet;
public class TreeSetFirstLastExample {
public static void main(String[] args) {
TreeSet numbers = new TreeSet<>();
numbers.add(10);
numbers.add(40);
numbers.add(20);
numbers.add(30);
System.out.println(\"TreeSet: \" + numbers);
System.out.println(\"First Element: \" + numbers.first());
System.out.println(\"Last Element: \" + numbers.last());
}
}
first() and last() are O(log n) operations, since TreeSet is backed by a tree structure. That's still pretty efficient for retrieving boundary elements.
Finding Elements with ceiling(), floor(), higher(), and lower()
When you need to find the closest match to a given value, these methods are a lifesaver:
ceiling(e) returns the smallest element greater than or equal to e. floor(e) returns the largest element less than or equal to e. higher(e) returns the smallest element strictly greater than e. lower(e) returns the largest element strictly less than e.
These methods are super helpful for quick lookups, like finding the next available time slot in a schedule or retrieving the closest priced item in a sorted list of prices.
Removing Elements with pollFirst() and pollLast()
Need to remove the smallest or largest element immediately? pollFirst() removes and returns the first element, while pollLast() does the same for the last element.
import java.util.TreeSet;
public class TreeSetPollExample {
public static void main(String[] args) {
TreeSet numbers = new TreeSet<>();
numbers.add(5);
numbers.add(15);
numbers.add(25);
System.out.println(\"TreeSet before polling: \" + numbers);
int first = numbers.pollFirst(); // Removes 5
System.out.println(\"Polled first: \" + first);
System.out.println(\"TreeSet now: \" + numbers);
int last = numbers.pollLast(); // Removes 25
System.out.println(\"Polled last: \" + last);
System.out.println(\"TreeSet now: \" + numbers);
}
}
These methods come in handy for scenarios where you want to maintain a sorted collection but also remove boundary elements on demand, like a min-heap or max-heap simulation.
Comparator in TreeSet: Sorting with Custom Criteria
Except for natural ordering, you can use a custom Comparator for sorting TreeSet. In this section, we will delve into the concept of a comparator and its role in TreeSet. We will explore how to create a TreeSet with a custom comparator and provide code examples to demonstrate sorting TreeSet based on specific criteria.
What is Comparator?
A Comparator is an interface in Java that allows custom sorting of objects. It provides a way to define the ordering of elements based on specific attributes or properties. By implementing the Comparator interface and overriding its compare() method, we can specify how elements should be sorted in a TreeSet.
Creating TreeSet with a Custom Comparator
To create a TreeSet with a custom comparator, we need to provide the comparator as an argument when creating the TreeSet instance. Let's see an example:
import java.util.Comparator;
import java.util.TreeSet;
public class TreeSetComparatorExample {
public static void main(String[] args) {
// Create a TreeSet with a custom comparator
TreeSet<String> names = new TreeSet<>(new LengthComparator());
// Add elements to the TreeSet
names.add("Johnny");
names.add("Ivy");
names.add("Rick");
names.add("David");
System.out.println(names); // Output: [Ivy, Johnny, David, Rick]
}
}
class LengthComparator implements Comparator<String> {
@Override
public int compare(String s1, String s2) {
return Integer.compare(s1.length(), s2.length());
}
}
In the above code, we create a TreeSet called names with a custom comparator called LengthComparator. The LengthComparator compares the length of two strings and sorts them accordingly. As a result, the TreeSet is sorted based on the length of the strings, giving us the output [Ivy, Rick, David, Johnny].
Examples of Sorting TreeSet using a Comparator
Besides creating a TreeSet with a custom comparator, we can also use a comparator to sort a TreeSet temporarily without modifying its natural ordering. Let's see an example:
import java.util.Comparator;
import java.util.TreeSet;
public class TreeSetTest {
public static void main(String[] args) {
TreeSet<String> names = new TreeSet<>();
names.add("Johnny");
names.add("Ivy");
names.add("Ricky");
names.add("David");
// Sort TreeSet temporarily using a comparator
TreeSet<String> sortedNames = new TreeSet<>(Comparator.reverseOrder());
sortedNames.addAll(names);
System.out.println(sortedNames); // Output: [Ricky, Johnny, Ivy, David]
System.out.println(names); // Output: [David, Ivy, Johnny, Ricky]
}
}
In the above code, we create a TreeSet called names and add some elements. We then create a new TreeSet called sortedNames with a custom comparator Comparator.reverseOrder(). By adding all elements from the original names TreeSet to the sortedNames, we obtain a temporary sorted version of the TreeSet.
Comparing TreeSet with Other Data Structures
Comparing TreeSet with HashSet
Both TreeSet and HashSet are implementations of the Set interface in Java. However, there are significant differences between them.
TreeSet: TreeSet stores unique elements in sorted order. It uses a self-balancing binary search tree (usually a Red-Black Tree) to maintain the sorted order, resulting in logarithmic time complexity for operations like insertion, deletion, and search. TreeSet is efficient for maintaining a sorted collection and performing range-based operations. However, it has higher memory overhead due to the tree structure and does not allow null elements.
HashSet: HashSet stores unique elements in an unordered manner using hash codes and hashtable internally. It provides constant time complexity for basic operations like insertion, deletion, and search. HashSet is efficient for fast element lookup and does not impose any additional memory overhead for maintaining order. However, it does not guarantee any specific ordering of elements.
When to Use TreeSet:
When you need to maintain elements in a sorted order automatically.
When you require range-based operations or need to find elements within a specific range efficiently.
When duplicate elements are not allowed and uniqueness is essential.
When you are willing to trade off slightly higher memory usage for the benefits of automatic sorting and range operations.
Comparing TreeSet with ArrayList
ArrayList is a dynamic array implementation in Java. Here are the key differences between TreeSet and ArrayList:
TreeSet: TreeSet stores unique elements in sorted order, providing efficient operations for maintaining a sorted collection and performing range-based searches. It has logarithmic time complexity for operations. TreeSet is not suitable for random access or maintaining the order of insertion.
ArrayList: ArrayList stores elements in the order of insertion, providing fast random access to elements using indices. It has constant time complexity for most operations when accessing elements by index. However, it has linear time complexity for inserting or removing elements from the middle of the list, as it requires shifting elements.
When to Consider Other Data Structures
If maintaining elements in a sorted order is not required, and you need a fast element lookup or an unordered collection, HashSet might be a better choice.
If you require frequent random access to elements by index or need to maintain the order of insertion, ArrayList would be more suitable.
GO TO FULL VERSION