Union-Find path compression
In the find function of the disjoint set union, path compression can be performed to more quickly find the root node of a node. For a set tree, many nodes can be attached under its root node. Therefore, during the find process, we can try to move the node upward as much as possible from bottom to top if the currently visited node is not the root node, thereby reducing the depth of the tree. This process is called path compression.
As shown in the figure below, the process of find(4) can use path compression to reduce the number of levels in the tree.
When node 4 searches upward for the root node, the first compression step reduces the tree's number of levels by one:
Node 2 also searches upward and is not the root node, so point element 2 to the parent of its original parent node. After this operation, the tree's number of levels is reduced by one accordingly, and root node 0 is returned.
Modify the find process code to:
// 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 path compression described above is not the optimal approach. We can compress the original tree into the form shown in the figure below, which has the minimum number of levels.
This find process can be represented as:
// 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);
// Second path compression algorithm
if (p != parent[p])
parent[p] = find(parent[p]);
return parent[p];
}
...
Java example code
Source code 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;
// Second path compression algorithm
//if( p != parent[p] )
//parent[p] = find( parent[p] );
//return parent[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
}
}
}