concept · INFO-CS-ADS-208Path Compression and Union by Rank
Path Compression and Union by Rank are two optimization techniques that make Disjoint Set Union operations extremely efficient by keeping its internal trees shallow.
Explanation
Overview
Path Compression changes parent pointers during Find operations so that visited elements point directly to the root. Union by Rank combines two trees by attaching the shorter or lower-rank tree beneath the taller or higher-rank tree.
Key concepts
Tree height; Path compression; Union by rank; Root representatives; Amortized analysis; Inverse Ackermann function
Time complexity
operation: Find; complexity: O(α(n)) amortized; operation: Union; complexity: O(α(n)) amortized
Space complexity
O(n) for parent and rank arrays.
Example
scenario: A software feature needs to use path compression and union by rank.; task: Design a small, testable solution that demonstrates path compression and union by rank while satisfying the requirements described in this entry.; approach: Identify the input and expected output, apply the central idea of path compression and union by rank, and trace the result with a small representative dataset.; learningPoint: This path compression and union by rank example should be checked with ordinary inputs, boundary conditions, and a case that could expose an incorrect assumption.
Applications
Kruskal's minimum spanning tree algorithm; Dynamic connectivity; Large-scale graph processing; Network grouping; Connected-component maintenance
Advantages
Significantly reduces tree height.; Makes repeated connectivity operations very efficient.; Works especially well for large graph problems.; Combining both techniques gives excellent amortized performance.
Example or application
Scenario
A software feature needs to use path compression and union by rank.
Task
Design a small, testable solution that demonstrates path compression and union by rank while satisfying the requirements described in this entry.
Approach
Identify the input and expected output, apply the central idea of path compression and union by rank, and trace the result with a small representative dataset.
Learning Point
This path compression and union by rank example should be checked with ordinary inputs, boundary conditions, and a case that could expose an incorrect assumption.
Definition
Path Compression changes parent pointers during Find operations so that visited elements point directly to the root. Union by Rank combines two trees by attaching the shorter or lower-rank tree beneath the taller or higher-rank tree.
Path Compression
Description
During a Find operation, the algorithm follows parent pointers to reach the root. Path compression then updates the visited nodes so that they point directly to that root.
Benefit
Future Find operations require fewer parent-pointer traversals.
Union By Rank
Description
Rank is an estimate of a tree's height. When merging two trees, the algorithm attaches the root with smaller rank beneath the root with larger rank. If both ranks are equal, one root becomes the parent and its rank increases by one.
Rules
If rank[rootA] is smaller, attach rootA under rootB.
If rank[rootB] is smaller, attach rootB under rootA.
If both ranks are equal, choose one root as the parent and increase its rank by one.
Benefit
Prevents the unnecessary growth of tall trees during repeated Union operations.
Implementation
Code
function find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
function union(a, b):
rootA = find(a)
rootB = find(b)
if rootA == rootB:
return
if rank[rootA] < rank[rootB]:
parent[rootA] = rootB
else if rank[rootA] > rank[rootB]:
parent[rootB] = rootA
else:
parent[rootB] = rootA
rank[rootA] += 1
Time Complexity
| Operation | Complexity |
|---|
Find | O(α(n)) amortized |
Union | O(α(n)) amortized |
Space Complexity
O(n) for parent and rank arrays.
Complexity Explanation
The function α(n) is the inverse Ackermann function. It grows so slowly that its value remains extremely small for all practical input sizes. Therefore, DSU operations with both optimizations are effectively constant time in typical applications.
Advantages
Significantly reduces tree height.
Makes repeated connectivity operations very efficient.
Works especially well for large graph problems.
Combining both techniques gives excellent amortized performance.
Limitations
The implementation is more complex than basic Union-Find.
Path compression changes the internal structure during Find.
Rank is an approximate height measure rather than an exact current height after compression.
Applications
Kruskal's minimum spanning tree algorithm
Dynamic connectivity
Large-scale graph processing
Network grouping
Connected-component maintenance
Practice Questions
| Question | Answer |
|---|
What does path compression do? | It makes visited nodes point directly to the root during Find. |
What is the purpose of Union by Rank? | It attaches the shorter tree beneath the taller tree to control tree height. |
What is the amortized complexity of optimized DSU operations? | O(α(n)), where α is the inverse Ackermann function. |
Learning Objectives
Explain the central idea and purpose of path compression and union by rank.
Identify the assumptions, inputs, and conditions relevant to path compression and union by rank.
Evaluate an application of path compression and union by rank for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
Suggest a correction or source · More in Algorithms & Data Structures