「Union-Find アルゴリズム」の「ランク」の必要性について

Question

teratail 初投稿です。質問法に不備があったらご容赦ください。

現在、「Union-Find アルゴリズム」を勉強しております。
高速化の方法として「経路圧縮」と「ランク」という2つの手段があることを知りましたが、腑に落ちない点がありました。

「経路圧縮」を行った場合、「子要素」は直接「親要素」に紐づくものになるはずです。つまり、親要素のランクは1より大きくはならないはずなので、「ランク」による管理は不必要ではないか、と思うのですが、この理解は正しいでしょうか。

「経路圧縮」または「ランク」のどちらか片方を実装するのは意味があると思うのですが、「経路圧縮」と「ランク」の両方を実装するのは意味がない、と思うのですが、この理解が正しいかどうか、どなたかご教示頂けないでしょうか。

Answer 1

rank kの木同士を結合したときにrank k+1の木ができるので
rank kの木には最低でも2^k個の要素があります。

つまり、大抵の場合rankが大きい程所属している要素が多いです。

所属してる要素が多い木を吸収するほど、経路圧縮の回数が増えます。
その為、ランクが大きい方を根として吸収させた方が効率がよくなります。