The dynamic-set operation UNION takes two disjoint sets S1 and S2 as input, and it returns a set S = S1 U S2 consisting of all the elements of S1 and S2. The sets S1 and S2 are usually destroyed by the operation. Show how to support UNION in O(1) time using a suitable list data structure.
UNION of two lists
2
$\begingroup$
algorithms
-
0Henning Makholm - Thank you. I will be glad to discuss it anywhere. – 2012-07-03
1 Answers
1
If all you care about is the union operation and all other operations (such as membership testing) can be as slow as you want to, just concatenate the two linked lists. This can be done in constant time if you make sure to remember a pointer to both the first and the last element of each list. Remember to check whether the two lists are the same.
If there is no requirement that the result must be a list, you could also represent a set as an unordered binary tree with the members in the leaves. Then the union operation consists just of creating a new root node with the two operands as children. And that doesn't even destroy the original sets.
-
0Well, I suppose that we have to know about the tails, otherwise it's impossible to unite (we will lose some data or the order will be incorrect) or we can use some other data structure to store a united set. We don't need to delete duplicates. – 2012-07-03