CODEWITHSUNDEEP
algorithm
venkysmarty
venkysmarty

Reputation: 11441

Disjoint union-find analysis using rank groups

Disjoint union-find compression analysis.

We will divide the nodes by their ranks. We then divide the ranks into rank groups. On each find, we will deposit some American coins into the general kitty and some Canadian coins into specific vertices. To compute the total number of Canadian coins deposited, we will compute the deposits per node. By adding up all the deposits for each node in rank r, we will get the total deposits per rank r. Then we will add up all the deposits for each rank r in group g and thereby obtain the total deposits for each rank group g. Finally, we add up all the deposits for each rank group g to obtain the total number of Canadian coins deposited in the forest. Adding this to the number of American coins in the kitty gives us the answer.

For each vertex, v, on the path from the vertex representing i to the root, we deposit one penny under one of two accounts:

  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 one unit under this rule. This deposits an American penny into the kitty.

  2. Otherwise deposit a Canadian penny into the vertex.

To get a good estimate for all the Canadian deposits under rule 2, we will add up the deposits by vertices instead of by find instructions. If a coin is deposited into vertex v under rule 2, v will be moved by path compression and get a new parent of higher rank than its old parent. (This is where we are using the fact that path compression is being done.) Thus, a vertex v in rank group g > 0 can be moved at most F(g) - F(g - 1) times before its parent gets pushed out of rank group g, since that is the size of the rank group.* After this happens, all future charges to v will go under rule 1.

My question on above text is

  1. How does author concluded that "a vertex v in rank group g > 0 can be moved at most F(g) - F(g - 1) times"

Thanks!

Upvotes: 0

Views: 305

Answers (1)

mcdowella
mcdowella

Reputation: 19621

In the original, above the section you quoted, it says that "The number of ranks in any rank group, g > 0, is thus F(g) - F(g - 1)"

The author does not conclude exactly what you query, and a node can indeed be moved an arbitrary number of times. What the author does conclude is that, once a node has been moved F(g) - F(g - 1) times by path compression, the parent that it has been moved to cannot be in the same rank group as the node, because every time a node is moved, it gets a parent with higher rank. After this has happened F(g) - F(g - 1) times, its parent cannot be in the same rank group.

The significance of this is that all further path compression moves of this node come under Rule (1), and deposit American pennies, and not Canadian pennies.

Upvotes: 0

Related Questions