不相交的森林 - 当两个节点的发现具有相同的等级时,为什么要将等级增加一？

Question

我正在实现不相交的数据结构来进行联合查找.我在维基百科中看到以下声明:

......每当两个相同等级r的树结合在一起时,结果的等级为r + 1.

当树木属于同一级别时,为什么连接树的等级只增加一个？如果我只是添加两个等级(即2*r)会发生什么？

Answer 1

首先,排名是什么？它几乎与树的高度相同.事实上,现在,假装它与高度相同.

我们希望保持树木短,所以跟踪每棵树的高度有助于我们做到这一点.当联合两个不同高度的树时,我们使较短树的根成为较高树的根的子.重要的是,这不会改变较高树的高度.也就是说,较高树的等级不会改变.

但是,当联合两个相同高度的树时,我们将一个根作为另一个的子,这会将整个树的高度增加一,因此我们将该根的等级增加一.

现在,我说排名几乎与树的高度相同.为何几乎？由于路径压缩,union-find数据结构使用第二种技术来保持树的简短.路径压缩可以改变现有树,使其比其等级指示的更短.原则上,根据实际高度做出决策可能比使用等级作为高度代理更好,但在实践中,跟踪真实高度信息太难/太慢,而它很容易/快速跟踪排名.

你还问:"如果我只是添加两个等级(即2*r)会怎么样？" 这是个有趣的问题.答案可能没什么,这意味着一切都会运转得很好,效率和以前一样.(好吧,假设您使用1作为起始等级而不是0.)为什么？因为使用等级的方式,重要的是等级的相对排序,而不是它们的绝对大小.如果你添加它们,那么你的等级将是1,2,4,8而不是1,2,3,4(或者更可能是0,1,2,3),但它们仍然具有完全相同的相对排序所以一切都很好.你的排名只是2 ^(旧排名).最大的危险是,当处理非常大的集合时,你会冒更大的溢出用于表示排名的整数的风险(换句话说,你将需要使用更多空间来存储你的排名).

另一方面,请注意,通过添加两个等级,您将近似树的大小而不是树的高度.通过始终添加两个等级,无论它们是否相等,那么您正在精确地跟踪树的大小.同样,一切都运行得很好,如果你的树很大,有关于整数溢出的可能性的注意事项.

实际上,按尺寸联合被广泛认为是逐级联合的合法替代方案.对于某些应用程序,您实际上想知道集合的大小,对于那些应用程序,按大小实际上优先选择逐级联合.

Answer 2

因为在这种情况下 - 你添加一棵树是另一棵树的"子树" - 这使得原始子树增加了它的大小.

看看下面的例子:

1           3
|           |
2           4

在上面,每棵树的"等级"是2.
现在,假设1将成为新的统一根,您将获得以下树:

    1
   / \
  /   \
 3     2
 |
 4

在加入之后,"1"的等级是3,rank_old(1) + 1- 如预期的那样.¹

至于你的第二个问题,因为它会产生树木的假高度.

如果我们采用上面的例子,并合并树来获得等级3的树.如果我们想要将它与这个树²合并,会发生什么:

         9
        / \
      10   11
            |
           13
            |
           14

我们会发现两个等级都是4,并尝试以与之前相同的方式合并它们,而不偏向于"较短"的树 - 这将导致树高度更高,最终 - 时间复杂度更差.

(1)免责声明:这个答案的第一部分来自我对类似问题的回答(尽管由于你的问题的最后部分不一致)

(2)注意上面的树是合成的,它不能在优化的不相交森林算法中创建,但它仍然展示了答案所需的问题.