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

上堂课要点回顾 森林与二叉树树的转换转换 l树转换为树转换为 二叉树树 l二叉树转换为树树转换为树 l森林转换为转换为 二叉树树 l二叉树转换为树转换为 森林 森林的遍历历 l先根深度优优先遍历历 l后根深度优优先遍历历 二叉树树的应应用 l哈夫曼树树与哈夫曼 编码编码 第 十二 次 课 阅读： 朱战立，第200-204页页 习题： 作业11 数据结构课程内容 二叉树 数据结构的应用 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，当且仅仅当(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。 l2、等价类类(equivalence classes)：设设R是定义义在非空 集合S上的一个的等价关系， 称 是x的等价类类。R可产产生集合S的唯一划分， 即可以按R将S划分为为若干不相交的子集S1，S2， ，这这些子集Si称为为S的R等价类类。简简言之，等价类类是 集合中相互等价的元素的最大子集合。 在一些应用问题中，给出各个元素之间 的联系，要求将这些元素分成几个集合 ，每个集合中的元素直接或间接有联系 。在这类问题中主要涉及的是对集合的 合并和查找，因此将这种集合称为并查 集。 例如：亲亲戚 或许许你并不知道，你的某个朋友是你的亲亲戚。他可能是你 的曾祖父的外公的女婿的外甥女的表姐的孙孙子。如果能得到 完整的家谱谱，判断两个人是否是亲亲戚应该应该 是可行的，但如 果两个人的最近公共祖先与他们们相隔好几代，使得家谱谱十分 庞庞大，那么检验亲检验亲 戚关系实实非人力所能及。在这这种情况下 ，最好的帮手是计计算机。 为为了将问题简问题简 化，你将得到一些亲亲戚关系的信息，如同 Xuebin和Grant是亲亲戚，Grant和Tension是亲亲戚等，从这这些 信息中，你可以推出Xuebin和Tension是亲亲戚。请请写一个程 序，对对于我们们的关于亲亲戚关系的提问问，以最快的速度给给出 答案。 设初始有一集合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 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 110,4,7,1,3,5,2,11,6,8,9,10 11 00,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型 lInitiate(S,n)：建立n个新集合，每个集合有唯一元 素。要求各集合不相交的 lFind(S,x)：返回x的等价类类名 lUnion(S,x,y)：如果Find(S,x)！=find(S,y)，则则把分 别别含有x和y的两个等价类类合并成到一个等价类类。 每一次union操作使得集合的个数减少1 算法性能参数 ln lFind操作的次数m lUnion操作的次数（至多n-1） 并查集实现方法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等价类 类名, union(x,y):把所有的 Find(x)改为为Find(y) 4 1 2 3 4 5 6 7 8 9 10 11 Union(0,4)：把所有的0改为为4 4 1 2 1 4 5 6 7 8 9 10 11 Union(3,1)：把所有的3改为为1 4 1 2 1 4 5 10 7 8 9 10 11 Union(6,10)：把所有的6改为为10 4 1 2 1 4 5 10 7 9 9 10 11 Union(8,9)：把所有的8改为为9 4 1 2 1 4 5 10 4 9 9 10 11 Union(7,4)：把所有的7改为为4 4 1 2 1 4 5 9 4 9 9 9 11 Union(6,8)：把所有的10改为为9 4 5 2 5 4 5 9 4 9 9 9 11 Union(3,5)：把所有的1改为为5 4 5 11 5 4 5 9 4 9 9 9 11 Union(2,11)：把所有的2改为为11 4 5 4 5 4 5 9 4 9 9 9 4 Union(11,0)：把所有的11改为为4 数组法算法分析 操作 时间时间 效率操作执执行次数 FindO(1)m UnionO(n)n-1 将所有元素合并到一个集合：O(m+n2) 并查集实现方法2：链表表示法 每个等价类用一个链表表示， 第一个结点作其代表，初始n个链表 (a) 两个集合的链链表表示 ，其中一个集合 cb,c,e,h，另一个集 合fd,f,g。链链表中每 个结结点包含一个集合 成员员、一个指向下一 个集合元素结结点的指 针针以及一个指向表中 第一个结结点的指针针。 每一个链链表都有头头指 针针和尾指针针，分别别指 向第一个和最后一个 元素结结点 (b) union(c,f)的结结果，代 表为为f。将第2个链链表 拼接在第一个链链表表 尾，原第2个链链表的 每个结结点都需更新指 向代表的指针针 链表法算法分析 操作 时间时间 效率操作执执行次数 FindO(1)m UnionO(n)n-1 将所有元素合并到一个集合：O(m+n2) 链表表示法的改进： 按秩合并启发式策略 假设设每个等价类类的链链表中增加表的长长度 信息 在执执行union操作时总时总 是把较较短的表拼 接到较长较长 的表上去，这这可以把结结点更新 的次数限制在O(log n)，因此Union操作 时间时间 效率O(logn) 改进后的链表法算法分析 操作 时间时间 效率操作执执行次数 FindO(1)m UnionO(logn)n-1 将所有元素合并到一个集合：O(m+nlogn) 并查集实现方法3：森林表示法 每一个等价类用一棵树表示，树中每个结点是集合 的一个成员，根是代表。如果两个结点在同一棵树 中，则认为它们在同一个等价类中 每个成员仅指向其父结点 Find操作实现：沿着双亲结点指针一直向上找直至 根结点 Union操作实现：将一棵树的根指向另一棵树的根 (a) 两个集合的树树表示， 其中一个集合 cb,c,e,h，另一个集 合fd,f,g。链链表中每 个结结点包含一个集合 成员员、一个指向双亲亲 结结点的指针针。 (b) union(c,f)的结结果，代 表为为f。 BCD E FG HI 序号 0 1 2 3 4 5 6 7 B -1 E 0 F 0 C -1 D -1 G 4 H 5 I 5 data parent 采用双亲表示法实现森林 例： 10个结结点A、B、C、D、E、F、G、H、J、K 和它们们的等价关系（A,B）、(C,K) 、(F,J) 、 (E, H) 、(D,G) 、(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(UFSTreeNode 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结结点置为为 rootj结结点的双亲亲*/ 森林法算法分析 操作 时间时间 效率操作执执行次数 FindO(n)m UnionO(1)n-1 将所有元素合并到一个集合：O(mn) 森林表示法的改进1： 按秩求并启发式策略 假设设每个等价类类的树树中增加树树中结结点个 数的信息 在执执行union操作时总时总 是把包含较较少结结 点的树树的根指向包含较较多结结点的树树的根 ，这这可以把树树的整体深度限制在(log n) 因此，Find操作的效率O(logn) 森林法改进1的算法分析 操作 时间时间 效率操作执执行次数 FindO(logn)m UnionO(1)n-1 将所有元素合并到一个集合：O(mlogn+n) 森林法改进1示例 使用按秩合并策略处处理等价对对（J,H）的结结果： 森林表示法的改进2： 路径压缩启发式策略 一种可以产生极浅树的聪明而简单的方法 在执行Find操作时将查找路径上的每个结 点都直接指向根结点。 路径压缩不改变结点的秩 使用路径压缩压缩 策略处处理等价对对（H,E）的结结果： 森林法改进2示例 森林法改进2的算法分析 操作 时间时间 效率操作执执行次数 FindO(log2+m/nn)m Unio