So I don't blame you if you're feeling a little bit restless.
You've now watched three videos about this alternative approach to the
Union-Find Data Structure based on Lazy Unions.
And, frankly, we don't have many tangible things to show for it.
We already had a perfectly fine implementation of this data structure
based on eager unions. That gave us constant time finds.
And yeah, union could be linear in the worst case.
But it was logarithmic on average of. For a sequence of unions.
And so now we have this other implementation.
Both of our operations are requiring logarithmic time.
It's true, it's a worst case bound, and it's true union by rank is pretty cool,
but still the bottom line up to this point is not that compelling.
But I've still got another trick up my sleeve.
Now just watch what happens once we employ a second optimization known as
path compression. So the optimization is very natural.
I suspect many as serious programmers would come up with it on their own if
they were tasked with implementing union find with union.
By rank. So to motivate this optimization let's
think about what would be our worst nightmare as someone maintaining such a
data structure and hoping for good performance.
Well remember the running time of a find is proportional to the number or parent
pointers you have to traverse that is as proportional to the depth of the object
that which. it's invoked.
So what's the worst case find look like? Well it's going to be the leaf, and
moreover it's going to be the leaf which is furthest away from its corresponding
root. Now, on the one hand we're using union by
rank so we know this depth can't be too bad.
We know it's going to be at most big o of log n.
However there will be examples, there will in general be leafs that are Theta
of log n hops away from their root. And for all we know we're just going to
get those endless sequence of Find operations where every single one is
invoked on a leaf that's a log n number of hops away from its root.
So for example in the pink tree that I've shown in the upper right of the slide You
know, maybe someone just keeps searching for the object, keeps invoking find from
the object 1 over and over and over again.
And then we're going to be suffering a log number of steps every single
operation. But if you think about it, it's totally
pointless to keep redoing the work of previous finds, to keep re-traversing the
same paretn pointers over and over again. So, for example, in the pink tree that
I've shown in the upper right, imagine that find is invoked from object.
The one. So then we traverse the 3 parent corners,
we discover the ancestors 4 and 6, before terminating at 7 and we discover that 7
is the leader, or the root corresponding to the object 1.
Now remember, we do not care that 4 and 6 are ancestors of 1.
That is uninteresting. We only visited them, to discover we
actually cared about that 7 is the leader, the root, corresponding to 1.
Well, but let's just, cache that information, now that we've computed it.
So this is now, basically reconstructing the eager, union-find implementation.
Let's just rewire 1's parent pointer to point straight to 7.
We don't need to recompute 4 and 6 and some later find them.
In operation,and more generally after we'll worth find from object 1 we may as
well rewire 4's parent pointer as well to point directly to it's leader 7.
So that then, is, path compression. When find is invoked from some node x,
and you traverse parent pointers from x, up to its root, call it r.
For every, object that you visit, along this path, from x to r, you rewire the
parent pointer to Point, directly to r. So r doesn't have its parent pointer
changed, it still points to itself. The penultimate object on this path
doesn't have it's parent pointer changed, it already was pointing to the root r.
But anything below the root, and it's immediate descendants, on this path from
x, will have its parent point updated, and it will be updated to point directly,
to r. Now we couldn't get away with this, if
the tree had to be binary But it doesn't have to be binary.
We couldn't get away with this, if we had to satisfy some other constraint, like a
search tree property. But we don't.
So nothing's stopping us from just casting this information, about whose
everyone's leaders are. Because that's really, the only
information we're responsible from exporting, from this union find data
structure. So pictorially if you like thinking about
the trees in effect what past compression does is make the tree shallower and more
bushy. So in our example in the upper right, it
rips out 1 and 4 and makes them immediate decendent of the root 7 Prefer to think
in terms of the array representation, and remember, in the array representation,
the array index for i, is recording the parent of the object i.
So, in our pink tree, 5, 6 and 7, all point to 7.
They all ave parent 7. Where as 2 and 3 have parent 5.
4 has the parent 6, and 1 has the parent 4.
And after applying path in, compression, following a find invoked at the object 1,
1 and 4 are redirected to have parent 7. So what are the pros and cons of the path
compression optimization. Well the con side is quite minor.
Really, we're just doing a little multitasking on find, and that introduces
a small constant factor overhead. You're already doing work proportional to
the number of hops. On the path from x towards root and we're
still just doing constant work for each node on that path.
We're doing an extra constant work preach node after the fact to rewire the parent
pointer out of the point to the root. The Pro should be obvious.
This is going to speed up all subsequent find operations, you're really making
sure you don't redo redundant work, you don't traverse parent pointers over and
over and over again. So what's clear is that you know finds
will speed up, what's really not clear is.
Whether they'll speed up by a lot. So is this only going to have an affect
the performance of the Find operation by say a factor of 2? Or, will we get
something fundamentally better than the logarithmic performance we were stuck
with without path compression? So, let me spend a slide on the subtle point of how
ranks interact with the path compression. In optimization.
So the plan is, we're going to manipulate, rank fields, with path
compression, in exactly the same way, as we did, when we didn't have path
compression. So how did we manipulate them previously?
Well, at the birth of the Union Find data structure, everybody has rank 0.
Ranks never change except possibly when you do a union.
When you do a union, you look at the roots of the two objects whose groups you
have to union, you look at their ranks. If one of them has strictly bigger rank,
that becomes the root of your new merged tree.
The root with the smaller rank is installed as a child Underneath.
If you union two roots that have exactly the same rank, you pick arbitrarily which
of them is the new root, and you bump up it's rank, by one.
That is how we manipulated ranks before. That is exactly how we're going to
manipulate them now. So in particular, when we apply path
compression, when we rewire parent pointers following a find, we do not
touch Anybody's ranks, we leave them all exactly the same.
So again, ranks only change in one specific case, in a very specific way.
Namely, during the union, when we merge two trees, that have exactly the same
rank and when we do that kind of union, that kind of merge.
Which ever of the old roots winds up being the new root, we bump up its rank
by 1, that is the only modification we ever make to any ranks.
Now, it might bother you, that we don't recompute the ranks, so when we apply
path compression in a way I sort of hope it does bother you.
Because by now recomputing ranks by just manipulating them exactly as before were
actually loosing the semantics of what ranks meant in the previous video.
So the key envering we have that ranks exactly represented.
Worse case, search time to that object is now lost.
The easiest way to see what I'm talking about is probably through an example, so
let me redraw the same tree we had on the previous slide, both before and after we
apply path compression following a find invoked at the object 1.
So what I've done here is in the top tree, before the path compression's been
applied I've labeled ranks just as they were in the previous video.
So for each node in the top tree, its rank is equal to the longest path from a
leaf to that node. Then I applied path compression from the
object one, resulting in the Bushier more shallow tree on the bottom and as I said,
I did not touch anybody's rank when I applied this past compression.
I didn't do any recomputation. I know see we've now lost the semantic
for the rank. Just to give a simple example, they're
now leaves. That don't have rank 0 they have rank
strictly bigger than 0. So what we can say is that for every node
the rank is a upper band not necessarily exactly the same as but at least as big
as the longest path from a leaf to that node.
But because of the shortcuts that we've installed we no longer have the equality
that we had before. There is good news however, we can
definitely salvage a lot of the technology that we developed in the last
video, for the union by rank analysis, and apply it fruitfully here to the case
with path compression. In particular, any statement that we
made, last video, that talks only about the ranks, of objects, and not about
their parent pointers per se, that will be as true with path compression As
without. Why? Well, think about making two copies
of a union-find data structure. Exactly the same set of objects, and now
run them in parallel, on exactly the same sequence of union and find operations.
So, by definition, we manipulate the ranks of objects, in exactly the same
way. In the 2 copies it doesn't matter if this
is path impression or not. So all moment in time every object will
have exactly the same ranks in one copy as it does in another copy.
Path impression or no, doesn't matter, exactly the same rank.
What's going to be different in the true copy is the parent pointer.
They're in some sense going to be further along, they're going to point further up
into the tree and then copied with path impression.
But no matter, any statements that's purely about ranks is going to be equally
well true. With or without path compression.
So in particular, remember the Rank Lemma that we proved in the last video.
That says there's the most n/r^r objects of rank r.
That was true without path compression. It's going to be true with path
compression. And we're going to use it in the fourth
The coming analysis. Another fact, which is still true with
path compression, in fact in some sense, it's only more true with path
compression, is that whenever you traverse a parent pointer, you will get
to a node with strictly, larger, rank. Remember in the last video we said, as
you go up toward the root, you're going to see a strictly increasing
[UNKNOWN] sequence of ranks. Here each pointer with path impression
represents a sequence without path impression.
So certainly, you will still only be increasing in ranks each time you.
A pointer. Lets now quantify the benefit of path
compression, by proving new performance gaurantees on the operatioins in this
union find data structure. In fact, the running time bounds are
going to blow away the logarithmic bound that we had when we were only doing union
by rank, without Path compression. We're going to do the analysis in two
steps. And it's going to be historically
accurate, in the sense that I'm first going to show you a theorem by Hopcroft
and Ullman, which gives an excellent, but not quite optimal bound, on the
performance of this union-find data structure.
And then, we're going to build on the Hopcroft-Ullman ideas, to prove Tarjan's
even better bound on the performance of this data structure.
So here is the performance guarantee that Hopcroft and Ullman proved back in 1973,
about 40 years ago. They said consider a union find data
structure implemented as we've been discussing.
Lazy unions, union by rank, path the pressure.
Consider and arbitrary sequence of M find and union operations, and suppose the
data structure contains N objects. Then the total work that the data
structure does. To process this entire sequence of m
operations, is m, times, log *, of n. What is, log * of n, you ask? Well, it's
the iterated logarithm operator. So, by analogy, remember when we first
demystified the logarithm. That way back at the beginning of part 1
we noticed that log base 2 of a number is just well you type that number into your
calculator, you count the number of times you / by 2 until the result drops below
1. So log * you type the number n into your
calculator you count the number of times you need to hit log before the result
drops below. Work one.
So it totally burgles the mind, just have slowly this log * function grows.
In fact that may give you a quick quiz just to make sure that you appreciate the
glacial growth of the log * function. So the correct answer is B, it is 5 and
you should probably spend a couple of seconds just reflecting on.
How absurd this is, right? So, you take this ridiculous number, 2 to the 65,000,
remember the number of atoms, in the known universe estimated is way smaller
than this, it's just 10 to the 80. So you dig this ridiculous number, you
apply the log * function, you get back, 5.
Why do you get back 5? Well, take logarithm once, what do you get back?
65,536, Also know as 2 to the 16. So, you take log again, you get back 16.
Also known as 2^4. You take the value again, you get back 4,
also known as 2^2. You take the value again, you get back at
2, and then one more time it gets you down to 1.
So, you think of log * as the inverse of tower function with the tower function
takes, think of it as a positive integer, t.
And it just raises to 2, to the 2, to the 2, to the 2, to the 2 t times.
And this in particular shows that log*, despite it's glacial growth, is not
bounded by a constant. This function is not L of 1.
For any constant c you can think of, I can, in principle, exhibit a large enough
n so that log* of my n is bigger than your c.
Anyway, I can just set c to be 2 to the 2 to the 2 to the so on c times.
log * of that will be at least c. So that's the HopCroft Ullman performance
guarantee, that, on average, over a sequence of N union and fine operations,
you spend only this ridiculously small log *.
In amount per operation. We're going to prove it in the next
video.