✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-208

Path 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.

Before

4 → 3 → 2 → 1

After

4 → 1, 3 → 1, 2 → 1

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

Language

Pseudocode

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

OperationComplexity

Find

O(α(n)) amortized

Union

O(α(n)) amortized

Space Complexity

O(n) for parent and rank arrays.

Key Concepts

  • Tree height

  • Path compression

  • Union by rank

  • Root representatives

  • Amortized analysis

  • Inverse Ackermann function

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

Related Topics

  • Disjoint Set Union

  • Union-Find

  • Amortized Time Complexity

  • Graph Algorithms

Practice Questions

QuestionAnswer

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.

  • Advanced Data Structures

Suggest a correction or source · More in Algorithms & Data Structures