0

私はこのようにアルゴリズムを理解しています...

  • パス圧縮により、検索操作の時間が短縮され、パス圧縮の時間の複雑さが平均して O(1) になります。

  • ランクを見て、2 つのうちどちらが親ノードであるか (ユニオン操作中) を決定します。

しかし、ランクごとの結合が何をするのか理解できませんでした。ここでランクが何を意味するのかを正しく理解しているとは思えません。また、結合する2つのセットのランクが同じ場合、結合中に親のランクが1増加する理由もわかりません。

4

1 に答える 1

2

https://en.wikipedia.org/wiki/Disjoint-set_data_structureの「ランクによるユニオンと呼ばれる最初の方法は、常に小さいツリーを大きいツリーのルートに接続することです」で始まる段落は、パス圧縮がなくても、ランクによる結合は、結合操作のコストを最悪の場合の O(log n) に削減するのに十分です。

また、パス圧縮なしでは、ランクはこれまでに生成されたツリーの最大深度を反映することも説明しています。これは、ランクが同じ場合にのみ増加する理由を説明しています。これは、小さいツリーが大きいツリーのルートに追加されるためです。これは、最大深度が実際に増加する唯一のケースです。

于 2016-06-05T04:24:08.903 に答える