这一章介绍解决等价问题的一种有效数据结构。实现简单，也非常快，每种操作只需要常数平均时间。
等价关系 (equivalence relation)
若对于每一对元素(a,b),a,b∈S, a R b或者为true或者为false，则称在集合S上定义关系R。如果a R b为true，我们说a和b有关系。
等价关系是满足下列三个性质的关系R：
- 自反性：对于所有的a∈S，
a R a - 对称性：
a R b当且仅当b R a - 传递性：若
a R b且b R c则a R c
元素a∈S的等价类(equivalence class)是S的子集，它包含所有与a有（等价）关系的元素。注意，等价类形成对S的一个划分：S的每一个成员恰好出现在一个等价类中。为确定是否a~b，我们只需验证a和b是否都在同一个等价类中。
输入数据最初是N个集合(collection)的类，每个集合含有一个元素。初始的描述是所有的关系均为false（自反的关系除外）。每个集合都有一个不同的元素，从而Si∩Sj=⊙，称为不相交(disjoint)
基本操作有两种，称为求并/查找(union/find)算法。
灵巧求并算法
直观的union操作相当随意，它简单地通过使第二棵树成为第一棵树的子树而完成合并。对其进行简单改进，使得总是较小的树成为较大的树的子树，称为按大小求并(union by size)，它保证树的深度最大是O(logN)。
连续M次操作平均需要O(M)时间。
另一种方法是按高度求并(union by height)，它同样保证树的深度最大是O(logN)。做法是使浅的树成为深的树的子树。
一个应用
应用求并/查找数据结构的一个例子是迷宫的生成。初始化时所有格子都在自己的等价类中，之后不断合并，最终生成迷宫。