假设我们有一组n个不相交的节点{node1,node1,…,noden}
以下3个操作的最快数据结构和算法是什么：
> Union(x,y)：在nodex和nodey之间添加一个非定向边,两个节点之间最多只能有一条边.
> IsConnected(x,y)：如果nodex和nodey直接或间接连接,则返回true,即nodex和nodey在同一个连接组件中.
> Un-union(x,y)：删除nodex和nodey之间的边缘(如果存在).
Disjoint-set是前两个操作的完美数据结构,但它不能直接支持第3个操作.有什么选择？
如果我们模拟过程,第一个和第三个操作可以在O(1)中实现,但第二个操作是O(n),所以我想看看是否可以在O(logn)时间运行所有三个操作或更少.
解决方法
Link/cut tree可以在O(log N)时间内执行这3个操作.
您可以在本书中阅读有关链接/剪切树和相关数据结构的信息：“Handbook of Data Structures and Applications”(第35章).
链接/剪切树不允许在已经(间接)连接的节点之间添加边缘.如果您需要“Union(x,y)”操作来支持此操作,则问题会变得更加复杂,您可以将其解决为无向图中的动态连接问题. (见同一本书或第this pdf章第36.4章).在这种情况下,插入/删除复杂性增加到O(log2 N).
