out*_*law 8 c++ java algorithm data-structures
假设我们有一组n个不相交的节点{节点1,节点1,...,节点n }
以下3个操作的最快数据结构和算法是什么:
Union(x,y):在节点x和节点y之间添加无方向边,两个节点之间最多可以有一条边.
IsConnected(x,y):如果节点x和节点y直接或间接连接,则返回true ,即节点x和节点y在同一个连接组件中.
Un-union(x,y):删除节点x和节点y之间的边(如果存在).
Disjoint-set是前两个操作的完美数据结构,但它不能直接支持第3个操作.有什么选择？
如果我们模拟过程,第一个和第三个操作可以在O(1)中实现,但第二个操作是O(n),所以我想看看是否可以在O(logn)时间内运行所有三个操作或更少.
链接/剪切树可以在O(log N)时间内执行这3个操作.
您可以在本书中阅读"链接/剪切树"和相关数据结构:"数据结构和应用手册"(第35章).
链接/剪切树不允许在已经(间接)连接的节点之间添加边缘.如果您需要"Union(x,y)"操作来支持此操作,则问题会变得更加复杂,您可以将其解决为无向图中的动态连接问题.(参见同一本书或本pdf中的第36.4章).在这种情况下,插入/删除复杂性增加到O(log 2 N).
Kaplan,Shafrir和Tarjan提出了一种通过增量重建向联合查找数据结构添加删除的一般技术,并且显示删除分别采用O(t_f(n)+ t_i(n)),这是查找和插入节点的成本.一般的想法是在每个集合中保留已删除项目的数量,并在此数量达到特定阈值时重建集合.
Alstrup,Gørtz,Rauhe,Thorup和Zwick通过指出树中的哪些元素被占用以及哪些是空的并且在删除操作之后"整理"树来显示如何在恒定时间内实现删除.