数据结构重读 – 树和等价问题(并查集)

数据结构这书感觉和之前没读过一样……以前从来没发现树这章还讲了并查集……

若R是集合S上的一个等价关系,则由这个等价关系可以产生这个集合的唯一划分。

如何划分等价类

假设集合S有n个元素,m个形如(x, y),的等价偶对(x, y都是集合S中的元素)。

(1)令S中每个元素各自形成一个只含单个成员的子集,记作S1, S2, …, Sn。
(2)依次读入m个偶对,对每个读入的偶对(x, y),判定x和y所属的集合,若他们还不属于同一集合,设x属于Si,y属于Sj,则合并Si和Sj。

集合操作的实现与并查集

其实上面描述的这种集合操作,归结起来有两个重要的:

Init(S):令集合S中的每个元素x,单独称为一个集合Sx。

Find(x):确定x属于那个子集合Si。

Merge(i, j):合并子集合Si和Sj。

这些操作可以有很多实现方法,例如用位向量、有序表等。

此外,还可以使用并查集

(1)将集合中的每个元素用结点表示,每个结点中含有一个指向其双亲的指针。
(2)约定根结点的成员做为子集合的类名。
根据上述规定,实现集合”并”(Merge)操作,只需要让一棵树的根指向另一棵即可。
而实现查找,就是依次向parent查找,直到到达该树的根。

下述是这种基础版本的并查集,其Find和Merge的时间复杂度分别为O(d)和O(1),d是树的深度。

并查集优化

(1)rank,秩的压缩,即总是把含孩子少的合并到孩子多的子树上。以减少不平衡树的产生。但是话说这个优化感觉有限。

(2)路径压缩。实际是记忆搜索的变种。如下:

上述优化后,查找和合并的时间复杂度都可以认为是常数级别。

 

 

Leave a Reply

Your email address will not be published.