第十二部分高级树结构教学课件.ppt
第十二章 高级树结构,任课教员：张 铭http:/,北京大学信息学院 版权所有，转载或翻印必究 Page 2,主要内容,12.1 Trie和Patricia 结构 12.2 改进的BST 最佳二叉搜索树 AVL树 伸展树 12.3 空间树结构 12.4 决策树和博弈树,北京大学信息学院 版权所有，转载或翻印必究 Page 3,12.1Trie结构和Patricia树,BST（二叉搜索树）不是一棵平衡的树，它的树结构与输入数据的顺序有很大的关系,北京大学信息学院 版权所有，转载或翻印必究 Page 4,对象空间(object space)分解,BST是一种组织上基于对象空间(object space)分解的数据结构空间分解是存储在树中的对象（关键码值）决定最简单的方法就是对对象（这里是关键码）的范围进行划分平均划分按照某种方式不平均划分,北京大学信息学院 版权所有，转载或翻印必究 Page 5,假设划分因子为2每次仅把当前范围分为两部分（对应于二叉树）在进行插入的时候，只要是小于结点的关键码的都在左子树中只要是大于结点的关键码的都在右子树中,北京大学信息学院 版权所有，转载或翻印必究 Page 6,关键码空间（key space）分解,不依赖于关键码的插入顺序树的深度受到关键码精度的影响最坏的情况下，深度等于存储关键码所需要的位数 例如，如果关键码是0到255之间的整数，那么关键码的精度就是8个二进制位。如果有两个关键码：10000010和10000011，它们的前面7位都是相同的所以直到第8次划分才能将这两个关键码分开这样的搜索树深度也为8，但这是最坏的情况,北京大学信息学院 版权所有，转载或翻印必究 Page 7,基于关键码范围的分解保证平衡吗？显然是不行的如果关键码的分布得很不均衡，将导致树的结构失衡 一种极端的情况，导致所有的关键码都小于根结点，那么以该结点为根的子树的右子树将没有任何的元素,北京大学信息学院 版权所有，转载或翻印必究 Page 8,Trie结构,基于关键码分解的数据结构，叫作Trie结构“trie”这个词来源于“retrieval”主要应用信息检索（information retrieval）用来存储英文字符串，尤其大规模的英文词典自然语言理解系统中经常用到,北京大学信息学院 版权所有，转载或翻印必究 Page 9,Trie结构的适用情况,Trie结构主要基于两个原则有一个固定的关键码集合 对于结点的分层标记 如果所有的元素都可以使用数字或者字母等来标记，那么就可以考虑使用Trie结构 例如，元素可以用0-9的数字来标记在根结点的地方，它分出10个子结点，分别标记0-9然后每个子结点又可以分出10个结点如此下去直到所有的元素都能够被区分开,北京大学信息学院 版权所有，转载或翻印必究 Page 10,Trie结构特点,与B+树一样，基于关键码空间分解的树结构，其内部结点仅作为占位符引导检索过程，数据纪录只存储在叶结点中 Huffman编码树(Huffman coding tree)也是一种二叉Trie树,北京大学信息学院 版权所有，转载或翻印必究 Page 11,Trie结构示意图,北京大学信息学院 版权所有，转载或翻印必究 Page 12,Trie结构 应用：“字符树”,存储字典里面的单词英文的单词是有26个字母组成的（简单起见，我们忽略大小写），英文字符树每一个内部结点都有26个子结点树的高度为最长字符串长度,北京大学信息学院 版权所有，转载或翻印必究 Page 13,英文字符树,一棵子树代表具有相同前缀的关键码的集合。例如“an”子树代表具有相同前缀an-的关键码集合and，ant,北京大学信息学院 版权所有，转载或翻印必究 Page 14,字符树的改进,由于单词可能不等长，所以更好的存储是其内部结点不存储单词信息，只有叶结点才存储单词信息,北京大学信息学院 版权所有，转载或翻印必究 Page 15,字符树的改进（续）,观察上图中的bad和bee两个单词，它们的父结点都只有一个儿子就是它们自己，也就是说，实际上它们在父结点的时候就已经被区分开了因为我们真正想做的是要检索每一个单词，不需要在已经能够区分每个单词的情况下继续进行分裂结点的动作,北京大学信息学院 版权所有，转载或翻印必究 Page 16,字符树的改进（续）,北京大学信息学院 版权所有，转载或翻印必究 Page 17,字符树中的检索,首先用待查关键码的第一个字符与树林的各个根的字符相比较 然后下一步的检索在前次比较相等的那棵树上进行其中，用待查关键码的第二个字符与选定的这棵树的根的各个子结点进行比较，接着再沿着前次比较相等的分支进行进一步的检索.直到进行到某一层，该层所有结点的字符都与待查关键码相应位置的字符不同，这说明此关键码在树目录里没有出现；若检索一直进行到树叶，那么就在树目录里找到了给定的关键码,北京大学信息学院 版权所有，转载或翻印必究 Page 18,Trie字符树的缺陷,Trie结构显然也不是平衡的在它存取英文单词的时候，显然t子树下的分支比z子树下的分支多很多（以t开头的单词比以z开头的单词多很多）而且，每次有26个分支因子使得树的结构过于庞大，给检索也带来了不便 字母在计算机中是以二进制ASCII码的形式存储的使用每个字母的二进制编码来代表这个字母关键码就只有编码0和1而不是a到z的26个字母二叉Trie树,北京大学信息学院 版权所有，转载或翻印必究 Page 19,Trie树的插入,Trie树的插入 首先根据插入纪录的关键码找到需要插入的结点位置 如果该结点是叶结点，那么就将为其分裂出两个子结点，分别存储这个纪录和以前的那个纪录 如果是内部结点，则在那个分支上应该是空的，所以直接为该分支建立一个新的叶结点即可,北京大学信息学院 版权所有，转载或翻印必究 Page 20,Trie树的删除,Trie树的删除根据插入纪录的关键码找到需要删除的结点位置 如果一个被删除结点的父结点没有其他的儿子，那么就需要合并 否则只需要将此分支设置为空即可,北京大学信息学院 版权所有，转载或翻印必究 Page 21,PATRICIA 结构,为了得到更加平衡的结构，D.Morrision发明了Trie结构的一种变体PATRICIA“Practical Algorithm To Retrieve Information Coded In Alphanumeric”它不是对整个关键码大小范围的划分而是根据关键码每一个二进制位的编码来划分因为每一位要么是0，要么是1，所以分支因子是2，生成的树是二叉树,北京大学信息学院 版权所有，转载或翻印必究 Page 22,PATRICIA 结构图,北京大学信息学院 版权所有，转载或翻印必究 Page 23,PATRICIA 结构图（续）,上图因为最大的数是63，用6位二进制表示即可每一个结点都有一个标号，表示它是在比较第几位，然后根据那一位是0还是1来划分左右两个子树标号为2的结点的右子树一定是编码形式为xx1xxx（x表示该位或0或1，标号为2说明比较第2位）在图中检索5的话，5的编码为000101 首先我们比较第0位，从而进入左子树然后在第1位仍然是0，还是进入左子树在第2位还是0，仍进入左子树第3位变成了1，从而进入右子树，就找到了位于叶结点的数字5,北京大学信息学院 版权所有，转载或翻印必究 Page 24,PATRICIA 结构图改进,观察PATRICIA的图发现有与Trie图类似的情况在区分2和5、41和45的时候，在第三个二进制位的比较是不能区别它们的 可以将它省略，得到一棵更为简洁的树,北京大学信息学院 版权所有，转载或翻印必究 Page 25,PATRICIA 结构图改进（续）,北京大学信息学院 版权所有，转载或翻印必究 Page 26,PATRICIA的特点,每个内部结点都代表一个位的比较，必然产生两个子结点所以它是一个满二叉树进行一次检索，最多只需要关键码位数次的比较即可,北京大学信息学院 版权所有，转载或翻印必究 Page 27,12.2二叉树结构的改进,平衡的二叉搜索树、伸展树和最佳二叉排序树，它们都是对二叉树的结构或者操作规则做部分的改进以使树保持在一种类似于平衡的状态，从而达到较好的效率,北京大学信息学院 版权所有，转载或翻印必究 Page 28,12.2.1最佳二叉搜索树,根据前面章节的二叉树介绍我们知道对应于关键码集合K:K=xal,wan,wil,zol,yo,xul,yum,wen,wim,zi,yon,xem,wul,zom的二叉排序树,北京大学信息学院 版权所有，转载或翻印必究 Page 29,二叉搜索树的多样性,同一个关键码集合，其关键码插入二叉搜索树的次序不同，就构成不同的二叉搜索树。包括n个关键码的集合中，关键码可以有n!种不同的排列法，因此可以构成n!个二叉搜索树(其中有相同的)可以用检索效率来衡量二叉搜索树,北京大学信息学院 版权所有，转载或翻印必究 Page 30,如果只计算不同的搜索树，则排列2，1，3的顺序插入关键码与按照排列2，3，1的顺序插入所构成的二叉搜索树完全相同 这种非前序排列的序列，总是可以找到与其相对应的一个合法前序排列这n!种排列中，只有 就是说n个结点可以构造 称为Catalan函数,北京大学信息学院 版权所有，转载或翻印必究 Page 31,扩充的二叉树,第4章讨论过扩充的二叉树的概念。扩充的二叉树是满二叉树，新增加的空树叶(以下称为外部结点)的个数等于原来二叉树的结点(以下称为内部结点)个数加1 在扩充的二叉搜索树里，关键码值最小的内部结点的左子女(外部结点)代表了值小于该内部结点的可能关键码的集合；关键码值最大的内部结点的右子女(外部结点)代表了值大于该内部结点的可能关键码的集合除此之外，每个外部结点代表其值处于原来二叉搜索树的两个相邻结点的关键码值之间的可能关键码的集合,北京大学信息学院 版权所有，转载或翻印必究 Page 32,路径长度,外部路径长度E定义为从扩充的二叉树的根到每个外部结点的路径长度之和。内部路径长度I定义为扩充的二叉树里从根到每个内部结点的路径长度之和,北京大学信息学院 版权所有，转载或翻印必究 Page 33,二叉搜索树里检索算法,在二叉搜索树里检索算法十分简单：首先用待查的关键码与二叉搜索树的根结点进行比较，若比较相等，则找到了要检索的关键码；若比较不等，具待查关键码值小于根结点的关键码值，则下一次与根的左子树的根比较；否则与根的右子树的根比较。如此递归地进行下去，直到某一次比较相等，检索成功；或一直比较到树叶都不相等，检索失败。,北京大学信息学院 版权所有，转载或翻印必究 Page 34,检索一个关键码的比较次数,在检索过程中，每进行一次比较，就进入下面一层。因此，对于成功的检索，比较的次数就是关键码所在的层数加1。对于不成功的检索，被检索的关键码属于哪个外部结点代表的可能关键码集合，比较次数就等于此外部结点的层数 在二叉搜索树里，检索一个关键码的平均比较次数为,北京大学信息学院 版权所有，转载或翻印必究 Page 35,参数意义,其中1i，是第i个内部结点的层数，是第i个外部结点的层数，pi是检索第i个内部结点所代表的关键码的频率qi是被检索的关键码属于第i个外部结点代表的可能关键码集合(即处于第i个和第i+1个内部结点之间)的频率。pi，qi也叫做结点的权,北京大学信息学院 版权所有，转载或翻印必究 Page 36,最佳二叉搜索树定义,是检索第i个内部结点所代表的关键码的概率，是被检索的关键码属于第i个外部结点代表的可能关键码集合的概率。我们把检索中平均比较次数最小，也就是ASL(n)最小的二叉搜索树称作最佳二叉搜索树,北京大学信息学院 版权所有，转载或翻印必究 Page 37,什么样的二叉搜索树是最佳的？,检索所有结点的概率都相等，即所有结点的权都相等：因此，要平均比较次数ASL(n)最小，就是要内部路径长度I最小,北京大学信息学院 版权所有，转载或翻印必究 Page 38,在一棵二叉树里，路径长度为0的结点仅有一个，路径长度为1的结点至多有两个，路径长度为2的结点至多有四个，等等。因此，有n个结点的二叉树其内部路径长度I至少等于序列:0，1，1，2，2，2，2，3，3，3，3，3，3，3，4，4，的前n项和。这个和写成:,北京大学信息学院 版权所有，转载或翻印必究 Page 39,可以证明：这种二叉树的特点是只有最下面的两层结点的度数可以小于2，其它结点度数必须等于2。在所有结点的权相等的情况下，这样的二叉搜索树是最佳二叉搜索树，对它进行检索的平均比较次数为这个ASL(n)是O(log2n)量级的,北京大学信息学院 版权所有，转载或翻印必究 Page 40,最佳二叉搜索树构造举例,首先将集合K里的关键码排序 wan，wen，wil，wim，wul，xal，xem，xul，yo，yon，yum，zi，zol，zom然后用二分法依次检索这些关键码，并把在检索中遇到的在二叉搜索树里还没有的关键码依次插入二叉搜索树中。首先检索序列中的第一个关键码wan，用二分法检索wan的过程中会依次遇到关键码xem，wil，wan，这就是最先插入二叉搜索树的三个关键码。,北京大学信息学院 版权所有，转载或翻印必究 Page 41,最佳二叉搜索树构造举例,然后检索序列中的第二个关键码wen，用二分法检索wen的过程中会依次遇到关键码xem，wil，wan，wen，其中只有 wen是二叉搜索树中还没有的，因此第四个插入到二叉搜索树中的关键码是wen。再检索序列中的第三个关键码wil，如此进行下去，直到所有的关键码都已插入到二叉搜索树中，这样可得到最佳二叉搜索树。,北京大学信息学院 版权所有，转载或翻印必究 Page 42,北京大学信息学院 版权所有，转载或翻印必究 Page 43,二叉搜索树的效率,反过来，如果关键码按值递增的顺序依次插入到二叉搜索树中，则将得到退化为线性的二叉搜索树平均比较次数为O(n)按任意的顺序把关键码插入到二叉搜索树中，它的检索效率如何呢？平均比较次数是接近最坏的情况O(n)呢，还是接近最好的情况O(1og2n)?可以证明，对n!种二叉搜索树进行平均，得到的平均检索次数仍是O(1og2n),北京大学信息学院 版权所有，转载或翻印必究 Page 44,检索各结点的概率不相等的情况,检索各结点的概率不相等的情况，即在具有不等权结点的二叉搜索树里进行检索。现在的问题是给了一个排好序的关键码集合keyl，key2，keyn，和权的集合p1，p2，pn，q0，q1，qn，要找使得ASL(n)为最小的最佳二叉排序树，也就是要找使得 为最小，上式也称为二叉排序树的开销,北京大学信息学院 版权所有，转载或翻印必究 Page 45,北京大学信息学院 版权所有，转载或翻印必究 Page 46,最佳二叉搜索树的构造方法,最佳二叉搜索树有个特点：它的任何子树都是最佳二叉搜索树。这一事实引导我们可以用这样的方法构造越来越大的最佳二叉搜索树：先构造包括一个结点的最佳二叉搜索树，再构造包括两个结点的最佳二叉搜索树，直到把所有的结点都包括进去。后来构造的较大的最佳二叉搜索树用前面构造的较小的最佳二叉搜索树作为其子树,北京大学信息学院 版权所有，转载或翻印必究 Page 47,设包括关键码keyi+1，keyi+2，keyj为内部结点(0ijn)，结点的权为(qi，pi+1，qi+1，pj，qj)的最佳二叉搜索树为t(i，j)，其根为r(i，j)，其花费为C(i，j)，其权的总和为W(i，j)=pi+1+pj+qi+qi+1+qj第一步构造包括一个结点的最佳二叉搜索树，就是找t(0，1)，t(1，2)，t(n-1，n)。,北京大学信息学院 版权所有，转载或翻印必究 Page 48,第二步构造包括两个结点的最佳二叉搜索树，就是找t(0，2)，t(1，3)，t(n-2，n)再构造包括三个，四个，结点的最佳二叉搜索树，直到最后构造t(0，n)如何构造最佳二叉搜索树t(i，j)呢?由最佳二叉搜索树的子树必是最佳二叉搜索树的原理可知：C(i，j)=W(i，j)+(C(i，k-1)+C(k，j),北京大学信息学院 版权所有，转载或翻印必究 Page 49,这个式子的意思是，用下列方法来找包括keyi+1，keyi+2，keyj为内部结点的最佳二叉搜索树t(i，j)：分别用keyi+1，keyi+2，keyj为根，考虑j-i棵二叉搜索树。以keyk为根的二叉搜索树其左子树包括keyi+1，keyk-1，而包括这些关键码为内部结点的最佳二又排序树t(i，k-1)已在前面的步骤确定，C(i，k-1)已求出，而以keyk为根的二叉搜索树其右子树包括keyk+l，keyk+2，keyj，以这些关键码为内部结点的最佳二叉搜索树t(k，j)也已在前面的步骤确定，C(k，j)已求出。,北京大学信息学院 版权所有，转载或翻印必究 Page 50,对于ikl找出使C(i，k-1)+C(k，j)为最小的那个k0，以keyk0为根，t(i，k0-1)为左子树，t(k0，j)为右子树的那个二叉搜索树就是所要求的t(i，j)。其花费 C(i，j)等于其根的左子树的花费C(i，k0-1)加上右子树花费C(k0，j)，再加上结点的总的权W(i，j)每一步构造出一棵最佳二叉搜索树t(i，j)就记下其根r(i，j)，花费C(i，j)，最后构造出t(0，n)，整个最佳二叉搜索树的结构就明确了,北京大学信息学院 版权所有，转载或翻印必究 Page 51,不等权结点的最佳二叉搜索树算法,void OptimalBST(int a,int b,int n,int cN+1N+1,int rN+1N+1,int wN+1N+1)for(int i=0;i=n;i+)for(int j=0;j=n;j+)/初始化 cij=0;rij=0;wij=0;,北京大学信息学院 版权所有，转载或翻印必究 Page 52,for(i=0;i=n;i+)wii=bi;/求出权和wi.jfor(int j=i+1;j=n;j+)wij=wij-1+aj+bj;/确定一个结点的最佳二叉排序树 for(int j=1;j=n;j+)cj-1j=wj-1j;rj-1j=j;,北京大学信息学院 版权所有，转载或翻印必究 Page 53,/确定d个结点的最佳二叉树 int m,k0,k;for(int d=2;d=n;d+)for(int j=d;j=n;j+)i=j-d;m=ci+1j;k0=i+1;for(k=i+2;k=j;k+),北京大学信息学院 版权所有，转载或翻印必究 Page 54,if(cik-1+ckjm)m=cik-1+ckj;k0=k;cij=wij+m;rij=k0;,北京大学信息学院 版权所有，转载或翻印必究 Page 55,构造过程,给出关键码集合及权的序列 计算次数为,北京大学信息学院 版权所有，转载或翻印必究 Page 56,北京大学信息学院 版权所有，转载或翻印必究 Page 57,北京大学信息学院 版权所有，转载或翻印必究 Page 58,北京大学信息学院 版权所有，转载或翻印必究 Page 59,动态规划（dynamic programming）,动态规划方法将问题分解为若干个子问题，分别求解子问题的解，然后由这些子问题的解得到原问题的解。动态规划算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质 最优子结构是指问题的最优解包含其子问题的最优解 重叠子问题是指在自顶向下的递归求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次,北京大学信息学院 版权所有，转载或翻印必究 Page 60,动态规划与分治策略,动态规划与分治策略有着明显的不同。分治策略要求子问题之间相互独立，可以根据最有子结构直接用递归法求解而动态规划方法所处理的子问题相互交叉。直接用递归法来求解具有重叠子问题性质的后一类问题时，常常要大量重复计算公共的子问题；而动态规划对每个子问题仅仅求解一次，并将结果填写到若干张表中，下次计算同一子问题时直接利用表中的结果。动态规划的具体形式虽然多种多样，但它们一般都具有“填表”这一基本模式。,北京大学信息学院 版权所有，转载或翻印必究 Page 61,动态规划的应用,动态规划方法通常由于解决优化问题。这一类问题往往具有多个可行解，每一个解对应一个值。我们希望找到其中一个具有最优值（最大值或最小值）的解，称为最优解（可能存在多个最优解具有同一个最优值）。,北京大学信息学院 版权所有，转载或翻印必究 Page 62,动态规划算法的步骤,设计一个动态规划算法的步骤如下：（1）刻画最优解的结构特征（2）递归定义最优值（3）以自底向上的方式计算出最优值（4）根据计算过程的信息构造一个最优解步骤（1）-（3）是动态规划方法求解最优值的基本步骤。如果需要求得最优解，则需要进一步记录计算过程的信息并执行步骤（4）。,北京大学信息学院 版权所有，转载或翻印必究 Page 63,动态规划算法求解例子,设计一个时间 的算法，找出由n个数组成的序列的最长单调递增子序列。将这个 的算法的优化为 的算法 设A和B是两个字符串。对字符串可以进行如下操作：（1）删除一个字符（2）插入一个字符（3）将一个字符替换为另一个字符利用以上三种操作可以将字符串A转换为字符串B。我们称这种转换所需要的最少的字符串操作次数为字符串A到B的编辑距离（Edit Distance），记为。设计一个算法，对任给的两个字符串A和B，计算出它们的编辑距离,北京大学信息学院 版权所有，转载或翻印必究 Page 64,12.2.2 平衡的二叉搜索树(AVL),BST受输入顺序影响最好O(log n)最坏O(n)怎样使得BST始终保持O(log n)级的平衡状态？Adelson-Velskii和Landis发明了AVL树一种平衡的二叉搜索树任何结点的左子树和右子树高度最多相差1,北京大学信息学院 版权所有，转载或翻印必究 Page 65,AVL树的性质,可以为空具有n个结点的AVL树，高度为O(log n)如果T是一棵AVL树那么它的左右子树TL、TR也是AVL树并且|hL-hR|1 hL、hR 是它的左右子树的高度,北京大学信息学院 版权所有，转载或翻印必究 Page 66,北京大学信息学院 版权所有，转载或翻印必究 Page 67,平衡因子,平衡因子，用bf(x)来表示结点x的平衡因子。它被定义为：bf(x)=x的右子树的高度 x的左子树的高度对于一个AVL树中的结点平衡因子之可能取值为0，1和-1,北京大学信息学院 版权所有，转载或翻印必究 Page 68,AVL树结点的插入,插入与BST一样新结点作叶结点需要调整相应子树的根结点变化大致有三类结点原来是平衡的，现在成为左重或右重的修改相应前驱结点的平衡因子结点原来是某一边重的，而现在成为平衡的了树的高度未变，不修改结点原来就是左重或右重的，而新结点又加到重的一边不平衡“危急结点”,北京大学信息学院 版权所有，转载或翻印必究 Page 69,恢复平衡,插入17后导致不平衡,重新调整为平衡结构,北京大学信息学院 版权所有，转载或翻印必究 Page 70,不平衡的情况,正常情况下，一个结点A的平衡因子只能是0，1，-1，而在非正常情况有下面四种可能 LL型：导致不平衡的结点为A的左子树的左结点，这时A的平衡因子为-2 LR型：导致不平衡的结点为A的左子树的右结点，这时A的平衡因子为-2 RL型：导致不平衡的结点为A的右子树的左结点，这时A的平衡因子为2 RR型：导致不平衡的结点为A的右子树的右结点，这时A的平衡因子为2,北京大学信息学院 版权所有，转载或翻印必究 Page 71,不平衡的图示,LL型 RR型的,北京大学信息学院 版权所有，转载或翻印必究 Page 72,不平衡情况总结,LL型和RR型是对称的，LR型和RL型是对称的 不平衡的结点一定在根结点与新加入结点之间的路径上 它的平衡因子只能是2或者-2如果是2，它在插入前的平衡因子是1如果是-2，它在插入前的平衡因子是-1,北京大学信息学院 版权所有，转载或翻印必究 Page 73,解决不平衡的方法旋转,我们可以使用一系列称为旋转(rotation)的局部操作解决这个问题 LL和RR的情况可以通过单旋转(single rotation)来解决 RL和LR的情况可以通过双旋转(double rotation)来解决 调整的整个过程称之为重构（restructuring）,北京大学信息学院 版权所有，转载或翻印必究 Page 74,单旋转,如果加入一个新结点后需要对根为结点a的子树进行单旋转，假设b为包含新加入结点的a的子女，c为包含新加入结点的b的子女单旋转，那么令b代替a成为新根，a和c作为其子结点；原来c的子树保持不变；原来b中c结点的兄弟子树，代替原b子树作为a的子树,北京大学信息学院 版权所有，转载或翻印必究 Page 75,单旋转示意图（LL型）,北京大学信息学院 版权所有，转载或翻印必究 Page 76,北京大学信息学院 版权所有，转载或翻印必究 Page 77,单旋转示意图（RR型）,RR型单旋转,北京大学信息学院 版权所有，转载或翻印必究 Page 78,双旋转,RL或者LR需要进行双旋转这两种情况是对称的我们只讨论 RL的情况LR是一样的,北京大学信息学院 版权所有，转载或翻印必究 Page 79,RL型双旋转第一步,北京大学信息学院 版权所有，转载或翻印必究 Page 80,RL型双旋转第二步,北京大学信息学院 版权所有，转载或翻印必究 Page 81,旋转运算的实质,以RR型图示为例，总共有7个部分三个结点：a、b、c四棵子树a的左子树T0b的左子树T1 c的左子树T2 和右子树T3加重的是c为根的子树，但是其结构其实没有变化因此，可以整体地看作b的右子树 目的：重新组成一个新的AVL结构 平衡保留了中序周游的性质T0 a T1 b T2 c T3,北京大学信息学院 版权所有，转载或翻印必究 Page 82,旋转运算的实质（续）,把树做任何一种旋转（RR、RL、LL、LR）新树保持了原来的中序周游顺序旋转处理中仅需改变少数指针而且新的子树高度为h+2，保持插入前子树的高度不变原来二叉树在a结点上面的其余部分（若还有的话）总是保持平衡的,北京大学信息学院 版权所有，转载或翻印必究 Page 83,template class avlNode/平衡二叉树结点类public:avlNode(T val);/构造函数avlNode(T val,avlNode*left,avlNode*right,int bf);void release();/删除以当前结点为根的左右子树avlNode*leftptr;/左右指针avlNode*rightptr;int add(avlNode*/码值,北京大学信息学院 版权所有，转载或翻印必究 Page 84,private:int bf;/平衡因子avlNode*removeLeftmostElement(avlNode*,北京大学信息学院 版权所有，转载或翻印必究 Page 85,template class avlTree/平衡二叉树类public:avlTree();/构造函数avlTree(const avlTree,北京大学信息学院 版权所有，转载或翻印必究 Page 86,插入算法,template int avlNode:add(avlNode*,北京大学信息学院 版权所有，转载或翻印必究 Page 87,return-bf;/bf=(0,+1)的情况，不需要调整树，只要修改bfelseif(rp-rightptr=NULL)rp-right=new avlNode(val);else if(rp-rightptr-add(rp-rightptr,val)=0)return 0;/插入后子树没有增高 if(rp-bf=1)/原来已经倾斜，需要做平衡处理 if(rp-rightptr-bf0)/插入在右侧，单旋转 rp=RR_singleRotation();else rp=RL_doubleRotation();/插入点在右侧.双旋转 return 0;return+bf;/bf=(0,-1)的情况，不需要调整树，只要修改bf,北京大学信息学院 版权所有，转载或翻印必究 Page 88,旋转的算法(LL),template avlNode*avlNode:LL_singleRotation()/以当前结点this(a)进行LL单旋转avlNode*b;b=leftptr;/得到当前结点this(a)的左子树leftptr=p-rightptr;/当前结点的左子树变为原子树的右子树bf=0;b-rightptr=this;/原子结点成为当前结点的父结点 if(b-bf=0)/如果是删除导致的旋转，则需要调整bf b-bf=1;else b-bf=0;return b;/返回新的子树根结点,北京大学信息学院 版权所有，转载或翻印必究 Page 89,旋转的算法(RR),template avlNode*avlNode:RR_singleRotation()/以当前结点this(a)进行RR单旋转avlNode*b;b=rightptr;/得到当前结点右儿子rightptr=b-leftptr;/当前结点的右儿子变为原其右儿子的左子女bf=0;b-leftptr=this;/原其右儿子变为当前结点的父亲 if(b-bf=0)/如果是删除导致的旋转，则需要调整bf b-bf=-1;else b-bf=0;return b;,北京大学信息学院 版权所有，转载或翻印必究 Page 90,旋转的算法(RL),template avlNode*avlNode:RL_doubleRotation()/以当前结点this(图11-24(d)中为a)进行LL单旋转avlNode*c,*b;b=rightptr;c=b-leftptr;b-leftptr=c-rightptr;/第一次旋转c,b位置互换，c的右子树变为b的左子树c-rightptr=b;bf=b-bf=0;if(c-bf=-1)b-bf=1;/因为c的右子树变为b的左子树if(c-bf=1)bf=-1;/所以根据原来的高度可以知道现在的平衡因子 rightptr=c-leftptr;/第二次旋转c和当前结点a互换 c-leftptr=this;c-bf=0;/旋转完c平衡return c;,北京大学信息学院 版权所有，转载或翻印必究 Page 91,旋转的算法(LR),template avlNode*avlNode:LR_doubleRotation()/以当前结点this(a)进行LR双旋转avlNode*c,*b;b=leftptr;c=b-rightptr;b-rightptr=c-leftptr;/第一次旋转b,c位置互换，c的左子树变为b的右子树c-leftptr=b;bf=b-bf=0;if(c-bf=-1)bf=1;/根据原来c的左子树的高度来判断当前if(c-bf=1)b-bf=-1;/b的平衡情况 leftptr=c-rightptr;/第二次旋转c和当前结点互换c-rightptr=this;c-bf=0;return c;,北京大学信息学院 版权所有，转载或翻印必究 Page 92,插入单词：cup，cop，copy，hit，hi，his和 hia后得到的AVL树,北京大学信息学院 版权所有，转载或翻印必究 Page 93,插入单词：cup，cop，copy，hit，hi，his和 hia后得到的AVL树,北京大学信息学院 版权所有，转载或翻印必究 Page 94,AVL树结点的删除,删除是插入的逆操作。从删除结点的意义上来说，AVL树的删除操作与BST一样 AVL树的删除是比较复杂过程，下面具体讨论一下删除的过程 由于情况较多，所以图示每种情况只列举了一种例子，其他都是类似的,北京大学信息学院 版权所有，转载或翻印必究 Page 95,AVL树结点的删除,具体删除过程请参考BST结点的删除如果被删除结点a没有子结点直接删除a；如果a有一个子结点用子结点的内容代替a的内容，然后删除子结点；如果a有两个子结点那么则要找到a在中序周游下的前驱结点b（b的右子树必定为空）用b的内容代替a，并且删除结点b（如果b的左子树不空，则该左子树代替代替原来b的位置）。,北京大学信息学院 版权所有，转载或翻印必究 Page 96,AVL结点删除后的调整,AVL树调整的需要删除结点后可能导致子树的高度以及平衡因子的变化沿着被删除结点到根结点的路径来调整这种变化需要改动平衡因子则修改之；如果发现不需要修改则不必继续向上回溯用一个布尔变量modified来记录之，其初值为TRUE当modified=FALSE时，回溯停止有以下三种情况,北京大学信息学院 版权所有，转载或翻印必究 Page 97,AVL树结点的删除过程2(续),第一种情况当前结点a平衡因子为0如果它的左子树或者右子树被缩短，则它的平衡因子该为1或者-1modified=FALSE因为这样的变化不会影响到上面的结点，调整可以结束,北京大学信息学院 版权所有，转载或翻印必究 Page 98,AVL树结点的删除情况1图示,北京大学信息学院 版权所有，转载或翻印必究 Page 99,AVL树结点的删除过程2(续),第二种情况是当前结点a平衡因子不为0，但是其较高的子树被缩短则其平衡因子修改为0modified=TRUE需要继续向上修改,北京大学信息学院 版权所有，转载或翻印必究 Page 100,AVL树结点的删除情况2图示,北京大学信息学院 版权所有，转载或翻印必究 Page 101,AVL树结点的删除过程2(续),第三种情况是当前结点a平衡因子不为0，且它的较低的子树被缩短结点a必然不再平衡，假设其较高子树的根结点为b，出现下面三种情况情况3.1：b的平衡因子为0单旋转modified=FALSE 情况3.2：b的平衡因子与a的平衡因子相同单旋转结点a、b平衡因子都变为0modified=TRUE,北京大学信息学院 版权所有，转载或翻印必究 Page 102,情况3.3：b和a的平衡因子相反双旋转，先围绕b旋转，再围绕a旋转新的根结点平衡因为为0其他结点应做相应的处理并且modified=TRUE,北京大学信息学院 版权所有，转载或翻印必究 Page 103,AVL树结点的删除情况3图示,北京大学信息学院 版权所有，转载或翻印必究 Page 104,AVL树结点的删除情况3图示,北京大学信息学院 版权所有，转载或翻印必究 Page 105,删除后的连续调整,从被删除的结点向上查找到其祖父结点然后开始单旋转或者双旋转操作 旋转次数为O(log n)连续调整调整可能会导致它祖先结点发生新的不平衡这样的调整操作要一直进行下去，可能传递到根结点为止,北京大学信息学院 版权所有，转载或翻印必究 Page 106,AVL树删除的例子,北京大学信息学院 版权所有，转载或翻印必究 Page 107,AVL树删除的例子,北京大学信息学院 版权所有，转载或翻印必究 Page 108,AVL树删除的例子,北京大学信息学院 版权所有，转载或翻印必究 Page 109,AVL树的高度,具有n个结点的AVL树的高度一定是O(log n)n个结点的AVL树的最大高度不超过Klog2 n这里K是一个小的常数 最接近于不平衡的AVL树 构造一系列AVL树T1，T2，T3，。其中Ti的高度是i每棵具有高度i的其它AVL树都比Ti的结点个数多或者说，每棵这样的树都是具有同样的结点数目的所有AVL树中最接近不平衡状态的，删除一个结点都会不平衡,北京大学信息学院 版权所有，转载或翻印必究 Page 110,北京大学信息学院 版权所有，转载或翻印必究 Page 111,高度的证明（推理）,可看出有下列关系成立：t(1)=2t(2)=4t(i)=t(i-1)+
