为什么按等级合并,不计算？

Question

我想知道,为什么在union-find算法中 - 你按照它们的高度合并两棵树 - 将较小的树连接到较高的树(在没有路径压缩的简单变体中).

如果你按照元素的数量合并它们会更糟糕吗 - 用更少的元素将树用更少的元素附加到树上？

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 个}独立的树开始并重复地将它们成对合并，您将生成一棵高度为 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) 位即可写出所有内容，这会大大减少空间。此外，使用路径压缩和按等级并集的优化是专门为使用高度信息而不是大小信息而设计的，因此，在不重复（极其困难的）运行时分析的情况下，我们无法断定我们是否仍然获得相同的时间限制。

希望这可以帮助！