Q31: How do TreeSet and TreeMap maintain sorted ordering?
TreeSet and TreeMap are backed by a Self-Balancing Red-Black Tree. They guarantee $O(log n)$ time complexity for add, remove, and contains operations. Elements are sorted either by natural ordering (Comparable) or an explicit Comparator passed at construction.
Key Takeaways
- Guarantees sorted element ordering using a Red-Black Tree.
- $O(log n)$ performance for insertion, lookup, and deletion.
Knowledge Check
What happens if you insert an object that does NOT implement Comparable into a default TreeSet?