YouTipThe previous section introduced the Union-Find based on size optimization, but in some scenarios, there can still be some problems, as shown in the figure below, the operation union(4,2).
According to the previous section, the size optimization makes the root node of the set with fewer elements point to the root node of the set with more elements. After the operation, the level becomes 4, which is one more than before, as shown in the figure below:
From this we can see that relying on the size of the set to determine the direction is not completely correct. More accurately, based on the levels of the two sets, we determine the direction of the root node specifically - the root node of the set with fewer levels points to the root node of the set with more levels, as shown in the figure below. This is the optimization based on rank.
We add a rank array to the Union-Find attributes, where rank represents the level of the tree represented by the set with i as the root.
...
private int[] rank;// rank represents the level of the tree represented by the set with i as the root
private int[] parent;// parent represents the parent node that the i-th element points to
private int count;// number of data elements
...
The constructor is modified accordingly:
...
// constructor
public UnionFind4(int count){
rank = new int;
parent = new int;
this.count = count;
// initialization, each parent points to itself, indicating that each element forms its own set
for(int i = 0; i < count ; i ++){
parent = i;
rank = 1;
}
}
...
When merging two elements, we need to compare the levels of the root node sets. 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 < rank ){
parent = qRoot;
}
else if( rank < rank ){
parent = pRoot;
}
else{ // rank == rank
parent = qRoot;
rank += 1; // at this time, we maintain the rank value
}
}
...
Java Example Code
Source Package Download:Download
UnionFind3.java File Code:
package tutorial.union;
/**
* Rank-based optimization
*/
public class UnionFind4 {
private int[] rank;// rank represents the level of the tree represented by the set with i as the root
private int[] parent;// parent 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;
parent = new int;
this.count = count;
// initialization, each parent points to itself, indicating that each element forms its own set
for(int i = 0; i < count ; i ++){
parent = i;
rank = 1;
}
}
// find the root node of p
// O(h) complexity, h is the height of the tree
public int find(int p){
assert(p >= 0 && p < count );
// continuously query its parent node until reaching the root node
// characteristic of root node: parent == p
while( p != parent )
p = parent;
return p;
}
// check whether elements p and 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 that elements p and q belong to
// 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 < rank ){
parent = qRoot;
}
else if( rank < rank ){
parent = pRoot;
}
else{ // rank == rank
parent = qRoot;
rank += 1; // at this time, we maintain the rank value
}
}
}