并查集 rank 的优化

上一小节介绍了并查集基于 size 的优化，但是某些场景下，也会存在某些问题，如下图所示，操作 union(4,2)。

根据上一小节，size 的优化，元素少的集合根节点指向元素多的根节点。操作完后，层数变为4，比之前增多了一层，如下图所示：

由此可知，依靠集合的 size 判断指向并不是完全正确的，更准确的是，根据两个集合层数，具体判断根节点的指向，层数少的集合根节点指向层数多的集合根节点，如下图所示，这就是基于 rank 的优化。

我们在并查集的属性中，添加 rank 数组，rank[i] 表示以 i 为根的集合所表示的树的层数。

...
private int [ ] rank ;   // rank[i]表示以i为根的集合所表示的树的层数
private int [ ] parent ; // parent[i]表示第i个元素所指向的父节点
private int count ;     // 数据个数
...

构造函数相应作出修改：

...
// 构造函数
public UnionFind4 ( int count ) {
    rank = new int [ count ] ;
    parent = new int [ count ] ;
    this . count = count ;
    // 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
    for ( int i = ; i < count ; i ++ ) {
        parent [ i ] = i ;
        rank [ i ] = 1 ;
    }
}
...

合并两元素的时候，需要比较根节点集合的层数，整个过程是 O(h)复杂度，h为树的高度。

...
public void unionElements ( int p, int q ) {
    int pRoot = find ( p ) ;
    int qRoot = find ( q ) ;
    if ( pRoot == qRoot )
        return ;

    if ( rank [ pRoot ] < rank [ qRoot ] ) {
        parent [ pRoot ] = qRoot ;
    }
    else if ( rank [ qRoot ] < rank [ pRoot ] ) {
        parent [ qRoot ] = pRoot ;
    }
    else { // rank[pRoot] == rank[qRoot]
        parent [ pRoot ] = qRoot ;
        rank [ qRoot ] += 1 ;   // 此时, 我维护rank的值
    }
}
...

Java 实例代码

源码包下载： Download

UnionFind3.java 文件代码：

package yssmx.union ;
/**
 * 基于rank的优化
 */
public class UnionFind4 {
    private int [ ] rank ;   // rank[i]表示以i为根的集合所表示的树的层数
    private int [ ] parent ; // parent[i]表示第i个元素所指向的父节点
    private int count ;     // 数据个数
    // 构造函数
    public UnionFind4 ( int count ) {
        rank = new int [ count ] ;
        parent = new int [ count ] ;
        this . count = count ;
        // 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
        for ( int i = ; i < count ; i ++ ) {
            parent [ i ] = i ;
            rank [ i ] = 1 ;
        }
    }
    // 查找过程, 查找元素p所对应的集合编号
    // O(h)复杂度, h为树的高度
    private int find ( int p ) {
        assert ( p >= && p < count ) ;
        // 不断去查询自己的父亲节点, 直到到达根节点
        // 根节点的特点: parent[p] == p
        while ( p != parent [ p ] )
            p = parent [ p ] ;
        return p ;
    }
    // 查看元素p和元素q是否所属一个集合
    // O(h)复杂度, h为树的高度
    public boolean isConnected ( int p , int q ) {
        return find ( p ) == find ( q ) ;
    }
    // 合并元素p和元素q所属的集合
    // O(h)复杂度, h为树的高度
    public void unionElements ( int p, int q ) {
        int pRoot = find ( p ) ;
        int qRoot = find ( q ) ;
        if ( pRoot == qRoot )
            return ;
        if ( rank [ pRoot ] < rank [ qRoot ] ) {
            parent [ pRoot ] = qRoot ;
        }
        else if ( rank [ qRoot ] < rank [ pRoot ] ) {
            parent [ qRoot ] = pRoot ;
        }
        else { // rank[pRoot] == rank[qRoot]
            parent [ pRoot ] = qRoot ;
            rank [ qRoot ] += 1 ;   // 维护rank的值
        }
    }
}