------------------------------------------------------------------------- Notes on Union Find Ackermann Analysis based on a lecture by Danny Sleator, based on a talk by Raimund Seidel, and analysis by Seidel and Sharir scribe: Anupam Gupta ------------------------------------------------------------------------- First, think of the basic operations as being 1. union(u,v): unions the trees rooted at u and v together. 2. rootof(x): returns y, the root of x's tree at that time 3. path-compress(x,y): compresses the path between x and some ancestor y. The usual way we implement find(x) is sub find(x) { y <- rootof(x); path-compress(x,y); } All we need to do is analyse the work done. So we ignore the rootof() operations done during the finds for the analysis' sake. Since the cost of the rootof() is the same as the cost of the following path-compress (PC) operation, we assume we want to bound the cost of the unions and PC operations alone. The actual cost is higher only by a factor of 2. Note that the cost of a union is constant. Moreover, we define cost(PC(x,y)) as the number of nodes whose parents were reassigned during this PC operation. Note that if the PC operation was on a single edge, we would count 0 cost, whereas there might be unit cost. But the loss in this is only O(# of PC operations), and we can add back this term at the end, increasing the cost by at most O(m). -------------------------------------------------------------- So really, how do we bound the cost of these PC ops???? -------------------------------------------------------------- Step I ====== Since these unions make things complicated, let us go from having World A: m unions and PC's arbitrarily interspersed to World B: all the unions first and then the PC's follow. For this reordering to make sense, we should make sure that 1. for any PC(x,y) operation that made sense in world A, it also makes sense in world B. I.e., y is still x's ancestor. 2. the cost of each PC(x,y) operation in world B has the same cost as the cost in world A. Proofs: deferred. QED. -------------------------------------------------------------- Step II: ======= Now that the unions all come first, let us fix the forest F we get after all the unions are done. (The work done until now for the unions is O(1) per operation.) Now we have to analyze the cost incurred for the sequence \$C\$ of \$m\$ PC operations to come. Since the cost of the PC operations on the forest is the sum of the PC operations on each tree, let us focus on a single tree T, with nodes X. Mark some of X as the top nodes Xt and the rest as the bottom nodes Xb. This should be done in such a way that the parent of a top node is another top node. ("Xt is upwards-closed" for all us math-terminology fans.) Either of these sets may be empty. Now this breaks the tree into another forest: the nodes in Xt induce a tree Tt, and the nodes in Xb induce a forest Fb. We create a new node N, and attach the roots of all the trees in the forest Fb to N to get the tree Tb. Example here. -------------------------------------------------------------- Why do we do this? So that we can now write a divide-and-conquer recurrence that will, at the end, give us the Ackermann-style bound we're looking for. -------------------------------------------------------------- Some proofs now. First make sure that the properties of Xt and Xb do not change as we apply the PC operations to T. Lemma: If Xt is upwards-closed in T, and if T' is the tree obtained by performing a PC operation on T, then Xt is upwards closed in T'. Proof. deferred QED. Now consider each of the PC operations on T and see how T evolves as we perform these operations. Just before we apply PC(x,y) on the current version of tree T we write down (at most two) operations that work on the trees Tt and Tb. a) if x,y in Xt, then generate PC(x,y), a valid op for Tt. b) if x,y in Xb, then generate PC(x,y), a valid op for Tb. c) if x in Xb, y in Xt, then consider the xy path in the current tree T. let y' be the first node in Xt on the path (maybe the same as y). Generate PC(y', y) on Tt. Generate PC*(x, N) on Tb. Charge one token. Nb. PC* works the same as PC, but we consider it separately it for charging purposes. These were the "root finds" that we were doing in lecture, but we've stated it this way in the notes to make things explicit. ------------------------------------------------------------ Why are we doing this? We want to claim that the work done by the new ops on Tt and Tb is at least the work done by the old ops on T. So if we could bound the latter we'd be done. This will be almost true, with a couple of fudge-factors. ------------------------------------------------------------ Let C be the set of PC ops performed on C Ct be the PC ops generated for Tt, Cb be PC ops generated for Tb C* be the PC* ops genearated (all for Tb). Lemma: the number of PC operations performed on T is the same as the number of PC operations performed on Tt and Tb together. I.e., |C| <= |Ct| + |Cb| Proof: immediate. QED. Lemma: the number of tokens used is at most |Ct| Proof: every time we generate a token, we generate an op in Ct. QED. Lemma: the number of edges on paths given to the PC* ops over the run of the algorithm is at most |Xb| + number of tokens <= |Xb| + |Ct| Proof: Note that whenever we do PC*(x,.), the second argument is N, and this makes a bunch of nodes in Xb now point to N. In T, all these nodes now have a parent in Xt. For each node in Xb that is made to point to N for the first time, charge this operation to the node itself. However, there can be (at most) one node on this path in Tb that was already pointing to N, this must be the node that (in T) had a parent in Xt. This one edge is charged to the token. QED. Lemma: cost_T(C) <= cost_Tt(Ct) + cost_Tb(Cb) + |Ct| + |Xb| Proof: the number of parent reassignments on T with a PC op is the number of edges on the path minus 1. If the PC op corresponds to Cases (a) or (b) above, the cost incurred is the same on both sides. The interesting case is (c): here the two paths in Tt and Tb have total length the same as the the original path in T. The PC op in Tt charges the length of the Tt-path minus 1. Hence, if the right side increases by at least the length of the Tb path, we'd be done. But by the lemma above, the total lengths of the Tb paths given to PC* ops is at most |Xb| + |Ct|, which completes the claim. QED. -------------------------------------------------------------- So we've got what we wanted: the cost of a sequence of PC ops on T can be bounded by the PC ops on Tt and Tb, plus the fudge factors of |Xb| and |Ct|. What good will this do us? A lot! We will choose these Xt and Xb sets carefully to get the result we want. -------------------------------------------------------------- But First, An Easy Result Let's show that even if we do not do union-by-rank, path compression gives us amortized O(log n) performance. Claim: For any sequence C of m PC operations on n = |X| items. cost(C) <= (m + n/2) log_2 n. Proof: By induction on n. For n = 1, cost(C) = 0. Let Xt and Xb be any valid partition of X such that Xt is upwards closed, and |Xt| = |Xb| = n/2. Now recall that cost(C) <= cost(Ct) + cost(Cb) + |Xb| + |Ct| (*) by IH: cost(Ct) <= (|Ct| + |Xt|/2) log |Xt| cost(Cb) <= (|Cb| + |Xb|/2) log |Xb| |Xb| = n/2 |Ct| <= |C| = m Hence the RHS of (*) is at most (|Ct| + |Cb| + |Xt|/2 + |Xb|/2) (log |X| - 1) + n/2 + m <= (m + n/2) log |X| QED. --------------------------------------------------------------