这是数据结构类重新复习笔记的第 六 篇，同专题的其他文章可以移步：https://www.jianshu.com/nb/39256701

等价关系

在离散数学（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）

不相交集类的适合用于查找，有两个重要的操作：find和union：

• 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-by-height）

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

按照高度合并

存储数据的数组内容：

按照高度合并的存储数组

从find操作改进

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

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

一个不相交集类

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

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

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

转载请注明出处，本文永久更新链接：https://blogs.littlegenius.xin/2019/08/29/%E3%80%90%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E3%80%91%E5%85%AD%E4%B8%8D%E7%9B%B8%E4%BA%A4%E9%9B%86%E7%B1%BB/