TreeSet中有序操作的时间复杂度是什么？

Question

以下是在java.util.TreeSet中以下操作的时间复杂度：

• first()：O(log n)
• last()：O(log n)
• lower()：O(log n)
• higher()：O(log n)

尽管API没有做出保证，但我认为这些操作的时间复杂度都是对数时间。

- signalseeker

Answer 1

实际上，我认为对于一般实现而言，这些操作都将是O(logN)。

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

• lower()和higher()方法必须执行与get相同的操作，因此它们的时间复杂度也是O(logN)。

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

- Stephen C

---

我看了一下源代码，但它太抽象了。我不确定第一个和最后一个在哪里实现。得再看看。 - signalseeker

TreeSet 内部使用 TreeMap 实现，因此大部分逻辑在 TreeMap.get[First|Last|Lower|Higher]Entry() 中。所有这些操作都需要遍历树来查找节点，所以 Stephen C 是正确的，时间复杂度为 O(log N)。 - SimonC

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;
}

- Shailesh

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: )

- daRuleBreaker

Answer 4

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

从文档中可以看到：

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

虽然这些不是您要求的函数，但请考虑 Java 如何遍历 TreeSet。

- atx

---

哈哈，是的，不过现在已经修好了 ;) - atx

Answer 5

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

如果树被实现为自平衡二叉搜索树，例如AVL树或任何其他平衡树结构，则每个操作的平均情况和最坏情况时间复杂度为O(log n)，最好情况为O(1)。

- ProdigySim

---

但是实现被指定为红黑树，因此它不依赖于实现。 - user207421