3

こんにちは、これは私の初めての投稿です、

私は勉強のための質問を考え出そうとしましたが、それを理解することができませんでした：

サイズとパス圧縮による加重和集合を使用した、互いに素なセットの抽象データ型のフォレスト実装を検討します。最初は、各要素は1ノードツリーにあります。

上記の初期状態から開始します。

  1. UNIONおよびFIND操作の（短い）シーケンスを指定します。最後の操作はUNIONであり、高いツリーAが短いツリーBのサブツリーになります（つまり、Aの高さがBの高さよりも厳密に大きい）。 。

  2. 最後のUNIONがマージする2つのツリーAとBを表示します

ヒント：n = 9個の要素から開始でき、各要素は1ノードツリーにあります。

サイズによる結合のために、小さいツリーは常に大きいツリーとマージされるため、それがどのように機能するかわかりませんか？

ありがとう。

4

1 に答える 1

2

私はあなたの宿題に答えたくありませんが、この質問はあなたの学期が終わった可能性が高いほど古いものであり、いずれにせよヒントは十分に役立つはずです.

主にパス圧縮のために、サイズによる結合と高さによる結合には違いがあります。具体的には、パス圧縮により、ノードの次数が非常に高くなり、ノードが多くても高さが非常に短いツリーが生成される可能性があります。たとえば、これらは、パス圧縮を使用してユニオン検索で作成できる 2 つのツリーです。

|T1:   o    (n=5, h=2)
|    /| |\ 
|   o o o o
|    
|T2:   o    (n=4, h=3)
|     /|
|    o o
|      |
|      o

次の操作がこれら 2 つのツリーのマージである場合、「ランクによる結合」アルゴリズムと「高さによる結合」アルゴリズムは異なる親を選択します。

実際には、「ランクによるユニオン」が通常使用されます。ランクは、一定時間で更新できる高さの上限であり、最良の漸近的な実行時間をもたらします。Web 検索を行うと、そのアルゴリズムの適切な説明が多数見つかります。

于 2013-01-19T01:55:38.540 に答える