我正在寻找一种可以相当有效地支持联合、查找和去联合的数据结构（一切至少为 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) 感到满意。我的直觉告诉我一个解决方案可能与堆有关，但我一直无法弄清楚。