[解決済み] 2つの木構造を同一にするための最小限の操作を計算する

質問

これはどちらかというとCSに関する質問ですが、興味深いものです。

多かれ少なかれ同じノードを再編成した2つの木構造があるとします。あなたはどのようにして

1. 任意の
2. ある意味で 最小限の

操作の順序

• MOVE(A, B) - ノードAをノードBの下に移動させる（サブツリー全体を含む）
• INSERT(N, B) - を挿入します。 新しい ノードNをノードBの下に
• DELETE (A) - ノードAを（サブツリーごと）削除します。

で、一方のツリーをもう一方に変換します。

明らかに、そのような変換が可能でない場合があるかもしれません。） そのような場合、アルゴリズムは単に結果 " を提供します。 不可能 という結果を返します。

さらに壮大なバージョンは、ネットワークに対する一般化です。すなわち、ノードがツリー内で複数回出現することができる (事実上複数の親を持つ) と仮定した場合ですが、サイクルは禁止されています。

免責事項：これは ではなく 宿題ではなく、実際のビジネス上の問題から来ています。

どのように解決するのですか？

Wikipedia にはグラフ同型に関する記事があるだけでなく (Space_C0wb0y が指摘しているように)、専用の グラフ同型性問題 . この記事には Solved special cases があり、その中で多項式時間解法が知られています。Trees はそのうちの一つで、以下の2つの文献を引用しています。

• P.J. Kelly, "A congruence theorem for trees""; Pacific J. Math., 7 (1957) pp.961-968.
• Aho, Alfred V.; Hopcroft, John; Ullman, Jeffrey D. (1974), The Design and Analysis of Computer Algorithms, Reading, MA: Addison-Wesley .