naveenath naveenath - 3 months ago 14
Java Question

Path Compression , How does this code is path compression?

/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package algorithm1;

/**
*
* @author Navin
*/

public class QuickUnionWeighted {


private int [] id;
private int [] size;
int numberOfChild;
int j=0;

public QuickUnionWeighted(int N){

id = new int[N];
size = new int[N];

for(int i=0;i<N;i++){

id[i] = i;
size[i]=1;
}


}

public int root(int i){

while (i != id[i]){
id[i] = id[id[i]];
i=id[i];


}

return i;
}

public boolean connected(int p,int q){

return(root(p) == root(q));
}


public void union(int p,int q){

int i = root(p);
int j = root(q);

// if(i == j) return;

if(size[i] < size[j]){

id[i] = j;
size[j] += size[i];
}else{
id[j] = i;
size[i] +=size[j];
}


for(int k=0;k<size.length;k++){
System.out.print(size[k]+" ");

}

}


public static void main(String [] args){


QuickUnionWeighted quw = new QuickUnionWeighted(10);


quw.union(3,0);
quw.union(4, 0);
quw.union(3, 5);
quw.union(3, 6);
quw.union(3,9);



}



}


Because as I examined the code, the
id[i] = id[id[i]]
is pointing to the parent of the node, and the examined node is not moved to its grandparents and the tree is not flattened.

Kindly Guide.

Answer
id[i] = id[id[i]];

This line is the path compression. id[i] is the parent of node i. Hence, this line re-links node i to its grand-parent. Therefore, it skips the parent. Then, the same happens to the grand-parent and so on. This flattens the tree.

Here is a visualization of this step:

1                    1
^                   / \
|     root(3)      /   \
2    -------->   2       3
^
|
3