= Path compression
<Path compression> changes parent pointers during a <disjoint-set find operation> so that future queries traverse fewer <edges>. Full <path compression> first follows the entire parent route to its <root of a tree>, then makes every member on that route point directly to that same <root of a tree>. No member changes its <block of a set partition> or its <disjoint-set representative>. Pointers outside the traversed route stay as they were. The following iterative Python implements full <path compression> and <union by rank>; `parent` and `rank` are initially indexed <arrays> with `parent[x] = x` and `rank[x] = 0` for every valid member.
``
def find(x):
root = x
while parent[root] != root:
root = parent[root]
while parent[x] != x:
following = parent[x]
parent[x] = root
x = following
return root
def unite(x, y):
a, b = find(x), find(y)
if a == b:
return False
if rank[a] < rank[b]:
a, b = b, a
parent[b] = a
if rank[a] == rank[b]:
rank[a] += 1
return True
``
Starting from the displayed <disjoint-set forest>, `find(3)` traverses $3\to4\to2$, returns $2$ and changes only $\mathrm{parent}[3]$ from $4$ to $2$. The route $5\to6\to2$ still has two <edges>. Then `find(5)` changes only $\mathrm{parent}[5]$ from $6$ to $2$. The final parent <array> is $(2,2,2,2,2,2,7)$; every stored rank retains its displayed value. The <rooted tree> at $2$ now has height one although its root's rank is two. Root $7$ still represents a separate <singleton set>.
\Image[/disjoint-set-union-path-compression-rank.png]
{title=Full <path compression> shortens two parent routes while <union by rank> metadata stays unchanged}
{description=Arrows point towards the <parent in a rooted tree>; self-pointers at roots are omitted. The same <partition of a set> appears before and after `find(3)` followed by `find(5)`. Labels $r$ record stored ranks, including historical ranks at nonroots.}
The two-pass <algorithm> first discovers the answer and then reuses it. During the second pass, saving `following` before overwriting the pointer preserves the remaining route. Every replacement pointer targets the original <root of a tree>, proving that the <partition of a set> is unchanged.
Full <path compression> is one specific rule. The authored `UF.java` implementation instead uses path halving, redirecting a visited member to its parent's parent while advancing along the route. Its <union by rank> rule agrees with the one above.<Algorithms, 4th edition by Robert Sedgewick and others/UF.java>[Algorithms, 4th edition by Robert Sedgewick and others; UF.java, find and union methods: halving assignment versus the full-compression algorithm here; lower-rank linking and equal-rank increment]{ref}
Back to article page
