0

我们用树实现了不相交的数据结构。在这个数据结构中，makeset()创建一个包含一个元素的集合，merge(i, j)合并两个集合树，i这样j高度较低的树成为第二棵树的根的子节点。如果我们以随机方式进行n makeset()操作和n-1 merge()操作，然后进行一次查找操作。在最坏的情况下，这种查找操作的成本是多少？

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

答案：四。

任何人都可以提到作者获得此解决方案的好技巧吗？

4

1 回答 1

1

O(log n) 查找仅在您使用按等级联合（也称为加权联合）时才成立。当我们使用这种优化时，我们总是将排名较低的树放在排名较高的树的根下。如果两者具有相同的等级，我们任意选择，但将结果树的等级增加一。这给出了树深度的 O(log n) 界限。我们可以通过证明一个比根节点低i级的节点（相当于在 rank >= 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 回答