1
$\begingroup$

I need data structure that is able to perform the following operations efficiently:

  1. Insert a new element into a set.
  2. Lookup element in set.
  3. Compute the union of two sets.

Union operation should return a new set containing all unique elements from both input sets (i.e., no duplicates).

I've also looked into tree-based data structures like Red-Black Trees or AVL Trees, but can't find comprehensive information about union operations on them. I have a feeling that they support fast unions of disjoint sets only. Though, I can't find good resources on this topic.

Can someone suggest a suitable data structure or algorithm that can handle all three operations (insert, lookup, and union) efficiently for sets with arbitrary elements (not only disjoint sets)?

Is this possible to implement it faster than with hash tables?

Thank you in advance!

$\endgroup$
3
  • 1
    $\begingroup$ Can you define what you mean by "efficiently"? There are many possible answers, with different tradeoffs between the running time of each operation. How will you evaluate answers? What are your requirements? What approaches can you already come up with, and what is the running time for each operation with those? That might help you articulate your requirements. For instance, will you accept a data structure where computing the union of two sets takes $O(a+b)$ time, where $a,b$ counts the number of elements in each set? $O((a+b)\log(a+b))$ time? $\endgroup$
    – D.W.
    Commented May 5 at 18:30
  • $\begingroup$ Do you need immutable sets, i.e., a persistent data structure? $\endgroup$
    – D.W.
    Commented May 5 at 18:35
  • $\begingroup$ I think this answer is good, you can do disjoint union sets, and have efficient unionization, potentially more efficienct than a hash-table, but potentially slower searching than a hash-table. $\endgroup$ Commented May 6 at 2:41

1 Answer 1

3
$\begingroup$

Here are a few ideas:

  • There are balanced binary search tree variants which are designed for efficient union/meld, such as weight-balanced trees. It's fairly well-established that the purpose of balancing a binary search tree is to avoid pathological behaviour, so to a first approximation, any balance scheme is as good as any other for insertion and querying.
  • Tries support an obvious linear-time merge operation.
  • Extendible hashing has a union operation that is easier to parallelise than other hash table variants, which might be a consideration.
  • B+-trees with relaxed balance is worth considering. You can traverse the elements in sorted order in both trees (i.e. using sort-merge), and insert the elements from the smaller tree into the larger one, splitting nodes to perform the insertion. You can then lazily rebalancing the large tree either on the fly (i.e. as you finish a leaf node), or at the end.
$\endgroup$

Your Answer

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

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