CODEWITHSUNDEEP
algorithmdata-structuresunion-find
synapse
synapse

Reputation: 5728

Why path compression doesn't change rank in UnionFind?

I'm looking at the implementation of UnionFind with union by rank and path compression from here http://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_forests (it's pretty much the same pseudo-code as in CLRS) and don't understand why path compression doesn't change rank. If we call find for an endpoint of the longest path from the root the rank should go down and if it doesn't the next union operation will choose an incorrect root.

Upvotes: 14

Views: 1979

Answers (2)

borrible
borrible

Reputation: 17366

Rank is not the actual depth of the tree rather it is an upper bound. As such, on a find operation, the rank is allowed to get out of sync with the depth.

Upvotes: 9

David Eisenstat
David Eisenstat

Reputation: 65478

"Rank" is one of those horribly overloaded terms in theoretical computer science. As Wikipedia notes, in the context of that disjoint set data structure with path compression, rank is not an intrinsic property of the current topology of the forest -- there's just no good way to keep the height of each node up to date. As defined by the sequence of unions, however, rank is useful in proving the running time bound involving the inverse Ackermann function.

Upvotes: 9

Related Questions