path compression
A union-find optimisation: after finding a root, point every node visited on the way directly at that root.
In more detail
Later finds on those nodes take one step instead of many. It changes only the shape of the internal trees, never which group an item belongs to, so results stay correct.
Related terms
- 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".
- 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.
Taught in
- Minimum Spanning Trees: Kruskal And Prim — Algorithms & Data Structures for Working Engineers