algorithm - Disjoint-set forests - 当发现两个节点具有相同等级时，为什么要将等级增加一？

Question

我正在实现 disjoint-set datastructure做联合查找。我在维基百科中看到了以下声明:

... whenever two trees of the same rank r are united, the rank of the result is r+1.

当树的等级相同时，为什么连接树的等级只增加一？如果我简单地将两个等级相加(即 2*r)会怎样？

Answer 1

首先，什么是排名？它几乎与一棵树的高度相同。事实上，就目前而言，假设它与高度相同。

我们想让树变矮，因此跟踪每棵树的高度有助于我们做到这一点。当合并两棵不同高度的树时，我们使较矮树的根成为较高树根的 child 。重要的是，这不会改变较高树的高度。也就是说，较高树的等级不变。

但是，当合并两棵相同高度的树时，我们使一个根成为另一个的子树，这会使整个树的高度增加一，因此我们将该根的等级增加一。

现在，我说等级几乎与树的高度相同。为什么差不多？由于路径压缩，联合查找数据结构使用的第二种技术来保持树短。路径压缩可以改变现有的树，使其比其等级指示的更短。原则上，根据实际高度做出决定可能比使用排名作为高度的代理更好，但在实践中，跟踪真实高度信息太难/太慢，而这很容易/快速跟踪排名。

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

另一方面，请注意，通过将两个等级相加，您估算的是树的大小，而不是树的高度。通过始终将两个等级相加，无论它们是否相等，您都可以准确地跟踪树的大小。同样，一切正常，但如果您的树非常大，则可能会出现整数溢出的警告。

事实上，按大小并集被广泛认为是按等级并集的合法替代方案。对于某些应用程序，您实际上想知道集合的大小，对于这些应用程序，按大小并集实际上比按等级并集更可取。