Why doesn't path compression change rank in UnionFind?

Question

I look at the UnionFind implementation with a union for rank and path compression here http://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_forests (this is almost the same pseudo-code as in CLRS) and I don’t understand why path compression does not change rank. If we call find for the endpoint of the longest path from the root, the rank should go down, and if the wrong root is not selected in the next union operation.

Answer 1

"Rank" is one of those terribly overloaded terms in theoretical computer science. As Wikipedia notes, in the context of this disjoint data set structure with path compression, rank is not an internal property of the current forest topology - there simply is no good way to keep the height of each node up to date. However, as determined by the sequence of unions, the rank is useful in checking the time reference of time associated with the inverse Ackerman function.

Answer 2

The rank is not the actual depth of the tree, but the upper bound. Thus, in a find operation, a rank may go out of sync with depth.