Adding Elements: Sorted Insertion
What you'll learn: How TreeSet maintains sorted order automatically when you add elements, with O(log n) performance.
How Sorted Insertion Works
When you call add() on a TreeSet, it doesn't just append the element to the end like ArrayList does. Instead, TreeSet must find the correct position in its red-black tree structure to maintain sorted order.
The process works like this:
- TreeSet calls
compareTo()(from the Comparable interface) to compare your new element with existing elements - Starting at the root node, it navigates left or right through the tree based on comparison results
- When it finds the correct position (an empty spot), it inserts the new element as a leaf node
- The tree may rebalance itself to maintain red-black tree properties
Think of it like inserting a name into an alphabetically-sorted filing cabinet. You can't just shove the new file at the end—you must flip through until you find where it belongs alphabetically, then slide it into that exact spot.
Why O(log n) Performance?
Unlike ArrayList's O(n) insertion when adding in the middle, TreeSet achieves O(log n) because the tree's height grows logarithmically. In a balanced tree with 1,000 elements, you only need about 10 comparisons to find the insertion point—not 500 comparisons on average like you'd need scanning through an array.
TreeSet<Integer> numbers = new TreeSet<>();
numbers.add(5); // Becomes root
numbers.add(3); // Inserted left of 5
numbers.add(7); // Inserted right of 5
numbers.add(1); // Navigates down, inserted left of 3
// Tree maintains order automatically: 1, 3, 5, 7
Key Takeaway: TreeSet's add() operation automatically maintains sorted order by using compareTo() to navigate the tree structure, achieving O(log n) insertion performance regardless of where the element belongs in the sorted sequence.