Union Find Path Compression 

Thank you for explaining these concepts so beautifully. Please keep posting new videos. Thank you so much.

Holy mother of clarity. Great explanation, bro.

Just to be clear, path compression happens during a find operation AND union operations? Also, why didn't you also compress A and C to point to E?

Thank you so much it is extremely helpful. One image's worth 1000 of words

All 4 videos on this topic are a gem!

It seems it would be better to set the new root of a union as the root of the tree with the larger height so that the resulting tree has the smallest height possible. See union(H,F) @ 4:07.

In around 4:11, for operation Union(A,C), I don't understand why the result is B points to C instead of B points to D?

Hey, just wondering why at 3:22 you wouldn’t compress all the traversed nodes when finding F to point to G instead, creating a star topology. It seems like this wouldn’t require any more work and would be much more optimal. Sorry to bring this up after so long, haha.

Hey William, I'm kind of confused approx @5:00 when you do the union(J,G). Why are you path compressing based on the new graph? The graph has yet to merge together. I think it would make sense if the graph you are merging into can be path compressed. For example, lets say you have H as root node w/ node I pointing to H, and j pointing to I. There is another directed graph where F is pointing to E. Example 1) Suppose you call union(F,H). Suppose E points to H. Then F should still point to E but E now points to H and H having it's original children nodes. F is not apart of H and you are calling find(F) which has E as its root. Example 2) Suppose you call union(F,I). Then, path compression should happen and I, J and E is pointing to H. Also, F is pointing to E still.

At 4:09, after Union(H, F), why H points to E? H's group is larger.

Great video! Just one doubt. I saw that people already asked why C and A are not connected to E, after compression, and you already answered, but still cant understand :(

Savior. Thanks for this amazing content ! :)

Love the way it's explained.

COuld have explained more clearly as to how it is compressed in each step!

Hi, William! Do you link some nodes like (C, D) and (E, F) (using different ways. It's just for this example or have some reason? Hi William! You link some nodes as (C, D) and (E, F) using different ways (left - > right and left < - right). A little different from the previous video. It's just for this example, or is there some special reason? Thanks, in advance!

At 3:24, should we also point A B C D E to G instead of F?

3:22 Would you not make E, D, C, B, A parents all G?

5:25 finding A or C at this point, still take more than one hop (in this case, 2 hops) since they're not directing pointing at E. Could you prove that such 2 hops in worst case? is it still constant time, or become linear time?

brilliant and easily explained thhanks

Thank you! Great explanation.

My version of union-find doesn't use this path compression method. My version makes the representative of each node union together and all nodes from the smaller group enter the larger group, setting it's representative to the representative of the larger group.

So you use Union Rank (aka Weighted Quick Union) together with Path compression. Which ends up with T O(1) find and union?

Great video series

at 3:27, wouldn't it have been better if everything pointed to G?

4:51 I think "compressing" J to H is not justified in vid. you are not doing Union(J,H) nor Find(J) :(

Thanks

Thank you!

What if I want to increase the size of my array? Initially the array is initialized as 100 say, and I now want to add new element, how does this algorithm tackle that?

Why don't we compress the whole tree after union rather than just the nodes we would like to merge while searching for their roots ?

you are genius, one of the best explanation!!!

thank you!!

hello prime's chat!

Does path compression implies using trees as a data structure for the union find, and without compression means relying on linked lists?

I have one doubt, if we do path compression, we would lose our previous root nodes, so we cannot revert them back :(

Good

5:10 Something that confuses me is that we are compressing the path during union command, but in your source code we compress during find() method

it's not clear at this stage what's the point of all of this - since all nodes are connected you can simply point all nodes to one - no need for "instructions". If the point was to show disjoint components then this example is awful - there is no disjoint components.

omg stop using purple, im color blind, cant distinguish subtle difference between blue and purple. Green would be good!!

it's a kind of bad animation. If the animation made more clear, then it is easier for beginners to understand more.