And look up the find function in the set can do path compression, in order to more quickly find the root node of a point. For a set tree, its root node can be attached to many nodes, so we can try in the process of find, from the bottom up, if the node visited at this time is not the root node, then we can move this node up as far as possible, reduce the number of layers, this process is called path compression.
In the following figure, the process of find (4) can be compressed to reduce the number of layers of the tree.
When node 4 looks up for the root node, the first step of compression reduces the number of layers of the tree by one layer:
Node 2 looks up and is not the root node, so point element 2 to the parent node of the original parent node, reduce the number of layers of the tree by one layer, and return to the root node 0 at the same time.
The find procedure code is modified to:
// 查找过程, 查找元素p所对应的集合编号
// O(h)复杂度, h为树的高度
private int find(int p){
assert( p >= 0 && p < count );
// path compression 1
while( p != parent[p] ){
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
The above path compression is not the best way, we can compress the initial tree into the following figure, the number of layers is the least.
The representative of the find process is represented as:
...
// 查找过程, 查找元素p所对应的集合编号
// O(h)复杂度, h为树的高度
private int find(int p) {
assert (p >= 0 && p < count);
//第二种路径压缩算法
if (p != parent[p])
parent[p] = find(parent[p]);
return parent[p];
}
...
5.27.1. Java instance code ¶
源码包下载： Download UnionFind3.java file code: ¶
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;
//第二种路径压缩算法
//if( p != parent[p] )
//parent[p] = find( parent[p] );
//return parent[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的值
}
}
}