联合查找 - 为什么我们要检查加权快速联合的大小

Question

我正在 Coursera 上学习普林斯顿大学的算法课程。

在并集查找部分，对于加权快速并集，我们根据哪棵树的Size更小来合并树。

但是，我不明白为什么我们使用Size而不是Depth来决定哪棵树更大，哪棵树更小。

由于树深度，寻找根的最坏情况时间复杂度不会增加吗？

在上面的示例中，如果我们通过检查 size 来合并 2 棵树，则结果树的 depth 为 4，而通过深度检查，我们会得到更小的结果树深度。

Answer 1

使用“排名”而不是大小来进行加权是很常见的。不使用高度，因为树的高度可以通过路径压缩以难以跟踪的方式改变。树的等级就是不使用路径压缩时的高度。

然而，使用树的大小与排名一样有效——并集和查找的最坏情况复杂性保持不变——并且同样容易跟踪。此外，了解每组的大小也是很有用的！因此，我更喜欢按大小而不是排名来加权。

Answer 2

当您使用按大小加权算法时，您提到的大小 3 示例不存在。

它会变成类似 -

     4                    or                   5
    / \                                       / \
   5   6                                     6   4

所以，你所说的身高增加问题并不会发生