等价关系

在离散数学(Discrete Mathematics)中提到过等价关系(equivalence relation),等价关系是对于任意一对元素 (a,b),存在一个关系R满足以下三个属性:

  • 自反性:对于所有的元素a,a R a
  • 对称性:a R b == b R a
  • 传递性:若 a R b 且 b R c 则 a R c

比如空间中的相互平行的线就满足等价关系,线与自身平行、两条平行线相互平行,如果a平行于b,b平行于c,a也就平行于c,所以平行关系是等价关系。

一个集合S上的元素之间存在的等价关系是对集合S的一个划分,相互等价的元素可以划分到一个子集中,而没有等价关系的两个元素肯定不会被分到同一个子集中,所以按照等价关系划分可以将S划分为多个子集,每个子集中的元素都相互等价,这些子集是不相交的,而且他们的并正好是集合S。具有这种特性的集合可以视为一个不相交集类(The Disjoint Sets Class)

不相交集类的适合用于查找,有两个重要的操作:findunion

  • find:查找操作,find(x)是返回x所在的子集的名字
  • union:合并操作,如果我们发现两个元素a和b相互等价,但是他们没有在同一个子集中,那么很显然,a所在的子集和b所在的子集中的所有元素都相互等价,我们可以将其合并成一个新的子集

基本实现

如果不要求find操作返回任意特定的名字,而是要求当且仅当两个元素属于相同的子集时,则作用在这两个元素上的find操作能返回相同的明自。那么我就需要对集合S进行划分,并且每一个子集都有唯一的名字。

一种简单的实现方式时是哟个森林,森林中的树就是一个子集,节点就是元素,同一棵树上的所有节点就都属于这个子集,显然可以将子集的名字存储到树的根节点中。这种方式很简单,使用数组就可以实现。比如我们有一个8元素的集合,他们分别是0 1 2 3 4 5 6 7,最初始的时候就是每个节点都单独成树,根节点中存储-1来代表这个时根节点,然后使用union方法来合并集合。像下边这样(union(a,b)默认将b挂到a上):

初始的一个森林

一个不相交集类的基本实现
一个不相交集类的基本实现

进行union(4,5)操作:

一个不相交集类的基本实现
一个不相交集类的基本实现

进行union(6,7)操作:

一个不相交集类的基本实现
一个不相交集类的基本实现

进行union(4,6)操作:

一个不相交集类的基本实现
一个不相交集类的基本实现

最终的存储这个不相交集类的数组如下:

一个不相交集类的基本实现
一个不相交集类的基本实现

从union操作改进

按大小求并(union-by-size)

这个思想是打破随意将一个集合接到另一个集合上的做法,而是根据大小将树合并,即永远将小的集合挂到大的集合上,这种实现方式很简单,并且使得森林中树的结构都不会特别复杂,避免了最坏情况的发生,存储时,将树的根节点的内容存储为此时树的大小的负数,比如继续上边的不相交集类,进行union(3,4)操作:

依旧按照原来的union方式合并:

依照一般的union方式合并
依照一般的union方式合并

按照小树并大树的方式进行union合并:

按照大小合并
按照大小合并

按照大小合并后的存储数组:

按照大小合并的存储数组
按照大小合并的存储数组

按高度求并(union-by-height)

根据高度将树合并,即永远将矮的集合挂到高的集合上,存储时,将树的根节点的内容存储为此时树的高度的负数,比如继续上边的不相交集类,进行按照高度的union(3,4)操作会得到:

按照高度合并
按照高度合并

存储数据的数组内容:

按照高度合并的存储数组
按照高度合并的存储数组

从find操作改进

在对union进行改进后可以对find进行改进,find改进的一种典型方式是路径压缩(Pass Compression)。即在每一次find后,将find的数据到根节点的沿途的每个节点都挂到根节点上,从而对路径进行压缩,而下次查找同一个元素或者其同子集下的元素就会非常省时间。

例如一个不相交集类如下:

一个不相交集类
一个不相交集类

在这个不太好的结构上进行find(14)后进行路径压缩可以得到:

对这个不相交集类进行路径压缩
对这个不相交集类进行路径压缩

这样就使得整棵树的高度、一些数据的路径深度(12、13、14、15)都得到了降低。