是否有一个很好的数据结构来执行查找、联合和去联合？

Question

我正在寻找一种可以相当有效地支持联合、查找和去联合的数据结构（一切至少为 O(log n) 或更好），因为标准的不相交集结构不支持去联合。作为背景，我正在使用 MCTS [ http://en.wikipedia.org/wiki/Monte_Carlo_tree_search]编写围棋 AI ，这将用于跟踪棋子组，因为它们在回溯过程中连接和断开。我认为这可能会使事情变得更容易，因为 de-union 不是在集合中的某个任意对象上，而是始终是最新联合的“撤消”。

我已经通读了以下论文，虽然我可以完成建议的数据结构，但它似乎有点过头了，需要一段时间才能实现 http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article =1773&context=cstech

当然，虽然 O( a(n)) 会很棒，但我很确定路径压缩不适用于 de-union，而且我对 O(log n) 感到满意。我的直觉告诉我一个解决方案可能与堆有关，但我一直无法弄清楚。

Answer 1

你所描述的有时被称为 union-find-split 问题，但大多数现代数据结构（或至少，我所知道的）通常对这个问题有不同的看法。将每个元素视为森林中的一个节点。然后您希望能够在操作下维护森林

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

这些数据结构通常称为动态树或链接切割树。据我所知，没有与标准 union-find 数据结构的实现简单性相匹配的高效数据结构。可能对您的案例有帮助的两种数据结构是链接/切割树（也称为 Sleator-Tarjan 树或 ST-tree）和 Euler-tour 树（也称为 ET-tree），它们都可以执行所有上述操作的每个时间为 O(log n)。

希望这可以帮助！