我正在寻找一种可以相当有效地支持并集、查找和解并的数据结构（一切至少 O(log n) 或更好），因为标准的不相交集结构不支持解并。作为背景，我正在用 MCTS 编写 Go AI [http://en.wikipedia.org/wiki/Monte_Carlo_tree_search] http://en.wikipedia.org/wiki/Monte_Carlo_tree_search%5D，这将用于跟踪石子组在回溯期间连接和断开的情况。我认为这可能会让事情变得更容易，因为解除联合不是在集合中的某个任意对象上，而是始终是最新联合的“撤消”。
我已经阅读了以下论文，虽然我可以完成建议的数据结构，但它似乎有点过头了，需要一段时间才能实现
当然，虽然 O( a(n)) 会很棒，但我很确定路径压缩不适用于 de-union，并且我会对 O(log n) 感到满意。我的直觉告诉我一个解决方案可能与堆相关，但我还没有弄清楚任何事情。
您所描述的有时称为并集查找拆分问题，但大多数现代数据结构（或者至少是我所知道的数据结构）通常以不同的方式看待这个问题。将每个元素视为森林中的一个节点。然后您希望能够在操作下维护森林
-
link(x, y)，添加边 (x, y)，
-
find(x)，返回包含 x 的树的代表节点，以及
-
cut(x, y)，切割从 x 到 y 的边。
这些数据结构通常被称为动态树 or 链接切割树。据我所知，没有任何有效的数据结构可以与标准并查数据结构的实现简单性相匹配。可能对您的情况有帮助的两种数据结构是链接/剪切树（也称为 Sleator-Tarjan 树或 ST 树）和欧拉图树（也称为 ET 树），两者都可以执行所有操作上述操作的时间分别为 O(log n)。
希望这可以帮助！
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
