Java TreeSet 类可以维持 add 方法的 O(logN) 成本。如果数据按排序顺序输入,这是如何工作的?
既然二叉搜索树的 add 方法在给定排序数据时会退化为 O(N),为什么 TreeSet 不会发生这种情况?
最佳答案
您的错误是认为 TreeSet
使用简单二叉搜索树。
事实并非如此。它使用自平衡二叉搜索树。
TreeSet
的 Javadoc说:
A
NavigableSet
implementation based on aTreeMap
.
TreeMap
的 Javadoc说:
A Red-Black tree based
NavigableMap
implementation. [...]This implementation provides guaranteed log(n) time cost for the
containsKey
,get
,put
andremove
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 inO(log n)
time.
然后详细描述了这一切是如何工作的。
关于java - TreeSet如何保持添加的O(logN)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58849584/