CODEWITHSUNDEEP
algorithmdata-structuresdisjoint-sets
Vimit Dhawan
Vimit Dhawan

Reputation: 677

Do we need to update the ranks while path compression in Disjoint set data structure?

I was studying disjoint set data structure. I understand how rank helps us make shallow trees and path compression decrease tree height.

I can find the below code in most articles or study materials for path compression.

int find(subset[] subsets, int I) {
    if (subsets[i].parent != I) {
        subsets[i].parent= find(subsets, subsets[i].parent);
        return subsets[i].parent;
    }
}

I am wondering what about ranks. When we will do path compression the rank for the root also change but we did not update that. Could you please explain to me if I am missing something?

I have checked with the online tool so it looks like if we don't update the rank then it would not work as expected. I think it's more about the approximation of path compression. I am thinking in the worst-case scenario it can possible to create a dense tree.

enter image description here

Upvotes: 3

Views: 516

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59303

No, you don't update the ranks in path compression. In fact the reason that the word "rank" is used instead of "height", is because the rank doesn't accurately reflect the height, because it isn't updated in path compression.

Rank is a worst-case height that is accurate enough to provide the promised complexities. Whenever I write a union-find structure, though, I use the size of the subtree instead of rank. It works just as well and is also useful for other things.

Upvotes: 1

Related Questions