加权快速联合解释
我需要帮助理解关于加权快速联合的问题所作的解释：
以下哪个
id[]数组可以是在一组10项上运行加权快速联合算法的结果？检查所有的申请。 回想一下，我们的加权快速合并算法使用的是大小(节点数)的合并(而不是按高度合并)。 不正确：9 1 7 3 4 9 6 7 8 9说明：9-5 7-2 5-0不正确：2 2 2 2 5 1 2 3 1 2说明：2-9 3-7 9-3 5-4 0-2 1-8 8-4 4-9 8-6正确：9 9 3 4 9 4 9 9 4 2说明：id[]数组包含一个循环：2->3->4->9->2正确：0 2 3 0 0 2 2 9 3 0说明:植根于2 <父母的树的大小是2树的两倍大。 正确：0 4 6 7 4 1 5 1 7 3说明:森林高度=4 > lg N = lg(10)
- 我如何才能知道前两个问题所显示的实际工会运作？
- 我是否需要看每一个元素才能确定是否有一个循环？
- 我怎么知道树的大小？(顺便说一句，第四个问题的解释对我来说毫无意义)
- 我怎么知道森林的高度？
回答 2
Stack Overflow用户
发布于 2014-09-12 18:31:38
你还没有给出完整的上下文，但我会试着从我所知道的关于加权联盟的情况来回答。
我是否需要看每一个元素才能确定是否有一个循环？
不是的。这将破坏快速联合的目的。循环表示工会操作未正确执行。任何时候都不应该有循环。
我怎么知道树的大小？
最初，所有的树都是1。在union操作中，我们把被连接的2棵树的大小相加。我们通过数组(比如SZ[])来跟踪大小。给定树的大小在数组中的根偏移量(SZ[root(i)])处更新。
我怎么知道森林的高度？
那也必须被追踪。最初，所有的树都是高度1。当你加入2棵树时--比如说A & B，你把A的根作为新的根。那么连接树的高度将是max(A.height, B.height+1)。
Stack Overflow用户
发布于 2016-02-08 01:59:15
顺便说一下，第四个问题的解释对我来说毫无意义。
因为只有在较小的树中节点的深度才会增加1，而组合树中最深节点的深度最多只能比树组合之前最深的节点深一层。因此，组合树中的节点总数至少是较小子树中节点数的两倍。来源
https://stackoverflow.com/questions/25814387
复制相似问题
腾讯云开发者
