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

Taught in

References