Union-Find: Do you do find operations in the union when using path compression

Question

My question is closely related to: https://stackoverflow.com/questions/49574421/path-compression-is-enough-for-disjoint-set-forests-why-do-we-need-union-by-ra#:~:text=We%20use%20both%20the%20union,the%20tree%20to%20almost%20one. Looking at the implementation in Wikipedia it seems that in the beginning of union we do:

x := Find(x)
y := Find(y)
if (x == y): nothing to do
do either rank/size based union

My understanding of path compression is that after the find operation we would have flattened the tree. If that was the case, wouldn't the rank of the two sets be the same?

Answer 1

The only thing that is really flattened is the paths from x and y to their roots. Paths from other nodes that eventually end up at the same roots, may be partially flattened, or not at all, depending on where they "connect" to the path that was followed to the root. There is no reasonable way to flatten the whole tree: we don't know what the leafs are (other than the node we start from), and even if we did it would be expensive to flatten them all (at least linear time in the size of the subset we're in, even if it already had been completely flattened before).

As such, it matters whether x is made the new root of y or the other way around.

Additionally, there are single-pass path-compression strategies that do not necessarily result in fully path-compressing the paths from x and y to their roots.