In Disjoint Sets, why do we make the smaller tree the subtree of the larger one?

Question

Currently I'm learning about the Disjoint Sets data structure. I understand that, when we create a union of two disjoint sets, we create a kind of "backwards" tree for fast lookup. As Skiena says in his book:

To minimize the tree height, it is better to make the smaller tree the subtree of the bigger one. Why? The height of all the nodes in the root subtree stay the same, while the height of the nodes merged into this tree all increase by one. Thus, merging in the smaller tree leaves the height unchanged on the larger set of vertices.

I don't get this part, the description is not clear to me. Could someone clarify why we need to make this distinction?

Answer 1

Probably best explained with pictures. Say we have these two sets $A$ of height 2 and $B$ of height 3:

Now we have a choice when joining them:

1. Attach root of $B$ to root of $A$.
2. Attach root of $A$ to root of $B$.

Remember we are optimizing for look-up / $find()$. Let's see what happens in either case.

Attach root of $B$ to root of $A$.

We end up with this resulting set of height 4:

Attach root of $A$ to root of $B$.

We end up with this resulting set of height 3!

Wonderful! We've increased the size of the set without increasing the height. In this scenario our find will take at most 3 iterations, same as what we originally had because $B$ was of height 3 to begin with. In the other scenario we have at most 4 iterations because we've increased the height of the new set by 1. This is why it is always preferable to join the shorter tree to the taller one, because it will not increase the height of the taller tree (unless they are the same height). Thus, optimizing for look-up.