The disjoint set class - Data Structures and Problem Solving Using Java - page 915

when union operations are performed—even with path compression—we are
using ranks, or estimated heights. These ranks behave as if there is no path
compression. Thus when the number of nodes of rank r are being bounded,
path compression can be ignored, as in Theorem 24.2.

Theorem 24.2

The number of nodes of rank r is at most N /2 r .

Without path compression, each node of rank r is the root of a subtree of at least 2 r
nodes. No other node in the subtree can have rank r . Thus all subtrees of nodes of
rank r are disjoint. Therefore there are at most N /2 r disjoint subtrees and hence
N /2 r nodes of rank r .

Proof

Theorem 24.3 seems somewhat obvious, but it is crucial to the analysis.

At any point in the union/find algorithm, the ranks of the nodes on a path from a leaf
to a root increase monotonically.

Theorem 24.3

Proof

The theorem is obvious if there is no path compression. If after path compression,
some node v is a descendant of w , then clearly v must have been a descendant of w
when only union operations were considered. Hence the rank of v is strictly less than
the rank of w .

The following is a summary of the preliminary results. Theorem 24.2
describes the number of nodes that can be assigned rank r . Because ranks are
assigned only by union operations, which do not rely on path compression,
Theorem 24.2 is valid at any stage of the union/find algorithm—even in the
midst of path compression. Theorem 24.2 is tight in the sense that there can be
nodes for any rank r . It also is slightly loose because the bound cannot
hold for all ranks r simultaneously. While Theorem 24.2 describes the number
of nodes in a rank r, Theorem 24.3 indicates the distribution of nodes in a
rank r. As expected, the rank of nodes strictly increases along the path from a
leaf to the root.
We are now ready to prove the main theorem, and our basic plan is as fol-
lows. A find operation on any node v costs time proportional to the number of
nodes on the path from v to the root. We charge 1 unit of cost for every node
on the path from v to the root during each find . To help count the charges, we

There are not too
many nodes of
large rank, and the
ranks increase on
any path up toward
a root.

N 2 r ⁄