Is there a good data structure that performs find,

Question

I am looking for a data structure that can support union, find, and de-union fairly efficiently (everything at least O(log n) or better) as a standard disjoint set structure doesn't support de-unioning. As a background, I am writing a Go AI with MCTS [http://en.wikipedia.org/wiki/Monte_Carlo_tree_search], and this would be used in keeping track of groups of stones as they connect and are disconnected during backtracking. I think this might make it easier as de-union is not on some arbitrary object in the set, but is always an "undo" of the latest union.

I have read through the following paper and, while I could do the proposed data structure, it seems a bit over kill and would take a while to implement http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1773&context=cstech

While O( a(n)) would be great, of course, I'm pretty sure path compression won't work with de-union, and I'd be happy with O(log n). My gut tells me a solution might be heap related, but I haven't been able to figure anything out.

Answer 1

What you're describing is sometimes called the union-find-split problem, but most modern data structures for it (or at least, the ones that I know of) usually view this problem differently. Think about every element as being a node in a forest. You then want to be able to maintain the forest under the operations

• link(x, y), which adds the edge (x, y),
• find(x), which returns a representative node for the tree containing x, and
• cut(x, y), which cuts the edge from x to y.

These data structures are often called dynamic trees or link-cut trees. To the best of my knowledge, there are no efficient data structures that match the implementation simplicity of the standard union-find data structure. Two data structures that might be helpful for your case are the link/cut tree (also called the Sleator-Tarjan tree or ST-tree) and the Euler-tour tree (also called the ET-tree), both of which can perform all of the above operations in time O(log n) each.

Hope this helps!