Union-Find

Union by Rank

Always attach the shallower tree under the deeper one. Rank labels on every node show the decision. Tree height stays bounded at O(log n).

Speed

Step 1/0

Forest — rank shown inside each node

Path A

Path B

Root A (higher rank)

Root B

Rank just incremented

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

…

Complexity

find(x)O(log n)

union(p,q)O(log n)

With compressionO(α(n))

SpaceO(n)

Max rank0

log₂(n)4

Active Recall1/3

When does union by rank increment a root's rank?

Union-Find

Loading visualizer…

Initialize