java - TreeSet 最坏情况的时间复杂度是多少？

Question

据说here那个

TreeSet has a log(n) time complexity guarantuee for add()/remove()/contains().

但是TreeSet使用二叉搜索树，在最坏的情况下，二叉搜索树的高度可以是O(n)。 log(n) 复杂度如何“保证”？

Answer 1

该实现在插入时重新平衡树。

插入 的 O(lg n) 时间界限由 official documentation 保证。这不足为奇:实现集合的经典方法是某种 self-balancing binary search tree .

Java 库是公开可用的，所以让我们亲自去看看。可以找到TreeSet，例如 here 。它是按照 TreeMap 实现的，依次是 here 。正如@Don Roby 指出的，底层数据结构是红黑树。