ランク別のパス圧縮と結合はどのように互いに補完しますか？

Question

私は組合発見問題について読んできました。 2つの主な改善点は、パス圧縮とランク別の結合です。私が知る限り、ランクごとにunionを使用して、分離したツリーを結合する方法を決定します。 2つの互いに素なツリーT1およびT2がある場合、より高いランクのツリーに、より小さなランクのツリーのルートをアタッチします。パス圧縮を使用しない場合、ランクはツリーの深さに過ぎません。これは、木の深さを増やしたいとは考えていないので意味があります。なぜなら、それはfindとunionの両方に直接影響するからです。

私の問題は、パス圧縮も使用する場合です。私は2つの最適化がお互いを補完することを読んでいるが、私はそれを見ていない。パス圧縮のため、ランクはもはやツリーの深さではなく（深度の上限になります）。 T1に2つのブランチがあり（T1のランクを3とする）、T2に深さ2とランク2があると仮定します。次に、「*」とマークされたT1の葉に（パス圧縮で）検索操作を実行すると仮定します。今度は、T1のルートとT2のルートを結合すると、T1のルートにT2が付けられます（ランクはfindによって更新されないため）。結果のツリーには深さ3がありますが、T1にT2を付けるとパフォーマンスが向上する可能性があります。我々は

T1: o  (Rank = 3)  T2: o (Rank = 2)  
    /| |\       | 
    * o o o      o 
            | 
            o 
Result of T1 union T2 
     o 
/| | |\ 
    * o o o o Rank = 3 and Max Depth = 3 
      | 
      o 
      | 
      o 

を取得し、T1とT2の根に、その後、T1（ "*"）の葉の上で見つける組合後

T1: o (Rank = 3) T2: o (Rank = 2) 
    /\      | 
    o o      o 
    |       | 
    o       o 
    | 
    * 

私はここで何かが足りないのですか？ランクごとのパス圧縮と結合はどのようにお互いを補完しますか？私は階数が木の深さの上界に過ぎないことを知っていますが、階級別の組合がどのように構造の全体的な性能を改善しているか分かりません。ルーツを無作為に組み合わせた組合よりも、これはどのように優れていますか？

ご協力ありがとうございます。

Answer 1

Union by rankは、ツリーの最大深さがlog Nであることを保証します。したがって、すべての操作でO（log N）の最悪の上限を設定します。特別な組合せず

パス圧縮は、（Nログ）上の各操作のコストを償却するが、最悪の場合は費用限定するものではないOの上限を支配します。 （償却されたコストは厳しく制限されるかもしれませんが、O（log N）は証明方法が分かります）

最悪のケースではO（ログN）の制限があります償却された結合は、実質的に一定であるO（（N））に改善する。このように、2つの最適化は相補的です。

ランク別ユニオンが絶対に最適ではない操作のシーケンスがありますが、の保証がある場合は、があなたの手に入れないものよりも優れているという保証があります。通常、ケースのパフォーマンスを最大限に引き出すように努力していません。が最悪または、平均がに最適化されています。