Algorithms and Data Structures · Senior · Question 6 of 75
What makes union-find operations nearly O(1)?
- 1Keeping every set as a sorted array
- ✓Correct answer: Path compression plus union by rank or size
- 3Rebuilding the whole structure after each union
Explanation
Path compression points nodes directly at the root during find; union by rank attaches the shorter tree under the taller. Together they give O(α(n)) amortized, where α (inverse Ackermann) is below 5 for any realistic n.