java树集迭代的时间复杂度是多少？

Question

在我的代码中，Java TreeSet迭代是主要的时间因素。从这个系统来看，我认为它是O（n）复杂的。有人能证实这一点吗

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

Answer 1

TreeSet迭代当然是O（n），这可以从任何合理的树行走算法中预期

I am thinking that by providing links backward from child node to parent node I could improve the performance.

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复制到一个数组或ArrayList（仅在更改时）并且仅在该数组/ArrayList上迭代几乎可以减少TreeSet迭代的成本