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.
$\begingroup$
$\endgroup$
asked Jun 6, 2018 at 18:11
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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.
