Which data structure technique is used to improve the performance of Union-Find by making the tree flatter?
Show answer
Path compression
Path compression occurs during the 'Find' operation, where every node on the path to the root is linked directly to the root. Combined with union-by-rank, it results in a nearly-constant amortized time complexity.
Also asked as:
- Which technique flattens the tree structure in a Union-Find data structure to improve performance?