0

ツリーを使用して Disjoint Data 構造を実装します。このデータ構造でmakeset()は、1 つの要素を持つセットを作成し、セットのmerge(i, j)2 つのツリーをマージして、高さの低いツリーが 2 番目のツリーのルートの子になるようにします。操作と操作をランダムに実行してから、検索操作を 1 回実行するとします。最悪の場合、この検索操作のコストはいくらですか?ijn makeset()n-1 merge()

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

答え: IV.

著者がこの解決策を得るための良いヒントについて言及できる人はいますか?

4

1 に答える 1

1

O(log n) の検索は、ランクによる結合(加重結合とも呼ばれます) を使用する場合にのみ真になります。この最適化を使用する場合、常にランクの低いツリーをランクの高いツリーのルートの下に配置します。両方のランクが同じ場合、任意に選択しますが、結果のツリーのランクを 1 つ上げます。これにより、ツリーの深さに制限された O(log n) が得られます。これは、ルートのiレベル下にあるノード (ランク >= iのツリーにあることに相当) が少なくとも 2 iノードのツリーにあることを示すことで証明できます(これは、サイズのツリーを表示するのと同じです)。nには log 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.
于 2016-05-15T20:15:06.943 に答える