algorithm - UnionFindでパス圧縮がランクを変更しないのはなぜですか?

Question

ここから、ランクとパスの圧縮によるユニオンを使用した UnionFind の実装を見ていますhttp://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_forests (CLRS とほぼ同じ擬似コードです)パス圧縮がランクを変更しない理由を理解していません。ルートからの最長パスのエンドポイントを呼び出すfindと、ランクが下がり、そうでない場合、次のunion操作で間違ったルートが選択されます。

Answer 1

「ランク」は、理論上のコンピューター サイエンスにおいて、恐ろしく過負荷な用語の 1 つです。ウィキペディアが指摘しているように、パス圧縮を伴うばらばらな集合データ構造のコンテキストでは、ランクはフォレストの現在のトポロジの固有のプロパティではありません。各ノードの高さを最新に保つ良い方法はありません。ただし、一連の和集合によって定義されるように、ランクは、逆アッカーマン関数を含む実行時間の範囲を証明するのに役立ちます。

Answer 2

ランクはツリーの実際の深さではなく、上限です。そのため、find操作では、ランクが深度と同期しなくなることがあります。