1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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(m \lg n)$ running time per operation, whereas using both Union by rank and path compression gives you a $O(\alpha(n))$ 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.