In this video we'll provide for the first time concrete evidence that the lazy
union approach to the Union-Find data structure is viable.
Specifically, we'll prove that the worst case running time of both the find and
the union operation is logarithmic in n, the number of objects stored in the data
structure. We are going to do even better later
once, we introduce a second optimization known as path impression.
But an important stepping stone is to understand just is why, just union by
rank, already gets us to a reasonable algorithmic run-time.
So a quick review of the lazy union approach to implementing the union fine
data structure. So, with each note we're going to
maintain a parent pointer. And it's no longer the case that we
insist the parent pointer point directly to the leader of a group.
Rather we just insist that the collection Collection of parent pointers, induces a
collection of directed trees. The root of each tree, that is, the node
which is it's own parent, we're going to define as the leader of that group.
So, given any old object, x, how do you implement find? How do you, figure out
what the leader vertex is? Well, you just traverse parent pointers, up until you
get to the root of that particular group. So for this implementation of the Find
operation, the worst case running time is just going to be the longest path of
parent pointers that you ever have to traverse, to get from an object to some
root. So the way we're going to quantify that
is using these ranks. So this is again, a field that we
maintain for each object. And for now, this will break down later,
but for now before we have path -pression, we're going to maintain the
invariant that the rank of an object x is exactly the largest number of pointers
you have to traverse, from some leaf, to get to x.
As a consequence, the biggest rank of any object is the longest path from any leaf
to any root. And that's going to be an upper bound on
the worst case running time of the find op- Operation.
So let's move on to the union operation. So here, given 2 objects, x and y, you
need to fuse their 2 trees, their 2 groups, so you find the roots of the 2
trees, so you call a find on x, you call a find on y.
That gives you their 2 respective roots, and now you install 1 as a new child.
Of the other. Now we saw in a quiz in the last video,
if you're not careful about which root you install as a child under the other,
you can wind up with these long chains. And be stuck with a linear worse case
time for both find and union. So instead we have this union by rank
optimization. Which says, well, we want to keep our
trees from getting scraggly. And the way we're going to do that is.
When we have a shallow tree and a deep tree we make the shallow tree shall under
the root of the deep one, that prevents the tree from getting even deeper.
Now there is a situation where the two trees have exactly the same depths that
is where the two roots have exactly the same rank, in that case we just proceed
arbitrarily. Then when we merge two trees that both
had a common rank r, its important that in the new tree, the rank is gone up to
r+1. So we need the update, we need the
incremental rank of the new root to reflect that increase.
So that's where we've already been. Where are we going to next? Well the plan
for this video is to show that, with the union by rank, optimization.
The maximum rank of any node, is always, bounded above, by log, base 2 (n).
Where n is the number of objects in the data structure.
Now we just said, the worst case running time of find, is governed, by the maximum
rank. So the logarithmic maximum rank means
logarithm run time of find. that also carries over to the union
operation. Remember union is just 2 finds plus
constant work to rewire 1 pointer, so that's going to give us algorithm time
value on both operations. So let's see why that's true.
So let's begin the analyses with a few simple, but useful properties that follow
immediately from our invariant. From the way that we change the ranks of
objects as we do finds and as we do unions.
So the first simple property is focus on your favorite object.
x. And, watch this objects rank change, over
the course of the data structure, as we do finds and unions.
How can it change? Well, when we do a find we don't change anything, all the
ranks stay the same. When we do a union, all the ranks stay
the same. Well, except there is 1 case in the
union, where the rank, of a single node, gets bumped up by 1, gets increased.
So ranks only go up, over time, for all of the Objects, that's property one.
So the second property is again pretty much trivial, but really, really useful.
So what is the situation in which somebody's rank gets bumped up by 1?
We're going to take the union of two trees that have a common rank.
And then whichever of the two roots that we pick to be the root of the new bigger
tree That's the object whose rank gets bumped up by 1.
So new roots of this fused tree. So in particular, the only type of
objects that can ever get a rank increase is a root.
If you're not a root, your rank will not go up.
Furthermore, once you're not a root in this data structure, you will never be a
root again in the future. There is no process by which, you shed
your parent. Once you have a parent other than
yourself, you will always have exactly that parent.
Putting those two observations together we find that, as soon as an object X.
Becomes a non root but as soon as it has a in parent other than itself it rank is
frozen for the rest of time forever more. The third and final simple property
follows from a formula we mentioned in the last video about computing ranks.
So remember the rank of a node in general is going to be one more than the maximum
rank of any of its children. So if you have a child and there is some
path from a leaf to that child, it takes 5 hops.
The path to you from that child is going to take 6 hops.
As a consequence as you go from the leaf up to the root you will see a strictly
increasing sequence of ranks. The rank of a parent is always strictly
more than the rank of all of those children.
So that's it for the immediate properties.
Let's go to a property which is a little less immediate.
But still this next lemma, which I'm going to call the rank lemma, it's the
best kind of lemma. So on the one hand, it's just not that
hard to prove. I'll give you a full proof in the
following 2 slides. On the other hand, it's really powerful.
It's going to play a crucial role in the analysis were doing right now.
A logarithmic run time bound, with a union by rank optimization, and we'll
keep using it again as a workforce, once we introduce path compression, and prove
better bounds on the operations. So what's the rank limit say? Well it
controls the population size of objects, that have a given (no period) Rank, so we
want it to apply at all intermediate stages of our data structure, so we're
going to consider an arbitrary sequence of unions.
You can throw in some finds as well. I don't care.
Finds don't change the data structure, so they're totally irrelevant, so think
about a sequence of unions, a sequence of mergers.
The claim is, for every non-negative integer, r.
The number of objects that have rank exactly r at this time is at must n.
the total number of objects divided by 2 to the r.
So for example, if our rank is 0. It says that at must n objects have rank
0, so it is a trivial statement because only n objects.
But at any given time the number of objects that have rank 1 is at most n
over 2, the number of objects that have rank 2 is at most no over 4 and so on.
And if you think about it, if we succeed in proving the rank Lemma, we're pretty
much done, showing the efficacy of the union by rank optimization.
So in particular, once you take r, the, in this, key Lemma, to be log base 2 (n),
it says that there's at most 1 object. That has rank log2(n).
And there can't be any objects that have rank strictly larger.
That is, this limit implies that the maximum rank at all times is bounded
above by log2(n). And remember, the maximum rank is the
longest path of pointers, traversals, you ever need to get from a leaf to a root.
And that means the most amount of work we'll ever do in a find, and therefore,
in a union is O (log n) Okay, so I've now teased you with the consequences of the
rank lemma, assuming that it's true, but why is it true? Let's turn to the proof.
I'm going to break the proof down into two claims, claim one and claim two.
We'll see that the two claims easily imply the rank Rank Lemma.
So claim 1 asks you to consider 2 objects, X and Y, that have exactly the
same rank R. And the claim asserts that the sub-trees
of these 2 objects have to be disjoint. They have no objects in common.
And here by the sub-tree of an object, I just mean the other objects that can
reach this one by following a sequence. Of, parent pointers.
So that is the subtree at x, is the objects from which you can reach x.
The subtree at y is the objects from which you can reach y.
The second claim, is that, if you look at any object that has rank r, and you look
at it's subtree, that is, if you look at the number of objects that can reach,
this object x by following pointers, there have to be a lot of them.
There have to be at least 2 raised to that objects rank Are, objects in it's
subtree? Notice that, if we prove claim 1 and claim 2, then the Rank Lemma, follows
easily. Why? Well, fix a value for, r.
2, 10, I don't care what. Look at all the nodes that have this rank
R. By claim 2, each of them has at least 2
to the R objects that could reach them. And by claim 1, these have to be disjoint
sets of objects. Well, there's only N objects to go
around, and if each of these disjoint sets has at least 2 to the R of them,
there are going to be at most N over 2 to the R such groups.
That is at most N over 2 to the R nodes, objects with this rank R.
So we've reduced the proof of the rank Lemma to proving claims 1 and 2, I will
do them in turn. So for claim 1 let me go via the contra
positive, that is, I will assume that the conclusion is false, and I will show that
the hypothesis must then also be false. So, lets assume that we have 2 no,
objects x and y, and their subtrees are not, disjoint.
That is, there exists an object z, from which You can reach X and from the same
object Z, you can also reach Y by a sequence parent pointers.
Well now let's use the fact that we're dealing with the directed tree, right, so
if you start with an object Z. There's only a unique parent point, or 2,
follow each time. So that is, all of the objects reachable
from z, they form a directed path, leading up to the root of z's group.
So the only way for both x and y to be reachable from z, they have to both be on
this path. If they're both on this path, then 1 has
to be an ancestor of the other. So now we're going to use the third of
our simple properties that we observed. That is, on every path to the root, ranks
strictly go up, each time. So, whichever of x or y is an ancestor of
the other, that has strictly higher rank. Therefore x and y do not have the same
rank. That completes the proof, of claim 1.
So lets move on to claim 2. Remember, claim 2 is search that, an
object of rank r, necessarily has 2 ^ r objects, or more, in its subtree.
That's how many objects can actually reach this object x, by following Parent
pointers. So for this proof we're going to proceed
by induction on the number of operations, and again remember fine operations have
no effect on the data structure, so we can ignore them.
So it's just by induction on the number of union operations that happen.
So for the base case, when, before we've done any unions whatsoever, we're doing
just fine. Every object has a rank of 0 and the
sub-tree size of every object is equal to 1.
That object itself, also known as 2 to the 0.
Zero. Now for the inductive step, there's an
easy case and a hard case. The easy case is where nobody's rank
changes, where we do a union, and everybody's rank stays exactly the same.
In this case, we're golden. Why? Well, when you do a union, sub-tree
sizes only go up. There's only more.
Pointers so there's only more objects that can reach any given other objects.
So sub-tree sizes go up, ranks stay the same.
If we had this inequality of sub-tree size as being at least 2 ^ r before, we
have it equally well now. Now.
So the interesting case is when somebody's ranked actually changes.
How can that happen? Well it happens in only one particular way that we
understand well. Looking at a union operation between
objects X and Y. Suppose the roots of these objects are S1
and S2 respectively. It's only when these.
Two roots have the same rank, let's call that common rank R, that somebodies rank
gets changed. In particular, we're going to break ties
as we did in the previous video. S2 will be the root of the fused tree, S1
will become a child of it. And, in that case, S2s rank gets bumped
up by 1. It goes from R To r + 1.
Now notice, in this case, we do have something to prove.
What are we trying to establish? We're trying to establish that every subtree
size is big, as a function of the rank. So, s2's rank has gone up, and therefore
the lowerbound, the bar that we have to meet, for the subtree size, has also Gone
up, it's doubled. So in this case we actually have to
scrutinize s2's new sub-tree. So what is its new sub-tree? Well, it's
really just composed from its old sub-tree, and it inherits s1 and all of
its sub-trees. Well, in that case, we know that s2's new
subtree size, the nubmer of no objects that can reach it, is just, it's old
subtree size, plus the old subtree size, of s1.
But then w're in good shape because we have the inductive hypothesis to rescue
us. So remember, before this union, by the
inductive hypothesis, for every object with a given rank, say r, it had at least
2^r objects in its sub tree. So S1, and S2, both had rank r before
this. Unions, before this union, both of their
subtree were at least two to the r. So as two subtree sizes bounded below by
two to the r plus two to the r, a quantity also known as two raised to the
r plus one. Quite conveniently, r plus one is S two's
new rank, so S two's new bigger rank, its subtree size is still meeting the lower
bound, meeting the target of two raised to, New rank, 2 ^ r + 1.
So that completes the inductive step, therefore it completes the proof of claim
2, that objects of rank r have subtree sizes at least 2 ^ r.
Therefore completes the proof of the rank Lemma, that for every rank r, there's at
most n / 2 ^ r nodes of rank r. And remember the rank Lemma, implies that
the maximum rank, at all times, is bounded by log base 2 (n), as long as
you're using union by rank. And that implies, that with this first
optimization, the worst case running time of union, and find, are both O (log n),
where n is the number of objects, in the data structure.