For any integer j ≥ 1, we have A₁(j) = 2 j + 1.

Proof We first use induction on i to show that . For the base case, we have . For the inductive step, assume that . Then . Finally, we note that .

For any integer j ≥ 1, we have A₂(j) = 2^j+1(j + 1) - 1.

Proof We first use induction on i to show that . For the base case, we have . For the inductive step, assume that . Then . Finally, we note that .

For all nodes x, we have rank[x] ≤ rank[p[x]], with strict inequality if x ≠ p[x]. The value of rank[x] is initially 0 and increases through time until x ≠ p[x]; from then on, rank[x] does not change. The value of rank[p[x]] monotonically increases over time.

Proof The proof is a straightforward induction on the number of operations, using the implementations of MAKE-SET, UNION, and FIND-SET that appear in Section 21.3. We leave it as Exercise 21.4-1.

As we follow the path from any node toward a root, the node ranks strictly increase.

Every node has rank at most n - 1.

Proof Each node's rank starts at 0, and it increases only upon LINK operations. Because there are at most n - 1 UNION operations, there are also at most n - 1 LINK operations. Because each LINK operation either leaves all ranks alone or increases some node's rank by 1, all ranks are at most n - 1.

Suppose we convert a sequence S' of m' MAKE-SET, UNION, and FIND-SET operations into a sequence S of m MAKE-SET, LINK, and FIND-SET operations by turning each UNION into two FIND-SET operations followed by a LINK. Then, if sequence S runs in O(m α(n)) time, sequence S' runs in O(m' α(n)) time.

