Optimization of rank in Union-Find
The previous subsection introduced size-based optimization for the union-find data structure, but in certain scenarios, some problems still exist, as shown in the figure below, performing the operation union(4,2).
According to the previous subsection, with size-based optimization, the root of the set with fewer elements points to the root of the set with more elements. After the operation, the number of levels becomes 4, which is one level more than before, as shown in the figure below:
It can be seen that relying on the size of the set to determine the direction of the pointer is not entirely correct. More accurately, the direction of the root pointer should be determined based on the number of levels of the two sets: the root of the set with fewer levels points to the root of the set with more levels, as shown in the figure below. This is rank-based optimization.
We add a rank array to the properties of the union-find data structure, where rank[i] represents the number of levels of the tree represented by the set rooted at i.
private int[] rank; // rank[i] represents the number of levels of the tree represented by the set rooted at i
private int[] parent; // parent[i] represents the parent node that the i-th element points to
private int count; // number of data elements
...
The constructor should be modified accordingly:
// constructor
public UnionFind4(int count){
rank = new int[count];
parent = new int[count];
this.count = count;
// initialize, each parent[i] points to itself, indicating that each element forms a set by itself
for( int i = 0 ; i < count ; i ++ ){
parent[i] = i;
rank[i] = 1;
}
}
...
When merging two elements, it is necessary to compare the number of levels of the sets of root nodes. The entire process has O(h) complexity, where h is the height of the tree.
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; // at this point, I maintain the rank value
}
}
...
Java example code
Source package download:Download
UnionFind3.java file code:
/**
* Rank-based optimization
*/
public class UnionFind4 {
private int[] rank; // rank[i] represents the number of levels of the tree represented by the set rooted at i
private int[] parent; // parent[i] represents the parent node that the i-th element points to
private int count; // number of data elements
// constructor
public UnionFind4(int count){
rank = new int[count];
parent = new int[count];
this.count = count;
// initialize, each parent[i] points to itself, indicating that each element forms a set by itself
for( int i = 0 ; i < count ; i ++ ){
parent[i] = i;
rank[i] = 1;
}
}
// find process, find the set number corresponding to element p
// O(h) complexity, h is the height of the tree
private int find(int p){
assert( p >= 0 && p < count );
// keep querying the parent node until reaching the root node
// characteristic of root node: parent[p] == p
while( p != parent[p] )
p = parent[p];
return p;
}
// check whether element p and element q belong to the same set
// O(h) complexity, h is the height of the tree
public boolean isConnected( int p , int q ){
return find(p) == find(q);
}
// merge the sets containing element p and element q
// O(h) complexity, h is the height of the tree
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; // maintain the rank value
}
}
}