Disjoint Set Path Compression

The find function in the Disjoint Set can perform path compression to expedite the search for the root node of a point. For a set tree, its root node can be attached with many other nodes. Therefore, we can attempt to compress the path during the find process by moving upward from the bottom. If the current node being accessed is not the root node, we can shift this node upward to reduce the tree's depth. This process is known as path compression.

In the diagram below, the find(4) process can be path-compressed, reducing the tree's depth.

When node 4 searches upward for the root node, the first step of compression reduces the tree's depth by one level:

When node 2 searches upward and is not the root node, element 2 is pointed to its parent's parent, reducing the tree's depth by one level and returning the root node 0.

The find process code modification is:

// Find process, find the set ID of element p
// O(h) complexity, h is the height of the tree
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 most optimal. We can compress the initial tree to the one shown below, with the minimum depth.

This find process is represented as:

...
// Find process, find the set ID of element p
// O(h) complexity, h is the height of the tree
private int find(int p) {
    assert (p >= 0 && p < count);

    // Second path compression algorithm
    if (p != parent[p])
        parent[p] = find(parent[p]);
    return parent[p];
}
...

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] indicates the depth of the tree represented by the set rooted at i
    private int[] parent; // parent[i] indicates 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 each element forms its own set
        for( int i = 0 ; i < count ; i ++ ){
            parent[i] = i;
            rank[i] = 1;
        }
    }

    // Find process, find the set ID of 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;

        // Second path compression algorithm
        //if( p != parent[p] )
        //parent[p] = find( parent[p] );
        //return parent[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 rank value
        }
    }
}