数据结构chapter树和二叉树等价问题.pptx

《数据结构chapter树和二叉树等价问题.pptx》由会员分享，可在线阅读，更多相关《数据结构chapter树和二叉树等价问题.pptx（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 十二 次 课阅读：朱战立，第200-204页习题：作业11第1页/共34页数据结构课程内容二叉树二叉树数据结构的应用数据结构的应用第2页/共34页8.7 8.7 等价问题（并查集）等价问题（并查集）基本概念基本概念l1、等价关系等价关系(equivalence relation)：假定有一具有：假定有一具有n个元素的非空集合个元素的非空集合S=1，2，n，另有一个具有，另有一个具有r个关系的集合个关系的集合R=(i1,j1),(i2,j2),(ir,jr)，若，若R满足：满足：l对所有的对所有的iS，有，有(i,i)R时，即关系是自反的时，即关系是自反的l对所有的对所有的i，jS，当且仅当

2、，当且仅当(i,j)R时时(j,i)R，即，即关系是对称的关系是对称的l对所有的对所有的i，j S，若，若(i,j)R且且(j,k)R，则有，则有(i,j)R，即关系是传递的，即关系是传递的则称关系则称关系R是定义在是定义在S上的一个上的一个等价关系等价关系，其中，其中，i1等等价于价于j1，i2等价于等价于j2，ir等价于等价于jr。第3页/共34页l2、等价类(equivalence classes)：设R是定义在非空集合S上的一个的等价关系，称 是x的等价类。R可产生集合S的唯一划分，即可以按R将S划分为若干不相交的子集S1，S2，这些子集Si称为S的R等价类。简言之，等价类是集合中相互

3、等价的元素的最大子集合。第4页/共34页在一些应用问题中，给出各个元素之间的联系，要求将这些元素分成几个集合，每个集合中的元素直接或间接有联系。在这类问题中主要涉及的是对集合的合并和查找，因此将这种集合称为并查集。第5页/共34页例如：亲戚 或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱，判断两个人是否是亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。在这种情况下，最好的帮手是计算机。为了将问题简化，你将得到一些亲戚关系的信息，如同Xuebin和Grant是亲戚，G

4、rant和Tension是亲戚等，从这些信息中，你可以推出Xuebin和Tension是亲戚。请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。第6页/共34页设初始有一集合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.每次读入一个等价对后，把等价集合union起来，则每读入一个等价对后集合的状态是:初始0,1,2,3,4,5,6,7,8,9,10,110 4 0,4,1,2,3,5,6,7,8,9,10,113 1 0,4,1,3,2,5,6,7,8,9,10,1

5、16 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,117 4 0,4,7,1,3,2,5,6,10,8,9,116 8 0,4,7,1,3,2,5,6,8,9,10,113 5 0,4,7,1,3,5,2,6,8,9,10,112 11 0,4,7,1,3,5,2,11,6,8,9,1011 0 0,2,4,7,11,1,3,5,6,8,9,10第7页/共34页ADT UnionFindSet数据元素：seti=aj,i=0,1,n-1,j=0,1,ni-1(n0,ni0)。其中ai0,1,2,n结构：逻辑操作：设S为Unio

6、nFindSet型Initiate(S,n)：建立n个新集合，每个集合有唯一元素。要求各集合不相交的Find(S,x)：返回x的等价类名Union(S,x,y)：如果Find(S,x)！=find(S,y)，则把分别含有x和y的两个等价类合并成到一个等价类。每一次union操作使得集合的个数减少1第8页/共34页算法性能参数nFind操作的次数mUnion操作的次数（至多n-1）第9页/共34页并查集实现方法1：数组表示法建立一大小为n的数组，其中每个元素是等价类名0 1 2 3 4 5 6 7 8 9 10 11下标下标0 1 2 3 4 5 6 7 8 9 10 11等价类名等价类名,un

7、ion(x,y):把所有的把所有的Find(x)改为改为Find(y)4 1 2 3 4 5 6 7 8 9 10 11 Union(0,4)：把所有的把所有的0改为改为44 1 2 1 4 5 6 7 8 9 10 11 Union(3,1)：把所有的把所有的3改为改为14 1 2 1 4 5 10 7 8 9 10 11 Union(6,10)：把所有的把所有的6改为改为104 1 2 1 4 5 10 7 9 9 10 11 Union(8,9)：把所有的把所有的8改为改为94 1 2 1 4 5 10 4 9 9 10 11 Union(7,4)：把所有的把所有的7改为改为44 1 2

8、 1 4 5 9 4 9 9 9 11 Union(6,8)：把所有的把所有的10改为改为94 5 2 5 4 5 9 4 9 9 9 11 Union(3,5)：把所有的把所有的1改为改为54 5 11 5 4 5 9 4 9 9 9 11 Union(2,11)：把所有的把所有的2改为改为114 5 4 5 4 5 9 4 9 9 9 4 Union(11,0)：把所有的把所有的11改为改为4第10页/共34页数组法算法分析操作操作 时间效率时间效率 操作执行次数操作执行次数FindO(1)mUnionO(n)n-1将所有元素合并到一个集合：将所有元素合并到一个集合：O(m+n2)第11页

