2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

ds1

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:

ds2

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

We end up with this resulting set of height 3!

ds3

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.