java - TreeSet如何保持添加的O(logN)？

Question

Java TreeSet 类可以维持 add 方法的 O(logN) 成本。如果数据按排序顺序输入，这是如何工作的？

既然二叉搜索树的 add 方法在给定排序数据时会退化为 O(N)，为什么 TreeSet 不会发生这种情况？

Answer 1

您的错误是认为 TreeSet 使用简单二叉搜索树。
事实并非如此。它使用自平衡二叉搜索树。

TreeSet 的 Javadoc说:

A NavigableSet implementation based on a TreeMap.

TreeMap 的 Javadoc说:

A Red-Black tree based NavigableMap implementation. [...]

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.

因此，如果您想查看具体算法的描述，请找到该书并阅读它。

你也可以做一些research并查看红黑树是如何工作的，例如请参阅Wikipedia ，其中表示:

A red–black tree is a kind of self-balancing binary search tree in computer science.

[...]

The balancing of the tree is not perfect, but it is good enough to allow it to guarantee searching in O(log n) time, where n is the total number of elements in the tree. The insertion and deletion operations, along with the tree rearrangement and recoloring, are also performed in O(log n) time.

然后详细描述了这一切是如何工作的。