So the optimization is very natural.

I suspect many a serious programmer would come up with this 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 of parent

pointers you have to traverse.

That is disproportional to the depth of the object at 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 a leaf,

which is furthest away from its corresponding roots.

Now, on the one hand we're using union by rank, so

we know that this depth can't be too bad.

It's going to be at most big 0 of log n.

However, there will be example 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 this endless sequence of find

operations, where every single one is invoked on

a leaf that's a log n number of hops away from from its root.

So for example, in the pink tree that is shown in the upper right of the slide

maybe someone keeps searching for the object,

keeps invoking find from the object one over and over and over again.

And then we're going to be suffering a log number of steps with every single

operation.