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.
In more detail
Rank is an upper bound on a tree's height; the tree only grows taller when two equal ranks merge. Together with path compression it keeps every tree extremely flat.
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".
- path compression — A union-find optimisation: after finding a root, point every node visited on the way directly at that root.
Taught in
- Minimum Spanning Trees: Kruskal And Prim — Algorithms & Data Structures for Working Engineers