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 \to 4 \to 2

, returns

2

and changes only

parent [3]

from

4

2

. The route

5 \to 6 \to 2

still has two edges. Then find(5) changes only

parent [5]

from

6

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.

Figure 1.
Full path compression shortens two parent routes while union by rank metadata stays unchanged
. 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. **Details**.

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.^[ref]

Path compression

 Ancestors (5)

 Incoming links (4)

 Discussion (0)

 Articles by others on the same topic (0)

Path compression

 Ancestors (5)

 Incoming links (4)

 Discussion (0)  Subscribe (1)

 Articles by others on the same topic (0)

 Discussion (0)