Overview
Persistent Union-Find is a persistent data structures method for versioned connectivity. It works by recording parent and rank changes so older connectivity states remain queryable.
SpecializedSource checked
Persistent Union-Find
Persistent Union-Find addresses versioned connectivity by recording parent and rank changes so older connectivity states remain queryable.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Advanced
- Family
- Persistent Data Structures
- Tier
- Specialized
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 2
- Code example
- Not ready
- Visualization
- Ready
Core Concepts
versioned connectivitypersistent data structuresdata structures
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(log n)
Worst
O(n)
Space
O(n)
When to Use
- Use Persistent Union-Find when solving versioned connectivity and you want to benefit from recording parent and rank changes so older connectivity states remain queryable.
- Choose it when O(log n) average/worst-case time and O(n) memory match your workload profile.
- Prefer it over Biconnected Components or Lengauer-Tarjan Dominators when the problem structure favors versioned connectivity.
When Not to Use
- Avoid when the query pattern is too simple to justify the structure's overhead.
- Avoid when memory layout or rebuild cost dominates the expected speedup.
What It Does
- Computes versioned connectivity within Persistent Data Structures workloads (O(log n) time, O(n) space).
- Works by recording parent and rank changes so older connectivity states remain queryable.
- Maintains key invariants across versioned connectivity, persistent data structures, data structures.
Use Cases
- Production and research workloads requiring versioned connectivity via recording parent and rank changes so older connectivity states remain queryable.
- Persistent Data Structures pipelines where O(log n) time and O(n) space fit system constraints.
- Engineering comparisons against Biconnected Components and Lengauer-Tarjan Dominators when tuning versioned connectivity.
Inputs
- Keys, values, items, or graph records
- Operations such as insert, delete, or query
Outputs
- Stored structure state
- Query result or updated collection
Pseudocode
- 1.Allocate the node layout, bit-vectors, or hierarchical buckets required by Persistent Union-Find.
- 2.Establish structural invariants over versioned connectivity and persistent data structures.
- 3.Execute queries or updates by recording parent and rank changes so older connectivity states remain queryable.
- 4.Rebalance, split/merge, or refresh auxiliary pointers to preserve logarithmic/sub-logarithmic bounds.
- 5.Return the queried value, membership result, or updated structure handle.
Canonical Example
- Input
- Keys, values, items, or graph records configured for a representative versioned connectivity test case
- Output
- Stored structure state satisfying Persistent Union-Find invariants
- Explanation
- Persistent Union-Find processes the input by recording parent and rank changes so older connectivity states remain queryable, tracking versioned connectivity and persistent data structures to produce the verified versioned connectivity result.
Implementation Notes
- Measure operations separately for insert, delete, query, and rebuild.
- Expose invariants in tests when balancing or compression is involved.
- Account for memory layout when performance matters.
Common Pitfalls
- Choosing the structure without matching it to the query/update pattern.
- Ignoring worst-case behavior behind favorable average-case examples.
- Forgetting memory overhead and rebuild costs.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow recording parent and rank changes so older connectivity states remain queryable on a small versioned connectivity example.
Step 1 of 5: Allocate the node layout, bit-vectors, or hierarchical buckets required by Persistent Union-Find.
data-structures-mechanismNotes
Persistent Union-Find operates in O(log n) time and O(n) space within the Persistent Data Structures family. Often compared with Biconnected Components and Lengauer-Tarjan Dominators.
Sources (1)
What each reference supports for this entry.
Making Data Structures Persistent
PaperReference for persistent data structures and versioned updates applicable to persistent disjoint-set structures.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageVariant ofUnion-Find
Persistent union-find is a versioned disjoint-set structure that preserves historical connectivity states.
Conceptual neighborPersistent Segment Tree
Both use persistence techniques to query older versions of an evolving structure.
Related Algorithms
Tags
Data Structure