带加权快速联合的 UnionFind（a.k.a 按排名联合）

Question

在LeetCode's tutorial提供的Union Find算法中，似乎树的权重（等级）只有在合并两个相等权重的子集时才增加，但是当一个大于或小于其他。有人可以解释为什么吗？

请参考以下算法：

private int[] rank;
public void union(int x, int y){
        int rootx = find(x);
        int rooty = find(y);
        if(rootx != rooty){

            if(rank[rootx] > rank[rooty]){
                //notice we don't increment the rank weight of rank[rootx] here
                root[rooty] = rootx; 
            }else if(rank[rootx] < rank[rooty]){
                root[rootx] = rooty;
            }else{
                //only if weights are the same, it is incremented. Why?
                root[rooty] = rootx;
                rank[rootx] += 1;  
            }
            count--;
        }
    }

Answer 1

union-find数据结构描述了一个forest, i.e. a collection of disjoint trees。 union 操作意味着将两棵树合并在一起（如果这两个顶点还不是同一棵树的一部分），这是通过将一棵树的根变为 child 来完成的另一棵树的根。

find算法的性能不依赖于树的基数（即顶点的个数），而是依赖于树的高度（即从顶点到路径的最大长度）根），因为这是从一个顶点遍历到包含该顶点的树的根所需的最大迭代次数。所以树的重量或等级就是它的高度。有两种情况：

如果树的高度为h1 < h2，则将高度为h1的树合并到高度为h2的树中。结果树的高度是 h2（如果这不是很明显，考虑一下），所以那棵树的根的等级不变。
如果两棵树的高度相等（都h），那么将一个的根作为另一个的根的child后，新树的高度将是h + 1, 所以树的根的秩增加1.

这不是它的方式，它只是您示例中数据结构中的方式。例如，如果您使用基数而不是高度，那么您会将数组中的所有等级初始化为 1，当合并两棵树时，无论基数是否为 rank[root2] += rank[root1];是否相等

另请注意，如果数据结构使用路径压缩，那么树的等级通常不会等于它的高度；它将是高度的上限，因为路径压缩可以降低树的高度，但是没有有效的方法来更新树中所有顶点的等级。请参阅 this other Q&A 进行讨论。

带加权快速联合的 UnionFind（a.k.a 按排名联合）

UnionFind with weighted Quick Union (a.k.a Union by rank)

algorithm

union-find