HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Do we need both path compression and union by rank together in disjoint set data structure?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
pathrankneedcompressionuniontogetherbothdisjointstructureand

Problem

I was studying disjoint set data structure. I studied path compression and union by rank. Initially all the elements are single in their own set and by performing unions we can combine different sets.
Now since we are performing union by rank the height of the resultant tree is always minimum. At this point i think that we might not need path compression at all. Am i right? If i am wrong please explain me with an example.

Solution

No, you are not right, at least not if you want the fastest possible running times. Using both is faster than using just one of them alone. Using just Union by rank gives you a $O(\lg n)$ amortized running time per operation, whereas using both Union by rank and path compression gives you a $O(\alpha(n))$ amortized running time per operation, which is asymptotically faster. Here $n$ is the number of elements and $m$ is the number of operations performed on them. See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Time_complexity.

Context

StackExchange Computer Science Q#92806, answer score: 2

Revisions (0)

No revisions yet.