有没有一种良好的数据结构可以执行查找、联合和取消联合操作？

Question

我正在寻找一种数据结构，能够支持联合、查找和分离操作，效率至少为O(log n)或更好。标准的不相交集合结构不支持分离操作。背景是我正在编写一个使用MCTS [http://en.wikipedia.org/wiki/Monte_Carlo_tree_search]的Go AI，并且需要在回溯过程中跟踪棋子组的连接和断开。我认为这可能会更容易，因为分离操作不是针对集合中的某个任意对象，而是针对最新联合操作的“撤消”。

我已经阅读了下面的论文，虽然我可以实现所提出的数据结构，但它似乎有点过于复杂，需要一段时间才能实现。 http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1773&context=cstech 虽然O( a(n))的效率非常棒，但我很确定路径压缩无法与分离操作一起使用，而我将满足O(log n)的效率也很满意。我的直觉告诉我这可能与堆有关，但我还没有想出任何解决方案。

- user1040423

---

可能会在计算机科学SE社区获得更多关注。 - Mephy

Answer 1

您描述的问题有时被称为并查集分裂问题，但是大多数现代数据结构（至少我知道的）通常从不同的角度来看待这个问题。把每个元素都看作是森林中的一个节点。然后您希望能够在以下操作下维护该森林：

• link(x, y)，添加边(x, y)
• find(x)，返回包含x的树的代表节点，以及
• cut(x, y)，切断从x到y的边。

这些数据结构通常称为动态树或链剖树。就我所知，没有一种高效的数据结构可以与标准的并查集数据结构实现简单性匹配。两种可能有助于您的情况的数据结构是链剖树（也称为Sleator-Tarjan树或ST树）和欧拉游览树（也称为ET树），它们都可以在O(log n)的时间内执行上述所有操作。

希望对您有所帮助！

- templatetypedef

---

啊，我怎么能忘记链/剪树了！非常感谢，我也会看看ET树。 - user1040423

Answer 2

另一个答案过于复杂。您可以使用标准的并查集数据结构，每次设置parent[x] = y时，将(x, old_parent)附加到堆栈中。在回溯时，只需重置为旧值即可。

您也可以使用路径压缩来做同样的事情，但是开销可能不会得到补偿。此外，如果您在每个union调用中进行多个修改，则需要向堆栈添加分隔符，以便知道何时停止。

- user1502040