# Disjoint Set - Tree Implementation with Union-By-Rank and Path Compression

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?

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.