Java Reference
In-Depth Information
U.S. charges are
limited by the num-
ber of different
groups. Canadian
charges are limited
by the size of the
groups. We eventu-
ally need to balance
these costs.
node gets a parent of higher rank after each path compression and because the
size of a rank group is finite, eventually the node obtains a parent that is not in
its rank group. Consequently, on the one hand, only a limited number of
Canadian pennies can be placed in any node. This number is roughly the size
of the node's rank group. On the other hand, the U.S. charges are also limited,
essentially by the number of rank groups. Thus we want to choose both small
rank groups (to limit the Canadian charges) and few rank groups (to limit the
U.S. charges). We are now ready to fill in the details with a rapid-fire series of
theorems, Theorems 24.5-24.10.
Theorem 24.5
Over the entire algorithm, the total deposits of U.S. pennies under rule 1 amount to
M ( G ( N ) + 2) .
Proof
For any find operation, at most two U.S. pennies are deposited because of the root
and its child. By Theorem 24.3, the vertices going up the path are monotonically
increasing in rank, and thus the rank group never decreases as we go up the path.
Because there are at most G ( N ) rank groups (besides group 0), only G ( N ) other ver-
tices can qualify as a rule 1 deposit for any particular find . Thus, during any find , at
most G ( N ) + 2 U.S. pennies can be placed in the kitty. Thus at most M ( G ( N ) + 2) U.S.
pennies can be deposited under rule 1 for a sequence of M find s.
Theorem 24.6
For any single node in rank group g , the total number of Canadian pennies deposited
is at most F ( g ) .
Proof
If a Canadian penny is deposited in a vertex v under rule 2, v will be moved by path
compression and get a new parent of rank higher than its old parent. As the largest
rank in its group is F ( g ) , we are guaranteed that after F ( g ) coins are deposited, v 's
parent will no longer be in v 's rank group.
The bound in Theorem 24.6 can be improved by using only the size of the
rank group rather than its largest member. However, this modification does
not improve the bound obtained for the union/find algorithm.
Search WWH ::




Custom Search