Weighted quick-union with path compression- Implementation

Question

I am implementing the quick union algorithm for a union/find structure. In the implementation given at the "Algorithms in Java" book site, the Princeton implementation fails to maintain the size invariant of tree while implementing path compression (in the find() method). Shouldn't this adversely affect the algorithm? or am I missing something? Also, if I am right, how would we go about modifying the size array?

Answer 1

Unless I'm mistaken, I think that this code is indeed maintaining the invariant that the root of each tree stores the number of nodes in its subtree.

When the data structure is created, note that the constructor sets sz[i] = 1 for each node in the forest. This means that the values start off correct.

During a union operation, the data structure correctly adjusts the size of the root of the merged trees. Therefore, after any union operation, all the tree roots have the correct sizes.

While you are correct that during path compression in the find step that the sizes aren't updated, there is no reason that the data structure would change sizes here. Path compression just reduces the length of the paths from nodes in some tree up to the root of the tree. It doesn't change the number of nodes stored in that tree. Accordingly, the size information at the root of the tree undergoing path compression does not need to change. Although some internal subtrees might lose some children as they are reparented higher up in the tree, this is irrelevant because the union/find structure only needs to maintain size information at the roots of its trees, not at internal nodes.

Overall, this means that the data structure does correctly store size information. There is no adverse impact on runtime, nor is there a need to correct anything.

Hope this helps!