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.