脱节以特殊方式设置？

我们用树实现了Disjoint Data结构。在这个数据结构makeset()中创建一个具有一个元素的集合，merge(i, j)合并两棵树集合i和j，使得高度较低的树成为第二棵树的根的孩子。如果我们以随机方式做nmakeset()操作和n-1 merge()操作，然后做一个查找操作。在最坏的情况下，查找操作的成本是多少？脱节以特殊方式设置？

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

答案：IV。

任何人都可以提到一个很好的提示，作者得到这个解决方案？当您使用工会通过排名（又称加权工会）

来源

2016-05-15 Maryam Koj

您能否提供此声明的来源？ – amit

有一个错字，我纠正它。这是一个本地考试，并已扫描文档。 @amit –

我认为答案是aaaa – user3661613

的O（log n）的发现仅仅是真实的。当我们使用这个优化时，我们总是把排名较低的树下的树放在树的根下。如果两者具有相同的等级，我们任意选择，但是将得到的树的等级增加1。这给出了一个O（log n）在树的深度上的界限。那就是根我水平以下的节点（相当于秩的树是> = 我）是在至少2 ^我节点树我们可以显示证明这一点（这是与展示尺寸为的树相同，其具有的尺寸为具有日志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-15 20:15:06

有一个不错的解决方案+1，但我认为这里有一个错字 – user3661613

对不起，这个问题没有说按级别结合，说事情不同。不是吗？ –

@MaryamKoj：你说你合并时把高度较低的树放在高度较低的树下。这正是所谓的_union by rank_（_rank_永远是任何叶子的最深层次）。 –

脱节以特殊方式设置？

回答

相关问题