Let's talk about path compression. Now, this operation is really what makes the union find one of the most remarkable data structures, because it's how the union find gets to boast in its efficiency. So let's dive right in. But before we get started, it's critical that you watch the last video so that you understand how the find in the Union operation work. Otherwise, you want to understand what's going on and what's up with path compression and how we going to get that really nice, amortized constant time. Alright, suppose we have this hypothetical union find.

I say hypothetical, because with path compression, I'm almost certain it's impossible to achieve a data structure or a structure that looks like this. Nonetheless, it's a good example. So now suppose we want to unify nodes, E and L. Or just unify groups, orange and blue, but we have access to nl and that's what we're calling the unify operation on. Well, we would have two pointers that start on E and L. And where we would want to do is find the root node of e and find the root node of L, and then get one of them to point to the other. But with path compression, we do that, but we're also going to do something else. So let's start by finding the parent node of E. So his parent is Dean and DS is C, C to B, and beat a, an eight F. So we found the root node of E, but with path compression, here's what we're going to do.

Now that we have a reference to the root note, we're going to make He points to the root node. And similarly DS are important to the root node and C, B and A. So now everything along the path got compressed, and now points to that root node. And in doing so, every time we do a look up on either A, B, C, D or E in constant time, we will be able to find out what the parent or the root node is for that component. Because we immediately point to it, we don't have to traverse a sequence of other notes. And we can do this because in a union client, we're always unifying things together and making them more and more compressed whenever and unifying things if you will.

So if we do the same thing for L, we find Al's parent. So we traverse up all the parents until we find the root Then we compress the path. So, J points to G iPhones the G, H points to G. And so we compress that path. But we also have found the parents now, so make one point to the other. And we've unified both groups. So now the group that was once with E and once with l have now been merged into one single group, but the only difference is we've compressed along the way as we've done this, and now it's so much more efficient.

Now let's have a look at another example. And this one, I want to compare and contrast, the regular union find operations. We were doing the last video to the path compression version, we now know. So if I run all those union instructions, this is what happened. So it's Start by getting all these pairs of components, and then executing the instructions on the right. And this is the final state of our union find.

And note that if I'm trying to determine what groups say a and j are n, then I have to traverse a whole bunch of different nodes. So j goes to I use h h goes to eat. But now if I include path compression, let's see what happens. So I still get all those components. But now as I execute the instruction on the right hand side, this is what happens. So I get the green group, but then, because of past compression that Jay merged into the he already counted is a little shorter.

And then I keep executing more instructions. But as I'm doing it, the path gets compressed dynamically. So I'm getting more and more compression, and even up to the very end. So on the last example, we hadn't even finish all the instructions and we have reached the final state. But with past compression, as long as there's something compressed along our path, we get to compress the path along the way pointing it to the root. So right now, we only have one root b e, and almost everything in constant time points to E. So we do a look up on any of our notes and we know that the root is East so we know a belongs to that component.

And this structure becomes very stable eventually because of This path compression. This is why the union find with path compression is so efficient. So I hope you guys enjoyed this video. And I will be going over an implementation of the Union find. You can find it on my GitHub repo@github.com slash William cheese slash data structures. And I will be going over it in the next video, so don't worry about it.

And we'll look at path compression and the union and find operations I also mentioned guys, thanks for watching and I'll catch you next time.