TreeSet迭代的时间复杂度是多少？

Question

在我的代码中，Java TreeSet 迭代是占主导地位的时间因素。在观察这个系统时，我相信它的复杂度是 O(n) 。任何人都可以验证这一点吗？

我认为通过提供从子节点到父节点的向后链接我可以提高性能。

Answer 1

TreeSet 迭代当然是 O(n)，正如任何合理的树遍历算法所期望的那样。

我认为通过提供链接
从子节点向后到父节点
节点我可以提高性能。

TreeMap（TreeSet 所基于的）已经有这样的父引用。这就是方法：

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

Answer 2

您是否考虑过在更改 TreeSet 时获取其副本？如果主要时间花在 TreeSet 迭代（而不是修改它）上，那么将 TreeSet 复制到数组或 ArrayList（仅在更改时）并且仅迭代此数组/ArrayList 几乎可以消除 TreeSet 迭代的成本。