CODEWITHSUNDEEP
algorithmtreeunion-find
Tesseract_R
Tesseract_R

Reputation: 39

In a Union-Find algorithm, whether/how to adjust the rank of a node in path compression

Path compression involves assigning the root as the new parent of every node on the path - this may reduce the rank of the root, and possibly the rank of all nodes on the path. Is there a way to deal with this? And is it necessary to deal with this? Or perhaps is it okay to think of rank as the upper bound of the height of the tree instead of the exact height?

Thanks!

Upvotes: 1

Views: 160

Answers (2)

Mishka
Mishka

Reputation: 73

If we are talking about common algorithm of path compression, I think in general it is not possible to decrease the root's rank - because many paths may be connected into this root, not only the path being compressed right now.

Upvotes: 0

David Eisenstat
David Eisenstat

Reputation: 65468

Yes, you can think of the rank as being an upper bound on the height. Its purpose is to limit the lengths of paths to at most logarithmic, by enforcing the invariant that a tree with less than 2^k nodes has height less than k.

Upvotes: 2

Related Questions