In Disjoint Set Union (D.S.U.), why do we make the smaller sized subset as the child of the larger sized subset while performing the union operation?

Question

I recently came across D.S.U. and its applications on the tree.As i was solving the related problems, I got Time Limit Exceeded error in some so i read the tutorial again and there I found that an improvised version of the normal union is weighted-union. In this weighted union operation, we make the smaller sized subset's root as child of larger sized subset's(among the two) root. How is it benefiting us? Link to Tutorial

Answer 1

You should realise the purpose/logic behind weighted union-find.

First, why do we need weighted union-find? That's because a simple inefficient union-find can lead to an unbalanced tree. In the worst cast a linked list. What's the complexity of traversal over a linked list? O(N). That's the worst complexity when using a simple union-find.

Our goal is - balancing the hence-formed tree.

How and why weighted union-find works? It's a simple optimization by just keeping the size of each subset and making the smaller subset child of the larger subset when performing union between the two.

Why this works? Because, as mentioned, our goal is to balance out the tree when doing the union and not unbalance it. If you make the smaller subset a child of the larger subset, the height of the overall tree is not increasing (obv when the sizes are equal we handle it differently :/). On the other hand, if you make the bigger subset a child of the smaller tree, you know what will happen.

Using just this optimization we improve the worst case time complexity from O(N) to O(log2(N)) - because the height of the tree will never go beyond log2(N)

There's another optimization that can be done along with this which will take the complexity down even further. Your link probably has it.

Answer 2

Doesn't make difference in correctness' point of view, but it is usually faster.

Check this example:

In the first case, you put the biggest set as child of the smallest. You can see that in this case, if you try the find method in the deepest node, it will perform 3 steps. This doesn't happen in the second case.

This is not a rule but pratically it's what happens.