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

figure 24.22
Possible partitioning
of ranks into groups

Group Rank

0 0

1 1

2 2,3,4

3 5 through 9

4 10 through 16

( i - 1) 2 through i 2 i

compression. Thus we must use some fact about path compression in our
analysis. The key observation is that, as a result of path compression, a node
obtains a new parent and the new parent is guaranteed to have a higher rank
than the old parent.

To incorporate this fact into the proof, we use the following fancy
accounting: For each node v on the path from the accessed node i to the root,
we deposit one penny in one of two accounts.

Rules for U.S. and
Canadian deposits.

1. If v is the root or if the parent of v is the root or if the parent of v is in

a different rank group from v, then charge 1 unit under this rule and
deposit a U.S. penny in the kitty.

2. Otherwise, deposit a Canadian penny in the node.

Theorem 24.4 states that the accounting is accurate.

For any find operation, the total number of pennies deposited, either in the kitty or in
a node, is exactly equal to the number of nodes accessed during the find .

Theorem 24.4

Proof

Obvious.

Thus we need only sum all the U.S. pennies deposited under rule 1 and all
the Canadian pennies deposited under rule 2. Before we go on with the proof,
let us sketch the ideas. Canadian pennies are deposited in a node when it is
compressed and its parent is in the same rank group as the node. Because the