java - TreeSet 中有序操作的时间复杂度是多少？

Question

java.util.TreeSet中下列操作的时间复杂度是多少？ ？

• first()
• last()
• 降低()
• higher()

我会假设这些是常数时间，但 API 不作任何保证。

Answer 1

实际上，我原以为这些操作对于一般实现来说都是O(logN)。

• 对于 first() 和 last() 是 O(1) TreeSet 实现需要维护一个指针分别到树中最左边和最右边的叶节点。维护这些会增加每次插入的恒定成本，并且至少会增加每次删除的恒定成本。实际上，该实现可能会即时找到最左边/最右边的节点……这是一个O(logN) 操作。

• lower() 和 higher() 方法必须完成与 get 相同的工作，因此是 O(logN).

当然，您可以自己查看源代码以了解实际情况。 (正如其他人所做的那样:见下文。)