union find disjoint set weighted quick union with path compression algorithm

Question

Concerning this question about union find disjoint set , weighted quick union with path compression algorithm

Weighted Quick-Union with Path Compression algorithm

does the path compression affect the iz[] array (array that contain length of the tree rooted at i) ?

Answer 1

I would start quoting a few basic points. First of all this is the most optimal algorithm for implementing disjoint set and referred as Union by rank with path compression heuristic. This algorithm requires 2 arrays, first(id[] there) is used as a link to parent and the second(iz[]) gives the number of nodes int that set.

We have 2 operations- Union and connected.

Union is done by 'rank' which leads to lower amortized cost for further operations by making the smaller tree child of the bigger one, by this the length tends to be minimum.

When connected method is called, after we get to know the root of that tree, we use a path compression technique which basically points that particular node to the root of that tree so in future we don't have to traverse the whole branch again. Since iz[] just contains the number of nodes of that set, it does not have any effect by path compression.

Answer 2

As far as I understood the code, the array iz[] represents the amount of elements in a given disjoint set. When you compress the path, you don't modify that number for each set. Thus, the path compression does not affect the iz[] array.