union-find
A data structure that tracks which items belong to the same group, supporting "find the group of x" and "merge the groups of x and y".
In more detail
Each group is a tree whose root names the group, and find follows parent pointers to the root. With path compression and union by rank, both operations take amortised time that grows so slowly, with the inverse Ackermann function, that it is effectively constant. Kruskal's algorithm uses it to avoid creating cycles.
Related terms
- path compression — A union-find optimisation: after finding a root, point every node visited on the way directly at that root.
- union by rank — A union-find rule: when merging two groups, attach the root of the shallower tree under the root of the deeper one.
- Kruskal's algorithm — An algorithm that builds a minimum spanning tree by sorting all edges by weight and adding each one unless it would create a cycle.
- inverse Ackermann function — A function that grows so slowly it is at most 4 for any input size that could ever exist, used to express union-find's amortised cost.
Taught in
- Bloom Filters: Membership Without The Data — Algorithms & Data Structures for Working Engineers
- Minimum Spanning Trees: Kruskal And Prim — Algorithms & Data Structures for Working Engineers