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