The last Union method doesn't increase the "RANK" (size) after the merge of the two sets. Also, after merging of "many" sets, the time complexity of Find will still be O(depth).
You can improve the performance of the structure by putting Parent[item] = Find(Parent[item]); and then returning Parent[item] - in the else case. This simulates the tree "flattening", and provides amortized O(1) performance. :) Cheers and thank you!
Nice video, thank you. However the union function is a bit simplistic. I know it is hard to code an exact data structure but it would be nice to mention that additional checks. Like not being able to union 'chars' that are not roots. But great video.
Hey bo, could you tell me what tools you use to create such high quality videos? I'll to create educational youtube videos of such high quality as yours.
your second union implementation is incorrect for what you're describing. You are right in saying that a smaller tree should be attached to the bigger one, but that does not really solve the problem of the height of the tree, because you can attach a tree to the END (leaf) of another tree, and its height would increase by the size of the smaller tree. But you don't change the ranks at all for that even in your method, which would lead to big erros in the future for comparing ranks of trees. If you wanted to solve the height issue, you should first: 1) Find the root of set_1 2) Find the root of set_2 3) THEN compare the Ranks of those 2 sets and union accordingly and increase rank of root by (bigger tree rank) - (smaller tree rank)
You don't attach the root of the smaller tree to a leaf... you attach the root of the smaller tree to the root of the larger tree. The height of the resultant tree has not changed. set_1 and set_2 are the roots of their respective trees.
I think the implication is that you would first use the find function to get the loot, and then use union on that. It would be smart to enforce that though, a simple find function in union would do it.
you are awesome. Thanks for your help. Can you also solve problems with the "trie" data structure? What about backtracking problems, boyle-morris, kmp, and rabin-karp searching for multiple words simultaneously? I would appreciate it. I'm already subscribed to your channel.
great video--but your initial union function makes the parent of the second argument the first argument. Meaning, UNION(a, b) makes a the parent of b. However, your diagrams do not show this. Thank you for the content.
![BLACK BAG - Official Trailer [HD] - Only in Theaters March 14](http://i.ytimg.com/vi/Du0Xp8WX_7I/mqdefault.jpg)
You sir, are an amazing person.
Your knowledge and teaching skills are simply awesome!
superb video! I mean the whole series too, this is way better than my teacher's instructions
Love these videos, very straight forward and well defined.
Your tutorials are amazing. Thank you so much for putting the time and creating them
Thank you very much for this tutorial!
Your illustrations have helped me understand the concept clearly
Thank you for your effort ! This has proven to be a great help for me.
Awesome tutorial, short and precise.
This is an excellent tutorial on Disjoint Set. Thank You!!!
Can you please create more videos like this? I find this combination of code walkthrough and algorithm explaination very easy to comprehend
subscribed. I'm watching you forever. I feel a job at Google or Facebook coming. Thanks so much.
The last Union method doesn't increase the "RANK" (size) after the merge of the two sets. Also, after merging of "many" sets, the time complexity of Find will still be O(depth).
This is a very good explanation.
You can improve the performance of the structure by putting Parent[item] = Find(Parent[item]); and then returning Parent[item] - in the else case.
This simulates the tree "flattening", and provides amortized O(1) performance. :)
Cheers and thank you!
Nice video, thank you. However the union function is a bit simplistic. I know it is hard to code an exact data structure but it would be nice to mention that additional checks. Like not being able to union 'chars' that are not roots. But great video.
Correct, the union should look for the root node before performing the operation
Hey bo, could you tell me what tools you use to create such high quality videos? I'll to create educational youtube videos of such high quality as yours.
This is a great explanation. Since you're using a hash table how would you print out the members of the set?
Man the way he spelled the LOOT that was
amazing
Nice. But what about a time complexity of the improved (with ranks) algorithm?
is Union(S1,S2) = Union(S2, S1)?
are Sets data structure and Disjoint Sets same?
Is there an example of a Disjoint Set that remembers the size of each set?
The website in your description does not work.
your second union implementation is incorrect for what you're describing. You are right in saying that a smaller tree should be attached to the bigger one, but that does not really solve the problem of the height of the tree, because you can attach a tree to the END (leaf) of another tree, and its height would increase by the size of the smaller tree. But you don't change the ranks at all for that even in your method, which would lead to big erros in the future for comparing ranks of trees.
If you wanted to solve the height issue, you should first:
1) Find the root of set_1
2) Find the root of set_2
3) THEN compare the Ranks of those 2 sets and union accordingly and increase rank of root by (bigger tree rank) - (smaller tree rank)
Correct indeed, however his picture illustration helped me to understand the concept clearer.
You don't attach the root of the smaller tree to a leaf... you attach the root of the smaller tree to the root of the larger tree. The height of the resultant tree has not changed. set_1 and set_2 are the roots of their respective trees.
I think the implication is that you would first use the find function to get the loot, and then use union on that. It would be smart to enforce that though, a simple find function in union would do it.
Bo Qian, what IDE are you using? Thanks for the video.
+OUR S10 Looks like visual studio
+OUR S10 Def codeblocks
very clear, very good
you are awesome. Thanks for your help. Can you also solve problems with the "trie" data structure? What about backtracking problems, boyle-morris, kmp, and rabin-karp
searching for multiple words simultaneously? I would appreciate it. I'm already subscribed to your channel.
This really helped! Thanks alot
Thanks bo. you are very good. Can you please solve problems with advanced data structures like Trie and Suffix tree?
that really helped sir...tq so much
Thanks a lot sir. Very useful video :)
Can you post source code?
thanks for the lutorial!
Awesome, thanks
真棒！！！
Great video with a great accent (not sarcastic)
chigga r u saying loot
thank you
Love your video, very helpful... Just hope you could speak a little faster...
Thumb up !!!
"loot"?
yes, return the loot) Still, excellent explanation. liked:)
There must be mega-like or super-like kind of thing along with like ..👍👍
great video--but your initial union function makes the parent of the second argument the first argument. Meaning, UNION(a, b) makes a the parent of b. However, your diagrams do not show this. Thank you for the content.
Niubility
"loot" lol
loot
You have amazing videos but you really need to work on your 'r' and 'l'.