algorithm - 为什么按等级合并而不是计数？

Question

我想知道，为什么在联合查找算法中- 你按它们的高度合并两棵树 - 将较小的一棵附加到较高的一棵（在没有路径压缩的更简单的变体中）。

如果您通过元素的数量将它们合并 - 将具有较少元素的树附加到具有更多元素的树上，这会是一种更糟糕的方法吗？

Answer 1

按高度或节点数合并是安全的。

当按高度合并时，其中有 n 个节点的树的高度最多为 O(log n)。要看到这一点，请注意至少需要一个节点才能获得高度为零的树。从那里，获得高度为 h + 1 的树的唯一方法是将两棵高度为 h 的树合并在一起。这意味着获得高度 h 所需的节点数，我们将用 N(h) 表示，由下式给出

N(0) ≥ 1

N(h + 1) ≥ 2N(h)

此递归求解 N(h) ≥ 2 ^h，这意味着在总共 n 个节点的情况下，我们将获得大约 log n 的最大可能高度。这个上限很紧，因为如果你从 2^小时独立的树开始并反复成对合并它们，你会产生一棵高度为 h 的树。

当按节点数进行合并时，我们可以类似地证明一棵有 n 个节点的树的高度最多为 O(log n)。我们可以使用类似的论点。令 M(h) 表示在按节点数合并时创建高度为 h 的树所需的最小节点数。显然，M(0) = 1。那么，要创建一个高度为 h + 1 的树会发生什么？这需要将两棵高度为 h 的树合并在一起，所以我们得到了

M(0) = 1

M(h + 1) ≥ 2M(h)

和以前一样，这解决了 M(h) ≥ 2 ^h，所以不仅上限也是 O(log n)，它与我们之前的上限完全相同。因此，按高度或节点数联合是安全的。

那么为什么使用高度而不是节点数呢？一个论点是考虑存储高度信息所需的信息位数。如果每个节点都存储它下面的节点数，我们需要每个节点 O(log n) 位来写出大小信息。另一方面，如果每个节点只存储它所在的高度，一个 O(log n) 的数字，我们只需要每个节点 O(log log n) 位来写出所有内容，这将成倍减少空间。此外，使用路径压缩和 union-by-rank 的优化是专门为使用高度信息而不是大小信息而设计的，因此如果不重复（非常困难的）运行时分析，我们无法得出结论是否仍然得到相同的时间限制。

希望这可以帮助！

Answer 2

这是个有趣的问题。在没有进行深入分析的情况下，将节点与其各自根的平均距离保持在最小值而不是最大距离似乎更好。这意味着，将元素较少的树添加到元素较多的树中是更好的方法。通过这样做，平均距离最多可以增加 1/2，而在另一种情况下，平均距离最多可以增加 1。