Union-Find Operations
find climbs to the root then flattens the path. Union hangs the smaller root under the larger.
Union-Find: Path compression at work
find(0): parent[0] = 0, so 0 is a root already. Its set is 0.
Cost
- Best
- O(1)
- Average
- O(alpha(n)) amortized
- Worst
- O(log n)
- Space
- O(n)
Before this
Related
Taught by the same lesson
Union-Find covers these too, in the same run.