0
$\begingroup$

Consider the following new operation for disjoint sets
PRINT(x): print every element in S_x the set containing x

One Approach that I found but couldn't figure out completely :
In addition to tree we store a linked list. And each node in the tree in addition to the element
the tree nodes also stores the pointer to element in the linked list.

UNION(x,y) : We union the x and y as usual. But we join the linked list for x and y
So here I could simply point the tail of one list to the head of another.

Print(x) : we obtain the s=FIND-SET(x) and print all the elements of the linked list pointed to
by s. This will print all the elements. Now for this to work in the UNION to merge the linked list has to be done in a proper way so that
the root of the tree always point to the beginning of the list.
This can be done like when I merge Tree2 into Tree1 that is point the root of Tree1 to root of
Tree2 then I point the tail of Tree2 list to head of Tree1 list. In the way the merged list
will start with the root node of the tree (or the extra element stored in the root of tree)

Will this approach work or there are some flaws in this ?

Confusion points :

  1. MAKE-SET(x) It's always mentioned that it takes O(1) time. As we have to create a single node
    But what if the element x is already there. Then we don't create the node we have to first
    execute FIND-SET(x) and see if it returns anything and then execute MAKE-SET(x).
$\endgroup$
7
  • $\begingroup$ What is exactly your confusion point? and what does it have to do with the rest of the question? (i.e., the Print operation). Your approach of the linked list will work in the sense that: if you keep a linked list for each set, then of course you can print it whenever you want. If you have $L_1$, the list corresponding to a set $S_1$, and $L_2$ corresponding to $S_2$, then when merging $S_1$ and $S_2$, simply joining their linked lists as $L_1 \to L_2$ gives you a linked list of the union. Are you worried about the complexity? the implementation? $\endgroup$ Commented Apr 19, 2021 at 21:17
  • $\begingroup$ 1) Whether this approach of merging linked list works and with required complexity. I am somewhat unconfident about the approach. But as you mentioned this approach seems coorect. $\endgroup$
    – pensee
    Commented Apr 20, 2021 at 3:08
  • $\begingroup$ 2) The confusion point $\endgroup$
    – pensee
    Commented Apr 20, 2021 at 3:08
  • $\begingroup$ For maintaining the linked-list so that Print is O(S_x). We need to store the head and tail pointer of the list in the tree node. So that will be required to merge the list while doing Union. So here I am storing two extra data in the tree node. Is it possible to do it using just one additional attribute to the tree node $\endgroup$
    – pensee
    Commented Apr 20, 2021 at 5:17
  • 1
    $\begingroup$ Why do you want to use one attribute per tree node? You can use constantly many without asymptotically affecting neither the time nor the space complexity $\endgroup$
    – Steven
    Commented Apr 20, 2021 at 7:57

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.