集合及其表示等价类与并查集静态搜索表二叉搜索树最佳二叉

集合及其表示等价类与并查集静态搜索表二叉搜索树最佳二叉内容摘要：

输出包含这个对象的等价类。 } 给定集合 S = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }, 及如下等价对 : 0  4, 3  1, 6  10, 8  9, 7  4, 6  8, 3  5, 2  11, 11  0。 初始 {0},{1},{2},{3},{4},{5},{6},{7},{8},{9}, {10},{11} 0  4 {0,4},{1},{2},{3},{5},{6},{7},{8},{9},{10},{11} 3  1 {0,4}, {1,3},{2},{5},{6},{7},{8},{9},{10},{11} 6  10{0,4},{1,3},{2},{5},{6,10},{7},{8},{9},{11} 8  9 {0,4},{1,3},{2},{5},{6,10},{7},{8,9},{11} 7  4 {0,4,7},{1,3},{2},{5},{6,10},{8,9},{11} 6  8 {0,4,7},{1,3},{2},{5},{6,8,9,10},{11} 3  5 {0,4,7},{1,3,5},{2},{6,8,9,10},{11} 2  11{0,4,7},{1,3,5},{2,11},{6,8,9,10} 11  0{0,2,4,7,11},{1,3,5},{6,8,9,10} 并查集 (UnionFind Sets)  并查集支持以下三种操作：  Union (Root1, Root2) //并操作  Find (x) //搜索操作  UFSets (s) //构造函数  对于并查集来说，每个集合用一棵树表示。  为此，采用 树的双亲表示 作为集合存储表示。 集合元素的编号从 0到 n1。 其中 n 是最大元素个数。  在 双亲表示 中， 第 i 个数组元素代表包含集合元素 i 的树结点。 根结点的双亲为 1，表示集合中的元素个数。  在同一棵树上所有结点所代表的集合元素在同一个子集合中。  为此，需要有两个映射：  集合元素到存放该元素名的树结点间的对应；  集合名到表示该集合的树的根结点间的对应。  设 S1= {0, 6, 7, 8 }, S2= { 1, 4, 9 }, S3= { 2, 3, 5 } 集合名 指针 0 S1 1 S2 2 S3 0 4 2 7 6 8 1 9 3 5  为简化讨论 ， 忽略实际的集合名 ， 仅用表示集合的树的根来标识集合。  初始时 , 用构造函数 UFSets(s) 构造一个森林 , 每棵树只有一个结点 , 表示集合中各元素自成一个子集合。  用 Find(i) 寻找集合元素 i 的根。 如果有两个集合元素 i 和 j, Find(i) == Find(j), 表明这两个元素在同一个集合中 ，  如果两个集合元素 i 和 j 不在同一个集合中 ,可用 Union(i, j) 将它们合并到一个集合中。 下标 parent 1 1 1 1 1 1 1 1 1 1 0 1 2 3 4 5 6 7 8 9 S1 下标 parent 集合 S1, S2 和 S3 的双亲表示 4 4 3 2 3 2 0 0 0 4 0 1 2 3 4 5 6 7 8 9 0 7 6 8 4 1 9 2 3 5 S2 S3 S1  S2的可能的表示方法 下标 parent 集合 S1  S2 和 S3 的双亲表示 7 4 3 2 0 2 0 0 0 4 0 1 2 3 4 5 6 7 8 9 0 7 6 8 4 1 9 4 1 9 0 8 7 6 const int DefaultSize = 10。 class UFSets { //并查集类定义 private: int *parent。 //集合元素数组 int size。 //集合元素的数目 public: UFSets ( int s = DefaultSize )。 //构造函数 ~UFSets ( ) { delete [ ] parent。 } //析构函数 const UFSetsamp。 operator = (UFSetsamp。 right)。 //重载函数 ： 集合赋值 void Union ( int Root1, int Root2 )。 //基本例程 : 两个子集合合并 int Find ( int x )。 //基本例程 : 搜寻集合 x的根 void UnionByHeight ( int Root1, int Root2 )。 //改进例程 : 压缩高度的合并算法 }。 UFSets :: UFSets ( int s ) { //构造函数 size = s。 //集合元素个数 parent = new int [size]。 //双亲指针数组 for ( int i = 0。 i size。 i++ ) parent[i] = 1。 //每一个自成一个单元素集合 }  并查集操作的算法  查找 5 0 1 2 3 0 1 2 3 4 Find (4) Find (3) = 3 Find (2) =2 Find (1) = 1 Find (0) = 0 = 5 0 结束 int UFSets :: Find ( int x ) { if ( parent [x] 0 ) return x。 else return Find ( parent [x] )。 } 5 0 1 2 3 parent Parent[4] =3 Parent[3] =2 Parent[2] =1 Parent[1] =0 Parent[0] =5 0 1 2 3 4 void UFSets :: Union ( int Root1, int Root2 ) { //求两个不相交集合 Root1与 Root2的并 parent[Root1] += parent[Root2]。 parent[Root2] = Root1。 //将 Root2连接到 Root1下面 }  Find和 Union操作性能不好。 假设最初 n 个元素构成 n 棵树组成的森林， parent[i] = 1。 做处理 Union(n2, n1), …, Union(1, 2), Union(0, 1)后，将产生退化的树。  合并 1 1 1 1 1 0 2 3 4 3 5 0 3 2 1 3 3 4 1 3 3 2 2 0 2 3 1 4 Union(0,1) 2 3 4 1 4 2 1 2 3 4 Union(1,2) Union(2,3) Union(3,4)  执行一次 Union操作所需时间是 O(1)， n1次 Union操作所需时间是 O(n)。  若再执行 Find(0), Find(1), …, Find(n1), 若被搜索的元素为 i，完成 Find(i) 操作需要时间为 O(i)，完成 n 次搜索需要的总时间将达到  改进的方法  按树的结点个数合并；  按树的高度合并；  压缩元素的路径长度。 nini12OO )()( 按树结点个数合并 结点个数多的树的根结点作根。 1 1 1 1 1 0 1 2 3 4 1 1 0 7 2 5 6 5 2 2 2 3 3 2 0 1 3 4 5 6 2 3 3 0 2 0 5 6 2 3 1 4 Union(2, 0) void UFSets :: WeightedUnion ( int Root1, int Root2 ) { //按 Union的加权规则改进的算法 int temp = parent[Root1] + parent[Root2]。 if ( parent[Root2] parent[Root1] ) { parent[Root1] = Root2。 //Root2中结点数多 parent[Root2] = temp。 //Root1指向 Root2 } else { parent[Root2] = Root1。 //Root1中结点数多 parent[Root1] = temp。 //Root2指向 Root1 } }  按树高度合并  高度高的树的根结点作根。 0 0 0 0 0 0 1 2 3 4 0 0 0 2 2 5 6 2 1 2 2 3 3 2 0 1 3 4 5 6 2 3 3 0 2 0 5 6 2 3 1 4 Union(2, 0) Union操作的折叠规则  为进一步改进树的性能 ， 可以使用如下折叠规则来 “ 压缩路径 ”。 即： 如果 j 是从 i 到根的路径上的一个结点 ， 且 parent[j]  root[j]， 则把 parent[j] 置为 root[i]。 0 0 6 7 8 6 7 8 1 9 1 9 3 5 3 5 从 i = 5 压缩路径 int UFSets :: CollapsingFind ( int i ) { //使用折叠规则的搜索算法 for ( int j = i。 parent[j] = 0。 j = parent[j] )。 //让 j 循双亲指针走到根 while ( parent[i] != j ) { //换 parent[i] 到 j int temp = parent[i]。 parent[i] = j。 i = temp。 } return j。 } 搜索 (Search)的概念 静态搜索表  所谓 搜索 ，就是 在数据集合中寻找满足某 种条件的数据对象。  搜索的结果通常有两种可能：  搜索成功 ，即找到满足条件的数据对象 这时 ,作为结果 , 可报告该对象在结构中 的位置 , 还可给出该对象中的具体信息。  搜索不成功 ，或搜索失败。 作为结果 , 应报告一些信息 , 如失败标志、位置等。  通常称用于搜索的数据集合为 搜索结构 ，它是由 同一数据类型的对象 (或记录 )组成。  在每个对象中有若干属性，其中有一个属性，其值可惟一地标识这个对象。 称为关键码。 使用基于关键码的搜索，搜索结果应是惟一的。 但在实际应用时，搜索条件是多方面的，可以使用 基于属性的搜索方法，但搜索结果可能不惟一。  实施搜索时有两种不同的环境。 静态环境 ，搜索结构在插入和删除等操作的前后不发生改变。  静态搜索表 动态环境 ，为保持较高的搜索效率 , 搜索结构在执行插入和删除等操作的前后将自动进行调整，结构可能发生变化。  动态搜索表 静态搜索表 template class Type class dataList。 template class Type class Node { friend class dataListType。 pri。