How to draw a visualization of disjoined set structure for the following p[] array?

Question

I have answered the following assignment:

Problem 1. Draw a visualization of the disjoint-set structure as we did in class for the following p[] array.

  i = [0 1 2 3 4 5 6 7 8 9],
p[i]= [2 2 2 3 4 4 4 7 3 7]

Problem 2. Suppose link(i, j) is the method as discussed in class that implements lazy linking with height (depth) control (i.e., point small into large). Draw a visualization after link(1,9) is called on the disjoint-sets data structure with the p[] array above. If you have heard of path compression, note that it does this without path compression.

Here are my answers:

Is my diagram correct?

Answer 1

You have an error in the first picture. The first tree should not have 0 as root, but 2. As p[0] indicates what the parent is of 0, we should see that 2 is a parent node and has 0 as child. The same goes for p[1], and so the first tree should be:

      2
     / \
    0   1

Also the second picture seems wrong.

First of all, the assignment says that no path compression should be used. That means that nodes 7 and 9 should not become siblings, but should remain in their original parent-child relationship.

Secondly, when two nodes are linked, a disjoint set algorithm will first retrieve the root nodes of the sets (trees) those two nodes are in.

In your example of link(1, 9), the first step would be to find the root of 1, which is 2 as can be seen in the above (corrected) representation. The root for 9 is 7. So now the problem is translated to link(2, 7).

As the assignment states that we should use a height controlled join, there is some ambiguity, because both involved trees (the one rooted by 2, and the other rooted by 7) have the same height. So we could choose which of these two roots will become the root of the joined set. Maybe in your class a specific algorithm was presented that would break that tie (of equal heights) by giving the first root precedence over the second. If so, then 7 should become the direct child of 2:

       2
      /|\
     0 1 7
         | 
         9

But there is no reason (nothing in your post) that would prevent us from choosing node 7 as the root, and then it would be:

       7
      / \
     9   2
        / \
       0   1

But either way, the already existing parent-child relationships should remain as they are when it is given that we should not perform any path compression.