我们用树来实现不相交的数据结构。在这个数据结构中 makeset() 创建一个只有一个元素的集合， merge(i, j) 合并集合 i 和 的两棵树>j 这样高度较低的树成为第二棵树的根的 child 。如果我们随机做n makeset()操作和n-1 merge()操作，然后做一个find操作。在最坏的情况下，此查找操作的成本是多少？
I) O(n)
II) O(1)
III) O(n log n)
IV) O(log n)
答案:IV.
Anyone could mentioned a good tips that the author get this solution?
最佳答案
仅当您使用按等级联合(也称为加权联合)时，O(log n) 查找才为真。当我们使用这种优化时，我们总是将排名较低的树放在排名较高的树的根下。如果两者具有相同的等级，我们任意选择，但将结果树的等级增加一。这给出了树深度的 O(log n) 界限。我们可以通过显示低于根 i 级的节点(相当于在级别 >= i 的树中)至少在树中来证明这一点2i 个节点(这与显示大小为 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.
关于algorithm - 以特殊方式设置不相交？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37242183/