0
$\begingroup$

Union-By-Rank and Path Compression is supposed to improve the performance of a tree implementation of a disjoint set.

However, in looking at the UNION(x, y) operation, I noticed that if x and y are actually the roots of the 2 trees being merged, no path compression actually takes place. The resulting tree would simply have a depth equal to the larger depth of the 2 trees.

Is my understanding of the algorithm correct?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

I assume you are talking about Union Find data structure. When you do UNION($x,y$), you just change the parent pointer of one of $x$ and $y$ to root of the other. The depth of resulting tree is not exactly equal to larger depth of two trees because, initially if the depth of two trees are equal, then the depth of new tree formed will be $1$ plus the old depth.

Coming to the original question, path compression takes place when we do FIND operations and not during UNION operations. When we do FIND($x$), we first find root $p$ of $x$ and for all ancestors of $x$ and also for $x$, we change the root pointer to $p$. You can see that this can reduce the height of tree drastically. After some FIND operations, next FIND operations will take time close to $O(1)$. This is formalised by saying that $n$ FIND operations take time $O(n\alpha(n))$ where $\alpha(n)$ is the inverse Ackermann function.

Improve this answer
$\endgroup$
4
  • $\begingroup$ if d1 and d2 are the depth of the 2 trees, after UNION it is stil true that the depth of the merged tree = max(d1, d2) even if d1 = d2. You are right that the UNION does not necessarily call FIND. The UNION algorithm I was looking at was UNION(x, y) -> LINK(FIND(x), FIND(y)). You can see that if x and y are the roots then behaviour of UNION is as you described. However, if either x or y or both are not, then path compression occurs. $\endgroup$
    – EggHead
    Mar 14, 2014 at 17:17
  • $\begingroup$ Suppose we started at all the elements in different trees. All of them have depth 1. If depth of merged tree == max(d1, d2), then the depth of new trees must never exceed 1. Or am I missing something? $\endgroup$
    – nitishch
    Mar 14, 2014 at 17:20
  • $\begingroup$ no you are not. If the 2 trees have equal depth, then yee, resulting depth will be d + 1. However, my question was really about the UNION(x, y) when x and y are the roots. In this case, according to the algorithm in CLRS, since the search path consists only of the root, no path compression takes place. $\endgroup$
    – EggHead
    Mar 14, 2014 at 21:36
  • $\begingroup$ Yes exactly. Previously I didn't see your edited question. $\endgroup$
    – nitishch
    Mar 15, 2014 at 6:14

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.