= Union by rank
{title2=$\operatorname{rank}(r)$}
<Union by rank> keeps a nonnegative <integer> rank, initially zero, for each member. For each input, obtain its <root of a tree> using the <disjoint-set find operation>, then compare the resulting ranks. Attach the lower-rank <root of a tree> below the higher-rank <root of a tree>, leaving both ranks unchanged. When the two <disjoint-set representatives> differ but their ranks are equal, choose either survivor and increase its rank by exactly one. A redundant <disjoint-set union operation> changes no ranks. <Path compression> also changes no ranks. The surviving root's rank bounds the height of its <rooted tree>, measured in <edges>; after <path compression> it need not equal that height.<COS 226 Bob’s Notes 1: Union-Find and Percolation (Version 2) by Robert Tarjan>[Robert Tarjan, COS 226 Bob’s Notes 1: Union-Find and Percolation, Version 2, Fall 2010, p. 4: rank linking, equal-rank increment and upper-bound interpretation after compression]{ref}
In our example, let the first argument's <root of a tree> survive equal-rank ties. The first two merges create roots $2,4$, each of rank $1$. The third gives $\mathrm{parent}[4]=2$ and increases the rank of $2$ to $2$. The fourth creates root $6$ of rank $1$. The fifth attaches $6$ below $2$ without increasing any rank. Before any subsequent compression queries, the indexed <arrays> are
$$
\begin{array}{c|rrrrrrr}
x&1&2&3&4&5&6&7\\\hline
\mathrm{parent}[x]&2&2&4&2&6&2&7\\
\mathrm{rank}[x]&0&2&0&1&0&1&0
\end{array}
$$
The redundant call on $1,2$ leaves these <arrays> unchanged. In particular, the <disjoint-set representative> of $1$ is $2$, although $1$ is the <minimum> member of its <block of a set partition>.
Two short arguments explain the rank invariant. First, a root of rank $r$ has at least $2^r$ members in its <block of a set partition>: rank zero starts with one, and increasing rank combines two disjoint <blocks of a set partition> with at least $2^r$ members each. Unequal-rank linking only adds members. Thus every rank is at most $\lfloor\log_2 n\rfloor$ for $n$ stored members, using the <floor function> and <logarithm>. Second, height is initially zero; unequal-rank linking adds at most one to the lower height, while equal-rank linking raises the available bound by one. <Path compression> only shortens routes. These arguments prove a height bound, not the stronger <amortized analysis> below.
Back to article page
