Tag
disjoint-sets
- Jul 9, 2026 Cache Behaviour and Node Layout in Disjoint-Set Arrays Why a find is a dependent-load chain, how index width and array splitting change the number of cache lines touched, and what key remapping costs before the first union. data structures
- Dec 11, 2025 Rollback Union-Find and Offline Dynamic Connectivity How to undo a union by recording only the parent slot it overwrote, and how a segment tree over time turns edge insertions and deletions into a stack of reversible merges. data structures
- Dec 2, 2025 Union by Rank and Path Compression: Two Heuristics That Fix the Chain How attaching the smaller tree under the larger bounds forest height, how rewriting parent links during a find flattens future traversals, and why the two heuristics must be analysed together. data structures
- Oct 9, 2025 The Potential Function Behind the Inverse-Ackermann Union-Find Bound Disjoint-set forests with union by rank and path compression cost O(m alpha(n)) for m operations, and the proof is a ranked accounting over nodes rather than any single tree shape. algorithms
- Apr 5, 2025 Parent-Pointer Forests as the Representation of Disjoint Sets How a partition of n elements is stored as a single array of parent indices, what find and union do to that array, and which questions the representation cannot answer. data structures
- Jun 3, 2024 The Inverse Ackermann Bound and Why It Is Effectively Constant How the α(n) function is defined, why the amortized cost of a disjoint-set sequence lands there, and what the matching lower bound says about improving it. data structures