ディスジョイントは特別な方法で設定しますか？

Question

私たちはツリーを使って非同型データ構造を実装しています。このデータ構造では、makeset()は、merge(i, j)の2つのツリーをセットiとjにマージして、2番目のツリーのルートの子になるようにします。 nmakeset()操作とn-1 merge()操作をランダムに実行した後、1つの検索操作を実行します。この最悪の場合の検索操作のコストはいくらですか？

I) O(n) 
II) O(1) 
III) O(n log n) 
IV) O(log n) 

回答：IV。

誰もがこの解決策を得る良いヒントを述べることができましたか？

Answer 1

O（n個のログを）見つけるあなたは（も加重組合として知られている）のランクで組合を使用する場合にのみ当てはまります。この最適化を使用するときは、ツリーのルートより下位のツリーを常に上位に配置します。両方が同じランクを持つ場合は、任意に選択しますが、結果ツリーのランクを1つ上げます。これは、ツリーの深さに拘束されたO（log n）を与える。我々は、（ランク> = iはのツリーであることに相当する）ルート以下Iレベルであるノードは、少なくとも2つの^Iノード（これはツリーであることを示すことによってこれを証明することができサイズがnのツリーを示すのと同じものは、ログnの深さを持ちます）。これは誘導で簡単に行うことができます。

Induction hypothesis: tree size is >= 2^j for j < i. 
Case i == 0: the node is the root, size is 1 = 2^0. 
Case i + 1: the length of a path is i + 1 if it was i and the tree was then placed underneath 
      another tree. By the induction hypothesis, it was in a tree of size >= 2^i at 
      that time. It is being placed under another tree, which by our merge rules means 
      it has at least rank i as well, and therefore also had >= 2^i nodes. The new tree 
      therefor has >= 2^i + 2^i = 2^(i + 1) nodes.