# Complexity of testing membership in a disjoint set

I have a disjoint set data structure (sometimes known as a union-find data structure) where I store a value in each "node". I want to look up a node by value. How can I do this?

The representations normally discussed in literature, both linked list and forests, deal with operations being given nodes (of the linked list or forest), not values contained therein, which avoids any difficulty caused by having to find the node that contains a given value. From what I can see, the question of whether a given disjoint set contains in any subset a given value, or finding the node that contains a given value if one exists, is scarcely touched by the literature.

However, given values, this question needs to be addressed for an implementation of what the CLRS Introduction to Algorithms calls Make-Set(x) if one wishes to not trust the user of the API to always know what is and is not in the set, as it has a prerequisite that x does not already exist in the set.

With both representations, I see no way better than $O(n)$ to check membership, as one must always check all nodes for equality. Obviously one could maintain a separate mapping of values to nodes for the set, with $O(log n)$ lookup given an ordered value type, but this means duplicating the whole set in memory. Is there any way to represent a disjoint set while being able to test set membership in less than $O(n)$ time without duplicating the data?

• (I know this isn't the best worded question in the world; feel free to ask me for clarifications or edit the question to reword it! I hope the question I'm asking is clear, however!) – gsnedders Jun 6 '16 at 0:41
• What exactly are you trying to achieve? This seems muddled and like it's talking about multiple algorithmic tasks. What are the inputs, and what are the outputs? I don't understand what you mean by "whether a given disjoint set contains in any subset a given value" - what does that mean? Why do you think that there's something that needs to be addressed for MakeSet() to work properly? Also, when you use the phrase "disjoint set", are you referring to the data structure or one node/equivalence class within it? Can you try editing to address these issues? – D.W. Jun 6 '16 at 3:12
• You try to make your union-find data structure into a read-only dictionary. New trade-offs will arise. – Raphael Jun 6 '16 at 8:58
• Would maintaining an array of pointers count as "duplicate data" for you? – Raphael Jun 6 '16 at 9:01

There's an easy way to find the node that contains a given value. You have two data structures: a union-find data structure (that keeps track of which nodes are in the same equivalence class), and a hashtable (that maps from a value to the node(s) that contain that value).

The MakeSet operation adds a new set to the union-find data structure and adds a new entry to the hashtable. The Union operation and Find operations use only the union-find data structure. The "look up a node by value" operation uses the hashtable.

The running time of the MakeSet, Union, and Find operations is as in the underlying union-find data structure. (MakeSet incurs an extra $O(1)$ (expected, amortized) time to insert into the hashtable, but this doesn't change the overall running time of MakeSet.) The running time of looking up a node by value is $O(1)$ (expected, amortized) time, if you have a good hash function and if each value is only found in a single node.

This doesn't require duplicating the data, if you use pointers in lieu of duplicating: each entry in the hashtable can have a pointer to the node, and each node has a pointer to the value, so values and nodes aren't duplicated. Of course, this does increase the memory usage (by at most a constant factor); nothing is free in life.

• I still don't agree with the running-time of MakeSet. Hashtables have fixed size, (many) union-find structures don't. So you need to account for the cost of moving to a larger table. You can remain withing $O(1)$ expected amortized cost, I guess. But there will be slow MakeSets, which may be a dealbreaker. – Raphael Jun 7 '16 at 6:54
• @Raphael, good point. It needs to be expected, amortized time. If you're using standard union-find data structures, you're already in the universe of amortized running time. – D.W. Jun 7 '16 at 7:03
• IIRC, MakeSet is typically $O(1)$ without amortization. – Raphael Jun 7 '16 at 7:09
• @Raphael, sure. The question didn't say that amortization is unacceptable; it merely asks for running time better than $O(n)$. And if for some reason this was important, it's possible to remove the amortization and make MakeSet run in $O(1)$ expected time, without amortization, by standard tricks (when the hashtable gets close to 50%-full, you on the side slowly start building a twice-as-large table in parallel, a little at a time, and then switch over to that once the hashtable is 100%-full -- rather than waiting until the hashtable is full and doing the resize all at once). – D.W. Jun 7 '16 at 7:20
• @D.W. Sorry, I missed your later edits (I'd meant to add a comment or two when I got back to a computer…), but I think with the edits that's a great answer to my question! – gsnedders Jun 14 '16 at 16:07