Union-Find

Path Compression

After find(x), every node on the walked path is re-pointed directly to the root. Tall chains flatten to stars in one pass.

Speed

Step 1/0

Forest

Walking path

Being compressed

Compressed → root

Root node

union(0,1)union(1,2)union(2,3)union(3,4)find(0)union(5,6)union(6,7)find(5)union(4,7)

Purple = find() with compression

…

Complexity

find(x)O(log* n) amort.

union(p,q)O(log* n) amort.

SpaceO(n)

Active Recall1/3

What does path compression do to the parent pointers after find(x)?

Union-Find

Loading visualizer…

Initialize