并查集 rank 的优化

Dear 丶 2024-03-16 23:48 8阅读 0赞

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

![71cc2c79c55c2c77840a35588e2344cf.png][]

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

![67e2aefcbc7434dbd3284a765a6540ee.png][]

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

![de22405a7118b182edcef8798d44ef54.png][]

我们在并查集的属性中，添加 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 = 0 ; 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 实例代码 ####

### UnionFind3.java 文件代码： ###

> package runoob.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 = 0 ; i < count ; i ++ )\{  
> parent\[i\] = i;  
> rank\[i\] = 1;  
> \}  
> \}  
> // 查找过程, 查找元素p所对应的集合编号  
> // O(h)复杂度, h为树的高度  
> private int find(int p)\{  
> assert( p >= 0 && 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的值  
> \}  
> \}  
> \}

[71cc2c79c55c2c77840a35588e2344cf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/4a09929f0f4a46ec862facfe4bc6be7c.png
[67e2aefcbc7434dbd3284a765a6540ee.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/f95bf9e9c2f94881809d20e31a9fcba1.png
[de22405a7118b182edcef8798d44ef54.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/bf7c9ac5250c4b0e9bdfcaf4de8da6ff.png