4

ユニオン検索を行うために、ばらばらなデータ構造を実装しています。ウィキペディアで次のような記述を見つけました。

... 同じランク r の 2 つのツリーを結合すると、結果のランクは r+1 になります。

ツリーが同じランクであるのに、結合されたツリーのランクを 1 つだけ上げる必要があるのはなぜですか? 単純に 2 つのランク (つまり2*r) を加算するとどうなりますか?

4

5 に答える 5

6

この場合、一方のツリーをもう一方の「サブツリー」として追加すると、元のサブツリーのサイズが大きくなります。

次の例を見てください。

1           3
|           |
2           4

上記では、各ツリーの「ランク」は 2 です。
ここで、1 が新しい統合ルートになるとしましょう。次のツリーが得られます。

    1
   / \
  /   \
 3     2
 |
 4

参加後、「1」のランクは3ですrank_old(1) + 1-予想どおり。1

2 番目の質問については、木の高さが間違っているためです。

上記の例で、ツリーをマージしてランク 3 のツリーを取得するとします。それをこのツリー2とマージするとどうなるでしょうか。

         9
        / \
      10   11
            |
           13
            |
           14

両方のランクが 4 であることを確認し、「短い」ツリーを優先せずに、以前と同じ方法でそれらをマージしようとします。これにより、ツリーの高さが高くなり、最終的には時間の複雑さが悪化します。

（1）免責事項：この回答の最初の部分は、同様の質問に対する私の回答から取られています（ただし、質問の最後の部分のために同一ではありません）

(2) 上記のツリーは構文的に作成されていることに注意してください。最適化されたばらばらのフォレスト アルゴリズムでは作成できませんが、回答に必要な問題を示しています。

于 2013-08-06T13:39:27.267 に答える
4

その段落をもう少し深く読むとrank、サイズではなく深さのようなものであることがわかります。

実行時間に影響を与えるのはツリーの深さであるため、深さが等しい場合にのみ深さを増やすだけで、より深いツリーのルートの下に深さの小さいツリーが追加されます。このアルゴリズムのコンテキストでは、「深さ」の代わりに「ランク」という用語が使用されます...

また、同じ深さのツリーをマージすると、一方のルートが他方のルートに追加されるため、ツリーの深さが 1 だけ増加します。

検討：

  A                  D
 / \   merged with  / \
B   C              E   F

は：

  A
 /|\
B C D
   / \
  E   F

深さは両方とも 2 で、マージされたものは 3 です。

于 2013-08-06T13:36:52.973 に答える
3

ランクは、ノードの数ではなく、ツリーの深さを表します。ランクの小さいツリーをランクの大きいツリーに結合すると、全体のランクは変わりません。

ランク 4 のツリーをランク 6 のツリーのルートに追加することを検討してください。深さ 4 のツリーのルートの上にノードを追加したため、そのサブツリーのランクは 5 になりました。ただし、深さ 4 の木は 6 であるため、ランクは変わりません。

ここで、ランク 6 のツリーをランク 6 の 2 番目のツリーのルートに追加することを検討してください。最初の深さ 6 ツリーのルートには、その上に余分なノードがあるため、そのサブツリー (およびツリー全体) のランクは次のように変更されます。 7。

ツリーのランクが処理速度を決定するため、アルゴリズムは、全体のランクを変更せずに常に短いツリーを高いツリーに接続することにより、ランクをできるだけ低く維持しようとします。ランクは、ツリーのランクが同じ場合にのみ変化します。この場合、一方のツリーがもう一方のルートに接続され、ランクが 1 つ上がります。

于 2013-08-06T13:45:05.773 に答える