我正在尝试在 C 语言中实现联合查找/不相交集数据结构，在 Find 中使用加权联合和路径压缩。与非加权联合相比，我有一些关于如何实施加权联合以减少时间复杂度的问题。
我已经在网上找到了这个问题的几种解决方案，并实施了我自己的解决方案。在每个解决方案中，每个单独树的根(表示一个集合)始终保存树的节点数。当合并属于不同集合的两个随机对象的集合时，首先找到根(此处使用路径压缩)，然后我们比较这些根的大小。最大树的根设置为最小树的根的父级。
然而，在我的理解中，我们试图通过加权联合实现的是降低结果树的高度(这也是我们试图通过路径压缩实现的)。因此，应该连接到另一棵树的不是节点数最少的树，而是高度最低的树。这样可以将高度保持在最低水平。
这是对的吗？考虑到实现的其余部分，检查高度和大小是否在某种程度上等效(我们总是从多个(一个节点)集开始)？
假设需要检查的是高度，如果不使用路径压缩，则跟踪树的高度相当简单。然而，我还没有找到一种方法来跟踪使用路径压缩时树的高度(至少不是没有遍历整个树，这增加了"查找"算法的时间复杂度。
以下是我发现的一个实现示例，并使用了我在 c++ 中描述的内容(与我编写的代码非常相似)： https://github.com/kartikkukreja/blog-codes/blob/master/src/Union%20Find%20(Disjoint%20Set)%20Data%20Structure.cpp
看起来你自己已经差不多想通了。
按高度联合是制作最短树的明显方法，但是当您使用路径压缩时，很难跟踪高度......
因此，通常使用按等级并集。 集合的"秩"是如果我们不进行任何路径压缩时它的高度，因此当您将逐个等级与路径压缩一起使用时，就像从按高度联合开始，然后应用路径压缩作为优化，确保路径压缩不会改变合并的工作方式。
然而，很多人(包括我自己)使用按大小联合，因为大小通常很有用，并且可以证明按大小联合会产生与按等级联合相同的最坏情况复杂性。 同样在这种情况下，路径压缩不会影响合并，因为它不会更改任何根的大小。