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

Question

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

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

我会假设这些是恒定的时间，但 API 不做任何保证。

Answer 1

实际上，我原以为这些操作都将O(logN)用于一般实现。

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

• 和方法必须做与因此相同lower()的工作。higher()getO(logN)

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

Answer 2

看起来 first() 和 last() 都将是 O(log n) 而不是 O(1)，基于 TreeMap 默认使用的 TreeMap 的 Implentation(sun jdk 1.6.0_23)：

 /**
 * 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

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

从文档中：

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

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

Answer 5

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

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