algorithm - ツリーでの Union-Find 操作?

Question

誰かが答えを太字で説明できますか? それはどのように行われますか？

以下は、次のアップツリーにつながる 4 つの Union-Find 操作 (重み付きユニオンと完全圧縮を使用) のシーケンスです。最後の 2 つの操作は何でしたか?

答え: Union(D,A), Union(B,C), Union(D/A,B/C),Find(B/C).

Answer 1

セットであるため に 表記 が 使用 さ れ て いる.

4 つの操作を適用してみましょう。

Union(D,A)次のツリーにつながります。

   D
  /
 A

Union(B,C)次のツリーにつながります。

   B
  /
 C

Union(D/A,B/C)これは、D と A が同じ set に属しているため、最初の引数が何であるかは問題ではないことをD意味しますA。同様に、B と C は同じ set に属しているため、2 番目の引数が何であるかは関係BありCません。

結果は 3 番目の操作の後になります。

   D
  / \
 A   B
      \
       C

圧縮も許可されているため、Find(C)操作の結果は次のようになります。

   D
  /|\ 
 A B C

4 番目の操作が の場合Find(B)、検索操作の後に圧縮を適用すると、ルートの直接の子であるルートまでのパスで検出されたすべてのノードが作成されるため、ツリーは同じままになりますが、検出されないため、次のCようになります。最終ツリーにあるため、Cの直接の子を作成することはできません。D

正解

4 つの操作の正しい順序は次のとおりです。

Union(D,A), Union(B,C), Union(D/A,B/C),Find(C).