-------------------------------------------------------------------------
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.
--------------------------------------------------------------