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

Question

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

• first()
• last()
• lower()
• higher()

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

Answer 1

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

• 要使 first() 和 last() 的时间复杂度为 O(1)，TreeSet 实现需要维护一个指向最左边的指针和树中最右边的叶节点。维护这些会为每次插入增加恒定成本，并且至少为每次删除增加恒定成本。实际上，该实现可能会动态找到最左/最右节点...这是一个 O(logN) 操作。

• lower() 和 higher() 方法必须执行与 get 相同的工作，因此 O(logN )。

当然，您可以自己检查源代码，看看实际发生了什么。 （正如其他人所做的那样：见下文。）

Answer 2

根据 TreeSet 默认使用的 TreeMap 的实现（sun jdk 1.6.0_23），看起来first()和last()都是O(log n)而不是O(1)：

 /**
 * Returns the first Entry in the TreeMap (according to the TreeMap's
 * key-sort function).  Returns null if the TreeMap is empty.
 */
final Entry<K,V> getFirstEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.left != null)
            p = p.left;
    return p;
}

/**
 * Returns the last Entry in the TreeMap (according to the TreeMap's
 * key-sort function).  Returns null if the TreeMap is empty.
 */
final Entry<K,V> getLastEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.right != null)
            p = p.right;
    return p;
}

Answer 3

其实我查了一下源码
在 http://developer.classpath.org/doc/java/util/ TreeSet-source.html，first()调用maps.firstKey()
然后在
http://developer.classpath.org/doc/java/util/TreeMap -source.html

393: public K firstKey()
394: (
395: if (root == nil)
396: throw new NoSuchElementException();
397: return firstNode().key;
398: )

并在firstNode()中，它执行while循环一直到左边

952: final Node<K, V> firstNode()
953: (
954: // Exploit fact that nil.left == nil.
955: Node node = root;
956: while (node.left != nil)
957: node = node.left;
958: return node;
959: )

Answer 4

这将取决于实施情况。我对JAVA不是很熟悉，但似乎所有这些操作都是遍历操作（获取最低元素，获取最高元素，获取下一个更高或下一个更低）。

如果树被实现为自平衡二叉搜索树，就像AVL 树，或任何其他类型的平衡树结构，您将看到平均情况每个操作的最坏情况为 O(log n) 时间，最好情况为 O(1)。

Answer 5

API 不提供任何保证，因为这些保证基于 trie 的标准模型。最好的情况是 O(1)，平均情况是 O(log n)，最坏情况是 O(n)。

从文档中：

此实现为基本操作（添加、删除和包含）提供有保证的 log(n) 时间成本。

这些不是您要求的功能，但请考虑一下 Java 将如何遍历 TreeSet。