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

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)，

找到 (x)，它返回包含 x 的树的代表节点，以及

cut (x, y)，将边从x 切到y。

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

希望这可以帮助!