Union Find Path Compression

let's talk about path compression now this operation is really what makes the UN 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 and the union operation work otherwise you won't understand what's going on and what's up with path compression and how we're going to get that really nice amortized constant time all right 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 uh e and l or just unify groups uh orange and blue but we have access to enl and that's what we're calling the unify operation on well we would have two pointers that start on enl and what we would want to do is find the root node of e and find the root node of L and then uh 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 E's parent is uh D and then D's is c c to B uh and B to a and then a to 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 node we're going to make make e point to the root node and similarly D is going to point to the root node and c and 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 lookup on either a b c d or e in constant time we will be able to find out what the parent or or the root node is for that component because we immediately point to it we don't have to Traverse a sequence of other nodes and we can do this because in a union find we're always unifying things together and making them more and more compressed we're never un unifying things if you will so if we do the same thing for L we find L's parent so we Traverse up all the parents until we find the root and then we compress the path so uh J points to g i points to g h points to G and 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 the regular Union find operations we were doing the last video to the path compression version uh we now know so if I run all those Union instructions uh this is what would happen so I start by getting all these pairs of components and then now I'm 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 in then I have to Traverse a whole bunch of different nodes so J goes to I I goes to h h goes to e 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 uh this is what happens so I get the green group but then because of path compression that J merged into the H so already that path is a little shorter and then I keep executing more instructions but as I'm doing it uh the path gets compressed dynamically so so I'm getting more and more compression and even up to the very end so on the last example we haven't even finished all the instructions and we have reached the final state but with path compression as long as there's something to compress 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 being e and almost everything in constant time points to uh e so we do a look up on any of our nodes and we know that the root is e so we know it belongs to that component and this structure becomes very stable eventually uh because of this uh path compression this is why the unit 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 uh you can find it on my GitHub repo at github.com Willam FUSD structures and I will all go be going over 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