java - 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 の反復に (変更ではなく) 費やされている場合は、TreeSet を配列または ArrayList にコピーし (変更された場合のみ)、この配列/ArrayList を反復処理するだけで、TreeSet 反復のコストをほとんどなくすことができます。