TreeSet迭代的时间复杂度是什么？

Question

在我的代码中，Java TreeSet 迭代是占主导的时间因素。看系统，我认为它具有O(n)复杂度。有人能验证一下吗？

我认为通过从子节点向父节点提供链接，可以改善性能。

- John Smith

---

这个问题没有意义。听起来你是在说遍历你的TreeSet是O(n)。这是迭代的最佳方法 - 查看n个项目需要O(n)时间。如果你想让被迭代支配的代码更快，你需要改变算法，使它不进行迭代 - 例如，通过按键在树中查找（这将是O(log n)）。 - babbageclunk

Answer 1

TreeSet 的迭代当然是O(n)的，因为对于任何明智的树遍历算法而言都可以预期。

我在考虑通过提供从子节点到父节点的链接来提高性能。

TreeSet 是基于 TreeMap 实现的，而 TreeMap 已经具有这样的父引用。这是它所有归结到的方法:

private Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

- Michael Borgwardt

---

我认为关键点在于，不仅叶节点附有值。对于 n 个叶子节点，您确实有 O(n log n) 个节点，但也有 O(n log n) 个值。在实际情况下，我预计 O(n) 操作将主导 O(n log n) 操作。 - Tom Hawtin - tackline

我认为它应该是O(n)+O(logn)，因为如果您按顺序迭代，您必须首先使用log(n)次遍历来找到最左边或最右边的叶子节点，然后您有n个遍历来向后遍历树。因此，您具有O(n)？ 我的数学是否有道理？ - John Smith

@john：根据定义，O(n)+O(log n)与O(n)是相同的。 - Michael Borgwardt

@Tom：O(nlog n)严格大于O(n)，但不能说对于n个叶子节点，你有O(nlog n)个节点。对于一个有n个叶子节点的二叉树，它在第二低层有n/2个节点，在上一层有n/4个... 这是一个等比数列，总和为2n，也就是 O(n)。 - Michael Borgwardt

第二部分是正确的（但这是一个明显可能发生的错误！）。虽然O(n log n)的复杂度比O(n)更高，但对于实际的n值，后者执行O(n log n)和O(n)的时间可能会更长。 - Tom Hawtin - tackline

Answer 2

你有没有考虑在修改TreeSet时复制一份？如果主要时间花费在TreeSet迭代上（而不是修改），那么将TreeSet复制到数组或ArrayList中（仅在修改时）并仅对该数组/ArrayList进行迭代，可以几乎消除TreeSet迭代的成本。

- Peter Lawrey

---

或者使用Guava的ImmutableSortedSet，它是基于数组实现的。 - Kevin Bourrillion