Union-Find Rank Optimization

The previous section introduced the Union-Find optimization based on size, but there are scenarios where issues can arise, as illustrated in the following figure with the operation union(4,2).

According to the previous section's size optimization, the root node of the smaller set points to the root node of the larger set. After the operation, the number of layers increases to 4, which is one more layer than before, as shown in the figure below:

It is evident that determining the direction based on the size of the sets is not entirely accurate. A more precise approach is to determine the direction of the root nodes based on the layers of the two sets, with the root node of the set with fewer layers pointing to the root node of the set with more layers. This is the optimization based on rank, as illustrated in the figure below.

We add a rank array to the properties of the Union-Find, where rank[i] represents the number of layers of the tree represented by the set with i as its root.

...
private int[] rank;   // rank[i] represents the number of layers of the tree represented by the set with i as its root
private int[] parent; // parent[i] represents the parent node of the i-th element
private int count;    // number of elements
...

The constructor needs to be modified accordingly:

...
// Constructor
public UnionFind4(int count){
    rank = new int[count];
    parent = new int[count];
    this.count = count;
    // Initialization, each parent[i] points to itself, indicating that each element forms its own set
    for( int i = 0 ; i < count ; i ++ ){
        parent[i] = i;
        rank[i] = 1;
    }
}
...

When merging two elements, it is necessary to compare the layers of the root nodes of the sets. The entire process is of 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;   // Maintain the rank value
    }
}
...

Java Example Code

Source Code Download: Download

UnionFind3.java File Code:

package tutorialpro.union;
/**
 * Rank-based optimization
 */
public class UnionFind4 {
    private int[] rank;   // rank[i] represents the number of layers of the tree represented by the set with i as its root
    private int[] parent; // parent[i] represents the parent node of the i-th element
    private int count;    // number of elements
    // Constructor
    public UnionFind4(int count){
        rank = new int[count];
        parent = new int[count];
        this.count = count;
        // Initialization, each parent[i] points to itself, indicating that each element forms its own set
        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 );
        // Continuously query the parent node until reaching the root node
        // Root node characteristic: parent[p] == p
        while( p != parent[p] )

p = parent[p];
return p;
}
// Check if 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 of elements p and 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
    }
}
}