如何在UnionFind数据结构中正确实现wighted union和路径压缩

Question

我试图用C实现一个联合查找/分离集数据结构，在查找中使用加权联合和路径压缩。我有一些问题，与非加权联合相比，如何实现加权联合以降低时间复杂度。

我已经在网上找到了解决这个问题的几种方法，并实施了自己的方法。在每个解决方案中，每个单独树的根（表示一个集合）始终保持树的节点数。当合并属于不同集合的两个随机对象的集合时，首先找到根（这里使用路径压缩），然后比较这些根的大小。最大树的根被设置为最小树的根的父级。

然而，在我的理解中，我们试图用加权联合实现的是降低结果树的高度(这也是我们试图用路径压缩实现的)。因此，应该连接到另一棵树的不是具有最低节点数的树，而是具有最低高度的树。这使高度保持最小。

这是正确的吗？考虑到实现的其余部分(我们总是从许多单个(一个节点)集合开始)，检查高度和大小在某种程度上是等价的吗？

假设需要检查的是高度，如果不使用路径压缩，则跟踪树的高度是相当简单的。然而，我还没有找到一种方法来跟踪使用路径压缩时树的高度（至少在不遍历整个树的情况下是这样，这增加了“find”算法的时间复杂性。

以下是我找到的一个实现示例，并使用我在c：https://github.com/kartikkukreja/blog-codes/blob/master/src/Union 查找（脱交集）数据结构中描述的内容（与我所编码的内容非常相似）.cpp

Answer 1

看来你自己已经很清楚了。

高度联合是生成最短树的明显方法，但是当使用路径压缩时，很难跟踪高度...

所以通常使用按等级联合。一个集合的“等级”是它的高度，如果我们不做任何路径压缩，所以当你在路径压缩中使用按等级联合时，就像从按高度联合开始，然后应用路径压缩作为优化，确保路径压缩不会改变合并的工作方式。

然而，很多人（包括我自己）使用按大小合并，因为大小通常是有用的，并且可以证明按大小合并会产生与按等级联合相同的最坏情况复杂性。同样，在这种情况下，路径压缩不会影响合并，因为它不会更改任何根的大小。