Why the search time for TreeSet is O(nlogn)?

Question

In my naive opinion it should be O(n) in worst case since Tree could get spindly and unbalanced.

Answer 1

TreeSet is based on TreeMap, which is a Red-Black Tree implementation. Red-Black Trees are self-balancing binary search trees that guarantee O(log n) performance for search, insert and delete operations.