TreeSet如何维护O（logN）以进行添加？

Question

Java TreeSet类可以为add方法维护O（logN）成本。如果数据按排序顺序输入，该如何工作？

由于给定排序的数据时，二叉搜索树的add方法将退化为O（N），为什么对于TreeSet不会发生这种情况？

Answer 1

TreeSet实现

基于NavigableSet。

NavigableSet的Javadoc说：

A

Red-Black tree

基于TreeMap实现。

此实现为TreeMap，TreeMap，TreeMap和NavigableMap操作提供了保证的log（n）时间成本。算法是对Cormen，Leiserson和Rivest的算法简介的改编。

因此，如果您想查看特定算法的描述，请找到该书并阅读。您还可以执行一些NavigableMap和

查找红黑树的工作方式

，例如在containsKey上显示：

树的平衡不是完美的，但是足以保证它在get时间内进行搜索，其中

n

是树中元素的总数。插入和删除操作以及树的重新排列和重新着色也都在put时间执行。remove

然后将详细介绍所有工作原理。