《数据结构 chapter 8(5) 树和二叉树 等价问题》由会员分享，可在线阅读，更多相关《数据结构 chapter 8(5) 树和二叉树 等价问题（34页珍藏版）》请在金锄头文库上搜索。
1、上堂课要点回顾,森林与二叉树的转换 树转换为二叉树 二叉树转换为树 森林转换为二叉树 二叉树转换为森林 森林的遍历 先根深度优先遍历 后根深度优先遍历,二叉树的应用 哈夫曼树与哈夫曼编码,第 十二 次 课,阅读：朱战立，第200-204页习题：作业11,数据结构课程内容,数据结构的应用,8.7 等价问题（并查集）,基本概念 1、等价关系(equivalence relation)：假定有一具有n个元素的非空集合S=1，2，n，另有一个具有r个关系的集合R=(i1,j1),(i2,j2),(ir,jr)，若R满足： 对所有的iS，有(i,i)R时，即关系是自反的 对所有的i，jS，当且仅当(i,
2、j)R时(j,i)R，即关系是对称的 对所有的i，j S，若(i,j)R且(j,k)R，则有(i,j)R，即关系是传递的 则称关系R是定义在S上的一个等价关系，其中，i1等价于j1，i2等价于j2，ir等价于jr。,2、等价类(equivalence classes)：设R是定义在非空集合S上的一个的等价关系，称 是x的等价类。R可产生集合S的唯一划分，即可以按R将S划分为若干不相交的子集S1，S2，这些子集Si称为S的R等价类。简言之，等价类是集合中相互等价的元素的最大子集合。,在一些应用问题中，给出各个元素之间的联系，要求将这些元素分成几个集合，每个集合中的元素直接或间接有联系。在这类问题
3、中主要涉及的是对集合的合并和查找，因此将这种集合称为并查集。,例如：亲戚 或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱，判断两个人是否是亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。在这种情况下，最好的帮手是计算机。 为了将问题简化，你将得到一些亲戚关系的信息，如同Xuebin和Grant是亲戚，Grant和Tension是亲戚等，从这些信息中，你可以推出Xuebin和Tension是亲戚。请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。,设初
4、始有一集合S=0,1,2,3,4,5,6,7,8,9,10,11，依次读若干事先定义的等价对04,31,610,89,74,68,35,211,110. 每次读入一个等价对后，把等价集合union起来，则每读入一个等价对后集合的状态是: 初始 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
5、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,ADT UnionFindSet 数据元素：seti=aj, i=0,1,n-1, j=0,1,ni-1 (n0, ni0)。其中ai0,1,2,n 结构： 逻辑操作：设S为UnionFindSet型 Initiate(S,n)：建立n个新集合，每个集合有唯一元素。要求各集合不相交的 Find(S,x)：返回x的等价类名 Union(S,x,y)：如果F
6、ind(S,x)！=find(S,y)，则把分别含有x和y的两个等价类合并成到一个等价类。每一次union操作使得集合的个数减少1,算法性能参数 n Find操作的次数m Union操作的次数（至多n-1）,并查集实现方法1：数组表示法 建立一大小为n的数组，其中每个元素是等价类名,数组法算法分析,将所有元素合并到一个集合：O(m+n2),并查集实现方法2：链表表示法 每个等价类用一个链表表示， 第一个结点作其代表，初始n个链表,两个集合的链表表示，其中一个集合cb,c,e,h，另一个集合fd,f,g。链表中每个结点包含一个集合成员、一个指向下一个集合元素结点的指针以及一个指向表中第一个结点的
7、指针。每一个链表都有头指针和尾指针，分别指向第一个和最后一个元素结点 (b) union(c,f)的结果，代表为f。将第2个链表拼接在第一个链表表尾，原第2个链表的每个结点都需更新指向代表的指针,链表法算法分析,将所有元素合并到一个集合：O(m+n2),链表表示法的改进： 按秩合并启发式策略,假设每个等价类的链表中增加表的长度信息 在执行union操作时总是把较短的表拼接到较长的表上去，这可以把结点更新的次数限制在O(log n)，因此Union操作时间效率O(logn),改进后的链表法算法分析,将所有元素合并到一个集合：O(m+nlogn),并查集实现方法3：森林表示法 每一个等价类用一棵树
8、表示，树中每个结点是集合的一个成员，根是代表。如果两个结点在同一棵树中，则认为它们在同一个等价类中 每个成员仅指向其父结点Find操作实现：沿着双亲结点指针一直向上找直至根结点 Union操作实现：将一棵树的根指向另一棵树的根,两个集合的树表示，其中一个集合cb,c,e,h，另一个集合fd,f,g。链表中每个结点包含一个集合成员、一个指向双亲结点的指针。 (b) union(c,f)的结果，代表为f。,B,C,D,E,F,G,H,I,采用双亲表示法实现森林例：,10个结点A、B、C、D、E、F、G、H、J、K和它们的等价关系（A,B）、(C,K) 、(F,J) 、(E, H) 、(D,G) 、
9、(A, K) 、(G, E) 、(H,J) 初始状态：,森林表示法示例,对（A,B）、(C,K) 、(F, J) 、(E,H) 、(D,G)这5个等价对的处理结果,森林表示法示例,对两个等价对（A, K）和（G, E ）的处理结果：,森林表示法示例,并查集类型定义 #define MaxTreeNode 20 typedef struct int data;int parent;/双亲结点在数组的下标，根的parent为-1 UFSTreeNode; UFSTreeNode ForestMaxTreeNode;/*存储森林结点的数组*/,【并查集初始化算法】,void Initiate(UFS
10、TreeNode F ,int n) /*初始化并查集，并查集(森林)中最初有n个集合(树)，每个集合只有一个元素*/ int i;for(i=0;i=0)i=Fi.parent;return i; ,【并查集合并算法】,void Union(UFSTreeNode F ,int i, int j) /*合并，将根为j的树并到根为i的树上，即结点j的双亲指向结点i*/ int rooti, rootj;rooti=Find(F,i); /找到结点i的根rootj=Find(F,j); /找到结点j的根if (rooti!=rootj) Frootj.parent=rooti;/*将rooti结
11、点置为rootj结点的双亲*/ ,森林法算法分析,将所有元素合并到一个集合：O(mn),森林表示法的改进1： 按秩求并启发式策略,假设每个等价类的树中增加树中结点个数的信息 在执行union操作时总是把包含较少结点的树的根指向包含较多结点的树的根，这可以把树的整体深度限制在(log n) 因此，Find操作的效率O(logn),森林法改进1的算法分析,将所有元素合并到一个集合：O(mlogn+n),森林法改进1示例,使用按秩合并策略处理等价对（J,H）的结果：,森林表示法的改进2： 路径压缩启发式策略,一种可以产生极浅树的聪明而简单的方法 在执行Find操作时将查找路径上的每个结点都直接指向根结点。 路径压缩不改变结点的秩,使用路径压缩策略处理等价对（H,E）的结果：,森林法改进2示例,森林法改进2的算法分析,将所有元素合并到一个集合：O(n+mlog2+m/nn),森林法改进1+改进2的算法分析,将所有元素合并到一个集合：O(m+n),作业11,算法设计题 1、实现FindPathCompress（）函数功能，该函数在查找的同时实现路径压缩，将深层结点移近根结点。 2、实现UnionRank（）函数功能，该函数实现按秩进行合并的算法，其中的查找操作调用第一步的函数。,
