TreeSet: Sorted Set with Red-Black Tree
What you'll learn: How TreeSet maintains elements in sorted order automatically using a balanced tree structure for efficient operations.
What Is TreeSet?
TreeSet is a Set implementation that keeps its elements automatically sorted at all times. Unlike HashSet, which stores elements in no particular order, TreeSet organizes elements in their natural ordering (or by a custom comparator you provide).
Under the hood, TreeSet uses a red-black tree—a self-balancing binary search tree. This structure ensures that even as you add or remove elements, the tree stays balanced and operations remain efficient.
How It Works
Think of TreeSet like a library that alphabetizes books as you shelve them. Each time you add a new book, it's automatically placed in the correct sorted position. You don't need to sort the collection later—it's always maintained in order.
The red-black tree structure guarantees that searching, adding, and removing elements all take logarithmic time (O(log n)). This is slower than HashSet's average O(1) operations, but the trade-off is that your elements are always sorted.
TreeSet Requirements
Elements in a TreeSet must be comparable. They need to either:
- Implement the
Comparableinterface (likeString,Integer, etc.) - Or you provide a
Comparatorwhen creating theTreeSet
Without a way to compare elements, TreeSet can't maintain sorted order.
When to Choose TreeSet
Use TreeSet when you need a collection that:
- Contains no duplicates (it's a
Set) - Must always be sorted
- Requires efficient ordered operations (finding smallest/largest element, range queries)
Key Takeaway: TreeSet maintains unique elements in sorted order using a red-black tree, providing O(log n) performance for add, remove, and search operations—ideal when you need both uniqueness and automatic ordering.