不支持删除的不相交集合数据结构

Question

假设我们有一组n个不相交的节点{node₁, node₂,..., node_n}

对于以下三种操作，最快的数据结构和算法是什么：

1. Union(x,y)：在节点_x和节点_y之间添加无向边，两个节点之间最多只能有一条边。

2. IsConnected(x,y)：如果节点_x和节点_y直接或间接相连，则返回true，即节点_x和节点_y在同一个联通分量中。

3. Un-union(x,y)：如果存在，则删除节点_x和节点_y之间的边。

Disjoint-set是实现前两个操作的完美数据结构，但它不能直接支持第三个操作。有什么替代方案吗？

如果我们模拟这个过程，第一个和第三个操作可以在O(1)时间内实现，但第二个操作需要O(n)时间，因此我想知道是否可能将这三个操作都运行在O(logn)时间或更短的时间内。

- outlaw

Answer 1

割边树（Link/cut tree） 可以在 O(log N) 的时间内执行以下三个操作。

您可以在本书中阅读关于割边树和相关数据结构的内容：《数据结构与应用手册》（第35章）。

割边树不允许在已经（间接地）连接的节点之间添加边。如果您需要支持 "Union(x,y)" 操作，则问题会变得更加复杂，并且您可以将其作为无向图动态连通性问题来解决。 （请参见同一本书的第36.4章或此PDF）。在这种情况下，插入/删除复杂度增加到 O(log² N)。

- Evgeny Kluev

---

太棒了，这是一个很好的参考！实际上我曾经听说过这种数据结构，但是对我来说理解起来很困难，我会看看这次能否理解。 - outlaw

Answer 2

Kaplan, Shafrir和Tarjan提出了一种通用技术，通过增量重建来添加删除到并查集数据结构，并展示了删除所需的O(t_f(n) + t_i(n))，分别是查找和插入节点的成本。其主要思想是在每个集合中保持已删除项目的数量，并在该数量达到某个阈值时重新构建集合。

Alstrup，Gørtz，Rauhe，Thorup和Zwick展示了如何通过注意树中哪些元素被占用，哪些元素是空闲的，并在删除操作后“整理”树来实现常数时间内的删除。

- Eran