Proof Since each UNION operation in sequence S' is converted into three operations in S, we have m' ≤ m ≤ 3m'. Since m = O(m'), an O(m α(n)) time bound for the converted sequence S implies an O(m' α(n)) time bound for the original sequence S'.

For every node x, and for all operation counts q, we have

0 ≤ φ_q(x) ≤ α(n) · rank[x].

Proof If x is a root or rank[x] = 0, then φ_q(x) = α(n) · rank[x] by definition. Now suppose that x is not a root and that rank[x] ≥ 1. We obtain a lower bound on φ_q(x) by maximizing level(x) and iter(x). By the bound (21.1), level(x) ≤ α(n) - 1, and by the bound (21.2), iter(x) ≤ rank[x]. Thus,

Similarly, we obtain an upper bound on φ_q(x) by minimizing level(x) and iter(x). By the bound (21.1), level(x) ≥ 0, and by the bound (21.2), iter(x) ≥ 1. Thus,

Let x be a node that is not a root, and suppose that the qth operation is either a LINK or FIND-SET. Then after the qth operation, φ_q(x) ≤ φ_q-1(x). Moreover, if rank[x] ≥ 1 and either level(x) or iter(x) changes due to the qth operation, then φ_q(x) ≤ φ_q-1(x) - 1. That is, x's potential cannot increase, and if it has positive rank and either level(x) or iter(x) changes, then x's potential drops by at least 1.

Proof Because x is not a root, the qth operation does not change rank[x], and because n does not change after the initial n MAKE-SET operations, α(n) remains unchanged as well. Hence, these components of the formula for x's potential remain the same after the qth operation. If rank[x] = 0, then φ_q(x) = φ_q-1(x) = 0. Now assume that rank[x] ≥ 1.

Recall that level(x) monotonically increases over time. If the qth operation leaves level(x) unchanged, then iter(x) either increases or remains unchanged. If both level(x) and iter(x) are unchanged, then φ_q(x) = φ_q-1(x). If level(x) is unchanged and iter(x) increases, then it increases by at least 1, and so φ_q(x) ≤ φ_q-1(x) - 1.

Finally, if the qth operation increases level(x), it increases by at least 1, so that the value of the term (α(n) - level(x)) · rank[x] drops by at least rank[x]. Because level(x) increased, the value of iter(x) might drop, but according to the bound (21.2), the drop is by at most rank[x] - 1. Thus, the increase in potential due to the change in iter(x) is less than the decrease in potential due to the change in level(x), and we conclude that φ_q(x) ≤ φ_q-1(x) - 1.

The amortized cost of each MAKE-SET operation is O(1).

Proof Suppose that the qth operation is MAKE-SET(x). This operation creates node x with rank 0, so that φ_q(x) = 0. No other ranks or potentials change, and so Φ_q = Φ_q-1. Noting that the actual cost of the MAKE-SET operation is O(1) completes the proof.

The amortized cost of each LINK operation is O(α(n)).

Proof Suppose that the qth operation is LINK(x, y). The actual cost of the LINK operation is O(1). Without loss of generality, suppose that the LINK makes y the parent of x.

To determine the change in potential due to the LINK, we note that the only nodes whose potentials may change are x, y, and the children of y just prior to the operation. We shall show that the only node whose potential can increase due to the LINK is y, and that its increase is at most α(n):

• By Lemma 21.9, any node that is y's child just before the LINK cannot have its potential increase due to the LINK.

• From the definition of φ_q(x), we see that, since x was a root just before the qth operation, φ_q-1(x) = α(n) · rank[x]. If rank[x] = 0, then φ_q(x) = φ_q-1(x) = 0. Otherwise,

  φq(x)	=	(α(n) - level(x)) · rank[x] - iter(x)
  	<	α(n) · rank[x] (by inequalities (21.1) and (21.2)).

  Because this last quantity is φ_q-1(x), we see that x's potential decreases.

• Because y is a root prior to the LINK, φ_q-1(y) = α(n) · rank[y]. The LINK operation leaves y as a root, and it either leaves y's rank alone or it increases y's rank by 1. Therefore, either φ_q(y) = φ_q-1(y) or φ_q(y) = φ_q-1(y) + α(n).

The increase in potential due to the LINK operation, therefore, is at most α(n). The amortized cost of the LINK operation is O(1) + α(n) = O(α(n)).

The amortized cost of each FIND-SET operation is O(α(n)).

Proof Suppose that the qth operation is a FIND-SET and that the find path contains s nodes. The actual cost of the FIND-SET operation is O(s). We shall show that no node's potential increases due to the FIND-SET and that at least max(0, s - (α(n) + 2)) nodes on the find path have their potential decrease by at least 1.

To see that no node's potential increases, we first appeal to Lemma 21.9 for all nodes other than the root. If x is the root, then its potential is α(n) · rank[x], which does not change.

Now we show that at least max(0, s - (α(n) + 2)) nodes have their potential decrease by at least 1. Let x be a node on the find path such that rank[x] > 0 and x is followed somewhere on the find path by another node y that is not a root, where level(y) = level(x) just before the FIND-SET operation. (Node y need not immediately follow x on the find path.) All but at most α(n) + 2 nodes on the find path satisfy these constraints on x. Those that do not satisfy them are the first node on the find path (if it has rank 0), the last node on the path (i.e., the root), and the last node w on the path for which level(w) = k, for each k = 0, 1, 2, ..., α(n) - 1.

Let us fix such a node x, and we shall show that x's potential decreases by at least 1. Let k = level(x) = level(y). Just prior to the path compression caused by the FIND-SET, we have

Putting these inequalities together and letting i be the value of iter(x) before path compression, we have

Because path compression will make x and y have the same parent, we know that after path compression, rank[p[x]] = rank[p[y]] and that the path compression does not decrease rank[p[y]]. Since rank[x] does not change, after path compression we have that . Thus, path compression will cause either iter(x) to increase (to at least i + 1) or level(x) to increase (which occurs if iter(x) increases to at least rank[x] + 1). In either case, by Lemma 21.9, we have φ_q(x) ≤ φ_q-1(x) - 1. Hence, x's potential decreases by at least 1.

The amortized cost of the FIND-SET operation is the actual cost plus the change in potential. The actual cost is O(s), and we have shown that the total potential decreases by at least max(0, s - (α(n) + 2)). The amortized cost, therefore, is at most O(s) - (s - (α(n) + 2)) = O(s) - s + O(α(n)) = O(α(n)), since we can scale up the units of potential to dominate the constant hidden in O(s).

A sequence of m MAKE-SET, UNION, and FIND-SET operations, n of which are MAKE-SET operations, can be performed on a disjoint-set forest with union by rank and path compression in worst-case time O(m α(n)).

Proof Immediate from Lemmas 21.7, 21.10, 21.11, and 21.12.

Prove Lemma 21.4.

Prove that every node has rank at most ⌊lg n⌋.

In light of Exercise 21.4-2, how many bits are necessary to store rank[x] for each node x?

Using Exercise 21.4-2, give a simple proof that operations on a disjoint-set forest with union by rank but without path compression run in O(m lg n) time.

Professor Dante reasons that because node ranks increase strictly along a path to the root, node levels must monotonically increase along the path. In other words, if rank(x) > 0 and p[x] is not a root, then level(x) ≤ level(p[x]). Is the professor correct?

Consider the function α'(n) = min {k : A_k (1) ≥ lg(n + 1)}. Show that α'(n) ≤ 3 for all practical values of n and, using Exercise 21.4-2, show how to modify the potential-function argument to prove that a sequence of m MAKE-SET, UNION, and FIND-SET operations, n of which are MAKE-SET operations, can be performed on a disjoint-set forest with union by rank and path compression in worst-case time O(m α'(n)).

The off-line minimum problem asks us to maintain a dynamic set T of elements from the domain {1, 2, ..., n} under the operations INSERT and EXTRACT-MIN. We are given a sequence S of n INSERT and m EXTRACT-MIN calls, where each key in {1, 2, ..., n} is inserted exactly once. We wish to determine which key is returned by each EXTRACT-MIN call. Specifically, we wish to fill in an array extracted[1 ‥ m], where for i = 1, 2, ..., m, extracted[i] is the key returned by the ith EXTRACT-MIN call. The problem is "off-line" in the sense that we are allowed to process the entire sequence S before determining any of the returned keys.

1. In the following instance of the off-line minimum problem, each INSERT is represented by a number and each EXTRACT-MIN is represented by the letter E:

   4, 8, E, 3, E, 9, 2, 6, E, E, E, 1, 7, E, 5.

   Fill in the correct values in the extracted array.

To develop an algorithm for this problem, we break the sequence S into homogeneous subsequences. That is, we represent S by

I₁, E, I₂, E, I₃, ..., I_m, E, I_m+1,

where each E represents a single EXTRACT-MIN call and each I_j represents a (possibly empty) sequence of INSERT calls. For each subsequence I_j, we initially place the keys inserted by these operations into a set K_j , which is empty if I_j is empty. We then do the following.

OFF-LINE-MINIMUM(m, n)
1  for i ← 1 to n
2       do determine j such that i ∈ Kj
3          if j ≠ m + 1
4             then extracted[j] ← i
5                  let l be the smallest value greater than j
                                   for which set Kl exists
6                  Kl ← Kj ∪ Kl, destroying Kj
7  return extracted

2. Argue that the array extracted returned by OFF-LINE-MINIMUM is correct.

3. Describe how to implement OFF-LINE-MINIMUM efficiently with a disjoint-set data structure. Give a tight bound on the worst-case running time of your implementation.

In the depth-determination problem, we maintain a forest of rooted trees under three operations:

• MAKE-TREE(v) creates a tree whose only node is v.

• FIND-DEPTH(v) returns the depth of node v within its tree.

• GRAFT(r, v) makes node r, which is assumed to be the root of a tree, become the child of node v, which is assumed to be in a different tree than r but may or may not itself be a root.

  1. Suppose that we use a tree representation similar to a disjoint-set forest: p[v] is the parent of node v, except that p[v] = v if v is a root. If we implement GRAFT(r, v) by setting p[r] ← v and FIND-DEPTH(v) by following the find path up to the root, returning a count of all nodes other than v encountered, show that the worst-case running time of a sequence of m MAKE-TREE, FIND-DEPTH, and GRAFT operations is Θ(m²).

By using the union-by-rank and path-compression heuristics, we can reduce the worst-case running time. We use the disjoint-set forest , where each set S_i (which is itself a tree) corresponds to a tree T_i in the forest . The tree structure within a set S_i, however, does not necessarily correspond to that of T_i. In fact, the implementation of S_i does not record the exact parent-child relationships but nevertheless allows us to determine any node's depth in T_i.

The key idea is to maintain in each node v a "pseudodistance" d[v], which is defined so that the sum of the pseudodistances along the path from v to the root of its set S_i equals the depth of v in T_i. That is, if the path from v to its root in S_i is v₀, v₁, ..., v_k, where v₀ = v and v_k is S_i's root, then the depth of v in T_i is .

2. Give an implementation of MAKE-TREE.

3. Show how to modify FIND-SET to implement FIND-DEPTH. Your implementation should perform path compression, and its running time should be linear in the length of the find path. Make sure that your implementation updates pseudodistances correctly.

4. Show how to implement GRAFT(r, v), which combines the sets containing r and v, by modifying the UNION and LINK procedures. Make sure that your implementation updates pseudodistances correctly. Note that the root of a set S_i is not necessarily the root of the corresponding tree T_i.

5. Give a tight bound on the worst-case running time of a sequence of m MAKE-TREE, FIND-DEPTH, and GRAFT operations, n of which are MAKE-TREE operations.

The least common ancestor of two nodes u and v in a rooted tree T is the node w that is an ancestor of both u and v and that has the greatest depth in T. In the off-line least-common-ancestors problem, we are given a rooted tree T and an arbitrary set P = {{u, v}} of unordered pairs of nodes in T, and we wish to determine the least common ancestor of each pair in P.

To solve the off-line least-common-ancestors problem, the following procedure performs a tree walk of T with the initial call LCA(root[T]). Each node is assumed to be colored WHITE prior to the walk.

LCA(u)
 1  MAKE-SET(u)
 2  ancestor[FIND-SET(u)] ← u
 3  for each child v of u in T
 4       do LCA(v)
 5          UNION(u, v)
 6          ancestor[FIND-SET(u)] ← u
 7  color[u] ← BLACK
 8  for each node v such that {u, v} ∈ P
 9       do if color[v] = BLACK
10            then print "The least common ancestor of"
                          u "and" v "is" ancestor[FIND-SET(v)]

1. Argue that line 10 is executed exactly once for each pair {u, v} ∈ P.

2. Argue that at the time of the call LCA(u), the number of sets in the disjoint-set data structure is equal to the depth of u in T.

3. Prove that LCA correctly prints the least common ancestor of u and v for each pair {u, v} ∈ P.

4. Analyze the running time of LCA, assuming that we use the implementation of the disjoint-set data structure in Section 21.3.