9、/共34页并查集实现方法2：链表表示法每个等价类用一个链表表示，第一个结点作其代表，初始n个链表(a)两个集合的链表表示，其中一个集合cb,c,e,h，另一个集合fd,f,g。链表中每个结点包含一个集合成员、一个指向下一个集合元素结点的指针以及一个指向表中第一个结点的指针。每一个链表都有头指针和尾指针，分别指向第一个和最后一个元素结点(b)union(c,f)的结果，代表为f。将第2个链表拼接在第一个链表表尾，原第2个链表的每个结点都需更新指向代表的指针第12页/共34页链表法算法分析操作操作 时间效率时间效率 操作执行次数操作执行次数FindO(1)mUnionO(n)n-1将所有元素合并到

10、一个集合：将所有元素合并到一个集合：O(m+n2)第13页/共34页链表表示法的改进：按秩合并启发式策略假设每个等价类的链表中增加表的长度信息在执行union操作时总是把较短的表拼接到较长的表上去，这可以把结点更新的次数限制在O(log n)，因此Union操作时间效率O(logn)第14页/共34页改进后的链表法算法分析操作操作 时间效率时间效率 操作执行次数操作执行次数FindO(1)mUnionO(logn)n-1将所有元素合并到一个集合：将所有元素合并到一个集合：O(m+nlogn)第15页/共34页并查集实现方法3：森林表示法每一个等价类用一棵树表示，树中每个结点是集合的一个成员，根

11、是代表。如果两个结点在同一棵树中，则认为它们在同一个等价类中每个成员仅指向其父结点Find操作实现：沿着双亲结点指针一直向上找直至根结点Union操作实现：将一棵树的根指向另一棵树的根(a)两个集合的树表示，其中一个集合cb,c,e,h，另一个集合fd,f,g。链表中每个结点包含一个集合成员、一个指向双亲结点的指针。(b)union(c,f)的结果，代表为f。第16页/共34页BCDEFGHI序号序号01234567 B -1 E 0 F 0 C -1 D -1 G 4 H 5 I 5 data parent采用双亲表示法实现森林例：第17页/共34页10个结点A、B、C、D、E、F、G、H、

12、J、K和它们的等价关系（A,B）、(C,K)、(F,J)、(E,H)、(D,G)、(A,K)、(G,E)、(H,J)初始状态：森林表示法示例 第18页/共34页对（对（A,B）、）、(C,K)、(F,J)、(E,H)、(D,G)这这5个个等价对的处理结果等价对的处理结果森林表示法示例 第19页/共34页对两个等价对（对两个等价对（A,K）和（）和（G,E）的处理结果：）的处理结果：森林表示法示例 第20页/共34页并查集类型定义#define MaxTreeNode 20typedef struct int data;int parent;/双亲结点在数组的下标，根的parent为-1 UFS

13、TreeNode;UFSTreeNode ForestMaxTreeNode;/*存储森林结点的数组*/第21页/共34页【并查集初始化算法】void Initiate(UFSTreeNode F,int n)/*初始化并查集，并查集(森林)中最初有n个集合(树)，每个集合只有一个元素*/int i;for(i=0;i=0)i=Fi.parent;return i;第23页/共34页【并查集合并算法】void Union(UFSTreeNode F,int i,int j)/*合并，将根为j的树并到根为i的树上，即结点j的双亲指向结点i*/int rooti,rootj;rooti=Find(

14、F,i);/找到结点i的根rootj=Find(F,j);/找到结点j的根if(rooti!=rootj)Frootj.parent=rooti;/*将rooti结点置为rootj结点的双亲*第24页/共34页森林法算法分析操作操作 时间效率时间效率 操作执行次数操作执行次数FindO(n)mUnionO(1)n-1将所有元素合并到一个集合：将所有元素合并到一个集合：O(mn)第25页/共34页森林表示法的改进1：按秩求并启发式策略假设每个等价类的树中增加树中结点个数的信息在执行union操作时总是把包含较少结点的树的根指向包含较多结点的树的根，这可以把树的整体深度限制在(log n)因此，F

15、ind操作的效率O(logn)第26页/共34页森林法改进1的算法分析操作操作 时间效率时间效率 操作执行次数操作执行次数FindO(logn)mUnionO(1)n-1将所有元素合并到一个集合：将所有元素合并到一个集合：O(mlogn+n)第27页/共34页森林法改进1示例 使用按秩合并策略处理等价对（使用按秩合并策略处理等价对（J,H）的结果：）的结果：第28页/共34页森林表示法的改进2：路径压缩启发式策略一种可以产生极浅树的聪明而简单的方法在执行Find操作时将查找路径上的每个结点都直接指向根结点。路径压缩不改变结点的秩第29页/共34页使用路径压缩策略处理等价对（使用路径压缩策略处理

16、等价对（H,E）的结果：）的结果：森林法改进2示例 第30页/共34页森林法改进2的算法分析操作操作时间效率时间效率操作执行次数操作执行次数FindO(log2+m/nn)mUnionO(1)n-1将所有元素合并到一个集合：将所有元素合并到一个集合：O(n+mlog2+m/nn)第31页/共34页森林法改进1+改进2的算法分析操作操作时间效率时间效率操作执行次数操作执行次数FindO(l)mUnionO(1)n-1将所有元素合并到一个集合：将所有元素合并到一个集合：O(m+n)第32页/共34页作业11算法设计题1、实现FindPathCompress（）函数功能，该函数在查找的同时实现路径压缩，将深层结点移近根结点。2、实现UnionRank（）函数功能，该函数实现按秩进行合并的算法，其中的查找操作调用第一步的函数。第33页/共34页感谢您的观看！第34页/共34页