8
Components
-
Active Parent
0
Active Rank
0
Path Compress
Ready
Status
Current traversal path
Chosen representative root
Rank comparison
Compressed parent pointer
Operation Timeline
How It Works
Union-Find maintains a forest of parent pointers. Each set is represented by a root. find(x) walks to the root, and path compression rewires every visited node to point directly to that root. union(a, b) attaches the shallower tree below the deeper tree using rank.
- Union by rank keeps trees shallow.
- Path compression flattens paths after every find.
- Together they make the amortized cost almost constant.