不相交集合指的是，将一组元素划分成若干个集合，每个元素必定属于某个集合且只能属于一个集合。
不相交集合的操作
不相交集合有三个操作：
1.MAKE-SET
创建一个集合，传入一个元素 x
2.UNION
将两个集合合并成一个
3.FIND-SET
查询元素 x 所在的集合
不相交集合的一个应用是，确定无向图的连通分量
不相交集合的链表表示
用链表的方式实现不相交集合，将集合中的对象串成一个链表，简洁明了。
MAKE-SET 和 FIND-SET 两种操作都只需要 O(1) 时间。
UNION 操作由于要更新元素到集合对象的指针，效率较低，需要O(n) 的执行时间，n 为链表长度。
一种加权合并的启发式策略，执行 UNION 操作时将较短的集合合并到较长的集合。
可以证明，在这种策略下，m 个操作的序列需要 O(m+nlgn) 时间。（n 为 MAKE-SET 操作的数量，即元素的数量）
不相交集合森林
不相交集合森林，是将每个集合定义为一颗树，所有的集合组成森林。
在不相交集合森林的操作中，
MAKE-SET 简单的创建一颗只有一个结点的树。O(1)
FIND-SET 需要从结点向上寻找到根结点。O(h)
UNION 将两棵树通过，将一颗树的根结点指向另一颗树的方式，合并成一棵树。O(1)
书中给出了两种启发式策略，以改进数据结构的运行效率
1.按秩合并
每个结点维护一个秩，秩不同于链表发中的集合结点数，秩是树高度的一个上界。在 UNION 操作中，我们让较小秩的根成为较大秩根的子结点。
2.路径压缩
路径压缩是在 FIND-SET 的向上寻找的过程中，顺便将路径上的结点都变为根的子结点。一个直观的改进是，下一次对路径上结点的 FIND-SET 操作都只需要 O(1) 时间。
同时使用两种启发式策略后，m 个操作只需要 O(ma(n)) 时间。
带路径压缩的按秩合并的分析
这一节的主要内容是证明，使用了两种启发式策略后，不相交集合森林的性能。
先证明了上一节的结论中 a 函数的定义，一个增长非常慢的函数，可以认为在我们能想象到的数字中，a(n) 都小于 4
给出了一个非常复杂的势函数
最后分别证明了三种操作的摊还代价都为 O(a(n))，合并结论即得到上一节给出的结论，m 个操作只需要 O(ma(n)) 时间。
网友评论