Internal Working of TreeSet in Java

Introduction

A TreeSet in Java is a part of the java.util package and is used to store unique elements in sorted order. Unlike HashSet, which does not maintain order, TreeSet is implemented using a self-balancing Red-Black Tree, ensuring that elements are always stored in ascending order or a custom order defined by a comparator.

---

1. Data Structure Used

TreeSet is implemented using a TreeMap, which internally uses a Red-Black Tree to maintain order.

Implementation in Java:

public class TreeSet<E> extends AbstractSet<E> {
    private transient NavigableMap<E,Object> map;
}

• The map is an instance of TreeMap, which maintains sorted order.
• Elements are stored as keys, and a dummy object (PRESENT) is stored as values.

Internally, TreeMap maintains a Red-Black Tree, ensuring that elements remain sorted and operations execute efficiently.

---

2. How Elements are Stored and Accessed

Adding an Element

When add() is called:

1. The element is stored as a key in TreeMap.
2. The Red-Black Tree maintains sorted order.
3. If the element already exists, it is not inserted again.

Example:

TreeSet<String> set = new TreeSet<>();
set.add("Banana");
set.add("Apple");
set.add("Cherry");
System.out.println(set); // Output: [Apple, Banana, Cherry]

Retrieving an Element

Elements are accessed using iteration, sorted in natural order:

for (String item : set) {
    System.out.println(item);
}

Output:

Apple
Banana
Cherry

Unlike HashSet, where elements appear in unpredictable order, TreeSet guarantees sorted order.

Removing an Element

When remove() is called:

1. The key is removed from the TreeMap.
2. The Red-Black Tree restructures itself to maintain balance and order.

Example:

set.remove("Banana");
System.out.println(set); // Output: [Apple, Cherry]

---

3. Internal Working of TreeMap (Behind TreeSet)

How the TreeSet Uses TreeMap

• TreeMap maintains a Red-Black Tree, ensuring elements remain sorted.
• The tree structure allows operations like search, insert, and delete to execute in O(log n) time.

Node Structure in TreeMap

static final class Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left, right, parent;
    boolean color;
}

• left and right pointers maintain tree hierarchy.
• parent tracks the parent node.
• color ensures Red-Black Tree properties are maintained for balancing.

Red-Black Tree Properties

1. Every node is either red or black.
2. The root node is always black.
3. No two consecutive red nodes appear in a path.
4. Every path from the root to a leaf has the same number of black nodes.
5. Balancing operations (rotations and color flips) ensure O(log n) complexity.

---

4. Performance Analysis

Operation	Time Complexity
Add Element	O(log n)
Get Element	O(log n)
Remove Element	O(log n)
Iteration	O(n)

Comparison with HashSet and LinkedHashSet

Feature	TreeSet (Sorted)	LinkedHashSet (Ordered)	HashSet (Unordered)
Maintains Order	✅ Yes (Sorted)	✅ Yes (Insertion Order)	❌ No
Performance	⏳ Slower (O(log n))	⚡ Faster (O(1))	⚡ Fastest (O(1))
Best Use Case	Sorted Unique Elements	Ordered Unique Elements	Fastest Unique Lookup

---

5. Use Cases of TreeSet

1. Maintaining Sorted Data: When elements must always be in sorted order.
2. Efficient Range Queries: The subSet(), headSet(), and tailSet() methods allow retrieving elements in a given range.
3. Implementing Priority-Based Collections: Since elements are always sorted, TreeSet is useful in scenarios where priority-based retrieval is required.

Example: Range Queries

TreeSet<Integer> numbers = new TreeSet<>();
numbers.add(10);
numbers.add(20);
numbers.add(30);
numbers.add(40);
System.out.println(numbers.subSet(15, 35)); // Output: [20, 30]

---

6. Key Takeaways

✔ TreeSet is a SortedSet implementation backed by TreeMap.

✔ Uses a Red-Black Tree, ensuring O(log n) operations.

✔ Provides ordered traversal and range queries.

✔ Allows retrieving the first, last, and subsets efficiently.

✔ If a duplicate key is added, the old value is replaced.

✔ Slower than HashSet but useful when sorting is required.

Understanding the internal working of TreeSet helps in selecting the right data structure based on sorting requirements and performance needs.