ツリーのノードで等価クラスを構築するための良いデータ構造は何ですか？

Question

私はツリーのノードに等価クラスを構築するための良いデータ構造を探しています。理想的な構造では、以下の動作は、（必要に応じてO（1）/ O（n））を高速で（謎のコードのない段落）容易にすべきである：

• （A）ルートからツリーをウォーク。各ノード上で - >子遷移は、子ノード
• （B）は、2つの同値クラスマージのすべての同等のバージョンを列挙
• （C）既存のノード（子供）と他のデータ
のリストから新しいノードを作成します
• （D）ノードと構造的に同等なノードを見つけます（つまり、同じ数の子を持ち、対応する子が同じ等価クラスに属し、「その他のデータ」が等しい）。

これまでのところ、私は考えました（いくつかは組み合わせて使用​​できます）：

• 子供がノードではなくノードの集合への参照である場合、パフェ。 （A）が高速であり、（B）ツリーを歩いてノードを更新してマージされたコレクションを指すようにする必要がある、（C）新しいノードの各子を含むコレクションを見つける必要がある、（D）木を歩くことが必要です
• それらの特性によってノードのハッシュこれにより（D）ははるかに高速ですが（B）遅くなります（等価クラスがマージされたときにハッシュが更新される必要があるため）
• ノードを循環リンクリストにまとめます。 （A）が速い、（B）速いが、循環リストの "マージ"部分が実際にリスト（C）を分割するのは速く、（D）は木を歩く必要があるという事実のためである。
• 上記と同様ですが、各ノードに追加の "up"ポインタがあり、これを使用して循環リストの正規メンバーを見つけることができます。

私は甘い選択肢がありませんか？

Answer 1

あなたは対処する2つの等価な形式を持っているようです。最新の状態に保たれている等価クラスとして追跡されている平等な等価性（A）と、構造的等価性（D）。これは、時には等価クラスを作成してそれを放棄することがあります。

プレーンなものと構造的なものの両方の等価クラスを維持すると、問題が概念的に簡単になるように聞こえます。それが構造的な等価性のためにあまりに多くのチャーンを導入するならば、構造的な等価性のいくつかの側面について等価クラスを維持することができます。これらの等価クラスのメンテナンスを行う余裕がありますが、構造的に同等のノードのリストを作成する際に検討するノードの数を大幅に削減することができます。

Answer 2

あなたの問題を解決する構造はありませんが、Disjoint-set data structureをご覧ください。結局、等価クラスは集合の分割と同じことです。これらの操作の一部を迅速に処理できるはずです。

Answer 3

すぐに戻って、私は木を全く使わないことを勧めます。前回同様の問題に直面しなければならなかった時、私は木で始めましたが、後に配列に移動しました。

複数の理由がありましたが、数字が1つの理由がパフォーマンスでしたが、100までの子供を持つクラスは、ハードウェアのローカリティやCPUプリフェッチなどの理由で、ロジック、およびCPUのパイプライン化が含まれます。

アルゴリズム的には、配列構造はツリーよりもNの操作が多く必要ですが、これらの操作を行うのはメモリをまたいでポインタを追うよりも高速です。