是否存在执行查找，合并和取消联合的良好数据结构？ [英] Is there a good data structure that performs find, union, and de-union?

问题描述

我正在寻找一种数据结构，该结构可以相当有效地支持联合，查找和取消联合（所有事物至少为O（log n）或更好），因为标准的不相交集结构不支持取消联合。作为背景，我正在使用MCTS [ http://en.wikipedia.org/wiki编写Go AI / Monte_Carlo_tree_search] ，这将用于跟踪成组的石头在回溯过程中的连接和断开连接。我认为这样做可能会更容易，因为去工会不在集合中的任意对象上，而是总是对最新工会的撤消。

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.

通读下面的文章，尽管我可以完成建议的数据结构，但似乎有点过头了，并且需要花一些时间来实现
http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1773&context=cstech

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

当然，O（a（n））会很好，但我敢肯定，路径压缩将不适用于去工会，而我会对O（log n）感到满意。我的直觉告诉我一个解决方案可能与堆有关，但我一直无法弄清楚。

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.

推荐答案

描述有时被称为联合查找分离问题，但是针对它的大多数现代数据结构（至少，至少我所知道的）通常对问题的看法不同。将每个元素都视为森林中的一个节点。然后，您希望能够在以下操作下维护目录林

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

• 链接（x，y），其中添加边（x，y），


• 查找（x），返回包含x的树的代表性节点，以及


• 剪切（x，y），将边沿从x剪切到y。

• 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.

这些数据结构通常称为动态树或链接剪切树。据我所知，没有有效的数据结构可以与标准联合查找数据结构的实现简单性相匹配。可能对您的情况有用的两个数据结构是链接/剪切树（也称为Sleator-Tarjan树或ST树）和Euler-tour树（也称为ET树），两者都可以执行所有操作。

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.

希望这会有所帮助！

这篇关于是否存在执行查找，合并和取消联合的良好数据结构？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！