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