为什么加权快速联合算法考虑树的大小而不是高度？

Question

我正在观看 Robert Sedgewick 关于快速联合改进的视频。 (https://youtu.be/sEo6LlPxpHE?t=267)

他使用树的大小而不是高度。实际上问题是找到根节点。如果高度很高的话，寻找起来就会很困难。所以我们应该找到一种方法来减轻高度的影响。只有比较高度会不会不符合预期呢？将较短的树连接到较高的树不会解决问题，而是这样做：将节点数较少的树连接到节点数较多的树？

下面这个案例呢？

根据视频中的逻辑：

A 树的大小 = 4

B 树的大小 = 7

如果将 A 连接到 B 。实际上，我们正在使生成的树更高（高度 4）。但是如果我们根据树的高度来完成它，我们可以通过将树 B 连接到 A 来解决它。因此生成的树的高度将为 3。

我说得对吗？ 如果错了我哪里错了？

Answer 1

请记住，不相交集森林的大多数实现都应用路径压缩优化，其中在每次查找期间，您都会更改链中所有节点的父指针，以便它们都指向其代表。

事实证明，如果您使用路径压缩并在压缩之前跟踪所有节点的高度，则按高度链接的渐近性能（通常称为union-by-rank，其中“rank”是任何压缩之前的高度）和重量连接是相同的。两者都给出了逆阿克曼时间复杂度。这个结果来自这篇论文，技术性很强，但确实证明了这两个结果。

即使您不这样做，也可以通过另一种方式来查看这两种方法（大致）彼此相同。请注意，如果您有一棵高度为 1 的树，则它必须至少有两个节点。为什么？那么，使高度为 1 的树的唯一方法是合并到高度为 0 的树，每个树必须至少有一个节点。使用类似的逻辑，您可以看到，如果您有一棵高度为 2 的树，那么它必须至少有四个节点，因为要形成它，您必须将两棵高度为 1 的树合并在一起。更一般地，您可以证明高度为 n 的树中必须至少有 2ⁿ 节点。因此，按高度合并本质上与按重量合并相同，因为树木的高度和大小之间存在密切联系。

希望这有帮助！

Answer 2

按大小或按高度加权的快速联合大致相同，它们具有相同的上限，如@templatetypedef之前提到的。

让我分享更多细节。

在按大小加权的策略中，让一棵树

T

有一个节点

x

，其深度（或高度）

h

为1。只有当

T

合并到另一棵大小相同的树时，h才会增加1等于或大于

T

。所以，

• 对于 h = 1，树大小 N = 1
• h = 2，N >= 2
• h = 3，N >= 4
• h = 4，N >= 8
• ....

换句话说，h 的上限是 lgN + 1(

h <= (lgN + 1)

)。

如果 union-find 按高度加权怎么办？显然，当树深度

h = 2

时，至少需要2个节点。当

h = 3

时，最小节点数为4（两棵深度为2的树都合并了最小节点数）。情况和上面一样，

• 对于 h=1，树大小 N = 1
• h = 2，N >= 2
• h = 3，N >= 4
• h = 4，N >= 8
• ....

对于按高度加权的并查，我们得到结论：

h <= (lgN + 1)

。也就是说，无论按高度加权还是按大小加权，它们的深度都有相同的上限。

关于你提到的令人困惑的情况，这是由于合并的随机性造成的，我们已经找到了深度的上限，假设它是

5

，但有可能结果是

4

或

3

，或任何不超过

5

的数字，根据合并顺序。

再说一遍，教科书《算法》（第4版）在1.5.14的创意问题第237页确实提到了按高度加权的快速并集。

Answer 3

首先，正如其他人提到的，尺寸和高度具有相似的性能。

但是，为什么我们选择尺寸而不是高度呢？ 我认为这是因为路径压缩期间高度会改变，而尺寸不会改变。

这是我自己的意见，因为我没有在任何地方找到它。希望是真的。