《第十二部分高级树结构教学课件.ppt》由会员分享，可在线阅读，更多相关《第十二部分高级树结构教学课件.ppt（232页珍藏版）》请在三一文库上搜索。
1、第十二章 高级树结构,任课教员：张 铭 http:/ 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有，转载或翻印必究,北京大学信息学院 版权所有，转载或翻印必究 Page 2,主要内容,12.1 Trie和Patricia 结构 12.2 改进的BST 最佳二叉搜索树 AVL树 伸展树 12.3 空间树结构 12.4 决策树和博弈树,北京大学信息学院 版权所有，转载或翻印必究 Page 3,12.1Trie结构和Patricia树,BST（二叉搜索树）不是一棵平衡的树，它的树结构与输入数据的顺序有很大的关系,北京大学信息学院 版权所有，转载或翻印必究 Page 4,对象空间( o
2、bject space )分解,BST是一种组织上基于对象空间( object space )分解的数据结构 空间分解是存储在树中的对象（关键码值）决定 最简单的方法就是对对象（这里是关键码）的范围进行划分 平均划分 按照某种方式不平均划分,北京大学信息学院 版权所有，转载或翻印必究 Page 5,假设划分因子为2 每次仅把当前范围分为两部分（对应于二叉树） 在进行插入的时候，只要是小于结点的关键码的都在左子树中 只要是大于结点的关键码的都在右子树中,北京大学信息学院 版权所有，转载或翻印必究 Page 6,关键码空间（key space）分解,不依赖于关键码的插入顺序 树的深度受到关键码精度
3、的影响 最坏的情况下，深度等于存储关键码所需要的位数 例如，如果关键码是0到255之间的整数，那么关键码的精度就是8个二进制位。 如果有两个关键码：10000010和10000011，它们的前面7位都是相同的 所以直到第8次划分才能将这两个关键码分开 这样的搜索树深度也为8，但这是最坏的情况,北京大学信息学院 版权所有，转载或翻印必究 Page 7,基于关键码范围的分解 保证平衡吗？ 显然是不行的 如果关键码的分布得很不均衡，将导致树的结构失衡 一种极端的情况，导致所有的关键码都小于根结点，那么以该结点为根的子树的右子树将没有任何的元素,北京大学信息学院 版权所有，转载或翻印必究 Page 8
4、,Trie结构,基于关键码分解的数据结构，叫作Trie结构 “trie”这个词来源于“retrieval” 主要应用 信息检索（information retrieval） 用来存储英文字符串，尤其大规模的英文词典 自然语言理解系统中经常用到,北京大学信息学院 版权所有，转载或翻印必究 Page 9,Trie结构的适用情况,Trie结构主要基于两个原则 有一个固定的关键码集合 对于结点的分层标记 如果所有的元素都可以使用数字或者字母等来标记，那么就可以考虑使用Trie结构 例如，元素可以用0-9的数字来标记 在根结点的地方，它分出10个子结点，分别标记0-9 然后每个子结点又可以分出10个结点
5、 如此下去直到所有的元素都能够被区分开,北京大学信息学院 版权所有，转载或翻印必究 Page 10,Trie结构特点,与B+树一样，基于关键码空间分解的树结构，其内部结点仅作为占位符引导检索过程，数据纪录只存储在叶结点中 Huffman编码树( Huffman coding tree )也是一种二叉Trie树,北京大学信息学院 版权所有，转载或翻印必究 Page 11,Trie结构示意图,北京大学信息学院 版权所有，转载或翻印必究 Page 12,Trie结构 应用：“字符树”,存储字典里面的单词 英文的单词是有26个字母组成的（简单起见，我们忽略大小写）， 英文字符树每一个内部结点都有26个
6、子结点 树的高度为最长字符串长度,北京大学信息学院 版权所有，转载或翻印必究 Page 13,英文字符树,一棵子树代表具有相同前缀的关键码的集合。例如“an”子树代表具有相同前缀an-的关键码集合and，ant,北京大学信息学院 版权所有，转载或翻印必究 Page 14,字符树的改进,由于单词可能不等长 ，所以更好的存储是其内部结点不存储单词信息，只有叶结点才存储单词信息,北京大学信息学院 版权所有，转载或翻印必究 Page 15,字符树的改进（续）,观察上图中的bad和bee两个单词，它们的父结点都只有一个儿子就是它们自己，也就是说，实际上它们在父结点的时候就已经被区分开了 因为我们真正想做
7、的是要检索每一个单词，不需要在已经能够区分每个单词的情况下继续进行分裂结点的动作,北京大学信息学院 版权所有，转载或翻印必究 Page 16,字符树的改进（续）,北京大学信息学院 版权所有，转载或翻印必究 Page 17,字符树中的检索,首先用待查关键码的第一个字符与树林的各个根的字符相比较 然后下一步的检索在前次比较相等的那棵树上进行其中，用待查关键码的第二个字符与选定的这棵树的根的各个子结点进行比较， 接着再沿着前次比较相等的分支进行进一步的检索 . 直到进行到某一层，该层所有结点的字符都与待查关键码相应位置的字符不同，这说明此关键码在树目录里没有出现； 若检索一直进行到树叶，那么就在树目
8、录里找到了给定的关键码,北京大学信息学院 版权所有，转载或翻印必究 Page 18,Trie字符树的缺陷,Trie结构显然也不是平衡的 在它存取英文单词的时候，显然t子树下的分支比z子树下的分支多很多（以t开头的单词比以z开头的单词多很多） 而且，每次有26个分支因子使得树的结构过于庞大，给检索也带来了不便 字母在计算机中是以二进制ASCII码的形式存储的 使用每个字母的二进制编码来代表这个字母 关键码就只有编码0和1 而不是a到z的26个字母 二叉Trie树,北京大学信息学院 版权所有，转载或翻印必究 Page 19,Trie树的插入,Trie树的插入 首先根据插入纪录的关键码找到需要插入的
9、结点位置 如果该结点是叶结点，那么就将为其分裂出两个子结点，分别存储这个纪录和以前的那个纪录 如果是内部结点，则在那个分支上应该是空的，所以直接为该分支建立一个新的叶结点即可,北京大学信息学院 版权所有，转载或翻印必究 Page 20,Trie树的删除,Trie树的删除 根据插入纪录的关键码找到需要删除的结点位置 如果一个被删除结点的父结点没有其他的儿子，那么就需要合并 否则只需要将此分支设置为空即可,北京大学信息学院 版权所有，转载或翻印必究 Page 21,PATRICIA 结构,为了得到更加平衡的结构，D.Morrision发明了Trie结构的一种变体PATRICIA “Practica
10、l Algorithm To Retrieve Information Coded In Alphanumeric” 它不是对整个关键码大小范围的划分 而是根据关键码每一个二进制位的编码来划分 因为每一位要么是0，要么是1，所以分支因子是2， 生成的树是二叉树,北京大学信息学院 版权所有，转载或翻印必究 Page 22,PATRICIA 结构图,北京大学信息学院 版权所有，转载或翻印必究 Page 23,PATRICIA 结构图（续）,上图因为最大的数是63，用6位二进制表示即可 每一个结点都有一个标号，表示它是在比较第几位，然后根据那一位是0还是1来划分左右两个子树 标号为2的结点的右子树一
11、定是编码形式为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,PAT
12、RICIA 结构图改进（续）,北京大学信息学院 版权所有，转载或翻印必究 Page 26,PATRICIA的特点,每个内部结点都代表一个位的比较，必然产生两个子结点 所以它是一个满二叉树 进行一次检索，最多只需要关键码位数次的比较即可,北京大学信息学院 版权所有，转载或翻印必究 Page 27,12.2二叉树结构的改进,平衡的二叉搜索树、伸展树和最佳二叉排序树，它们都是对二叉树的结构或者操作规则做部分的改进以使树保持在一种类似于平衡的状态，从而达到较好的效率,北京大学信息学院 版权所有，转载或翻印必究 Page 28,12.2.1最佳二叉搜索树,根据前面章节的二叉树介绍我们知道对应于关键码集合
13、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的顺序插入所构成的
14、二叉搜索树完全相同 这种非前序排列的序列，总是可以找到与其相对应的一个合法前序排列 这n!种排列中， 只有 就是说n个结点可以构造 称为Catalan函数,北京大学信息学院 版权所有，转载或翻印必究 Page 31,扩充的二叉树,第4章讨论过扩充的二叉树的概念。扩充的二叉树是满二叉树，新增加的空树叶(以下称为外部结点)的个数等于原来二叉树的结点(以下称为内部结点)个数加1 在扩充的二叉搜索树里，关键码值最小的内部结点的左子女(外部结点)代表了值小于该内部结点的可能关键码的集合；关键码值最大的内部结点的右子女(外部结点)代表了值大于该内部结点的可能关键码的集合 除此之外，每个外部结点代表其值处于
15、原来二叉搜索树的两个相邻结点的关键码值之间的可能关键码的集合,北京大学信息学院 版权所有，转载或翻印必究 Page 32,路径长度,外部路径长度E定义为从扩充的二叉树的根到每个外部结点的路径长度之和。 内部路径长度I定义为扩充的二叉树里从根到每个内部结点的路径长度之和,北京大学信息学院 版权所有，转载或翻印必究 Page 33,二叉搜索树里检索算法,在二叉搜索树里检索算法十分简单：首先用待查的关键码与二叉搜索树的根结点进行比较，若比较相等，则找到了要检索的关键码； 若比较不等，具待查关键码值小于根结点的关键码值，则下一次与根的左子树的根比较；否则与根的右子树的根比较。 如此递归地进行下去，直到
16、某一次比较相等，检索成功；或一直比较到树叶都不相等，检索失败。,北京大学信息学院 版权所有，转载或翻印必究 Page 34,检索一个关键码的比较次数,在检索过程中，每进行一次比较，就进入下面一层。因此，对于成功的检索，比较的次数就是关键码所在的层数加1。对于不成功的检索，被检索的关键码属于哪个外部结点代表的可能关键码集合，比较次数就等于此外部结点的层数 在二叉搜索树里，检索一个关键码的平均比较次数为,北京大学信息学院 版权所有，转载或翻印必究 Page 35,参数意义,其中1i，是第i个内部结点的层数，是第i个外部结点的层数， pi是检索第i个内部结点所代表的关键码的频率 qi是被检索的关键码
17、属于第i个外部结点代表的可能关键码集合(即处于第i个和第i+1个内部结点之间)的频率。pi，qi也叫做结点的权,北京大学信息学院 版权所有，转载或翻印必究 Page 36,最佳二叉搜索树定义,是检索第i个内部结点所代表的关键码的概率， 是被检索的关键码属于第i个外部结点代表的可能关键码集合的概率。 我们把检索中平均比较次数最小，也就是ASL(n)最小的二叉搜索树称作最佳二叉搜索树,北京大学信息学院 版权所有，转载或翻印必究 Page 37,什么样的二叉搜索树是最佳的 ？,检索所有结点的概率都相等，即所有结点的权都相等： 因此，要平均比较次数ASL(n)最小，就是要内部路径长度I最小,北京大学信
18、息学院 版权所有，转载或翻印必究 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)量级的,北京大学
19、信息学院 版权所有，转载或翻印必究 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的过程
20、中会依次遇到关键码xem，wil，wan，wen，其中只有 wen是二叉搜索树中还没有的，因此第四个插入到二叉搜索树中的关键码是wen。 再检索序列中的第三个关键码wil，如此进行下去，直到所有的关键码都已插入到二叉搜索树中，这样可得到最佳二叉搜索树。,北京大学信息学院 版权所有，转载或翻印必究 Page 42,北京大学信息学院 版权所有，转载或翻印必究 Page 43,二叉搜索树的效率,反过来，如果关键码按值递增的顺序依次插入到二叉搜索树中，则将得到退化为线性的二叉搜索树平均比较次数为O(n) 按任意的顺序把关键码插入到二叉搜索树中，它的检索效率如何呢？平均比较次数是接近最坏的情况O(n)呢
21、，还是接近最好的情况O(1og2n)?可以证明，对n!种二叉搜索树进行平均，得到的平均检索次数仍是O(1og2n),北京大学信息学院 版权所有，转载或翻印必究 Page 44,检索各结点的概率不相等的情况,检索各结点的概率不相等的情况，即在具有不等权结点的二叉搜索树里进行检索。 现在的问题是给了一个排好序的关键码集合keyl，key2，keyn，和权的集合p1，p2，pn，q0，q1，qn，要找使得ASL(n)为最小的最佳二叉排序树，也就是要找使得 为最小 ，上式也称为二叉排序树的开销,北京大学信息学院 版权所有，转载或翻印必究 Page 45,北京大学信息学院 版权所有，转载或翻印必究 Pa
22、ge 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)，其权的总
23、和为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,这个式子的意
24、思是，用下列方法来找包括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，
25、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+1
26、N+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.j for(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,/
27、确定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,北京大学信息学院 版权所有，转载或翻印必究 P
28、age 57,北京大学信息学院 版权所有，转载或翻印必究 Page 58,北京大学信息学院 版权所有，转载或翻印必究 Page 59,动态规划（dynamic programming）,动态规划方法将问题分解为若干个子问题，分别求解子问题的解，然后由这些子问题的解得到原问题的解。 动态规划算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质 最优子结构是指问题的最优解包含其子问题的最优解 重叠子问题是指在自顶向下的递归求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次,北京大学信息学院 版权所有，转载或翻印必究 Page 60,动态规划与分治策略,动
29、态规划与分治策略有着明显的不同。 分治策略要求子问题之间相互独立，可以根据最有子结构直接用递归法求解 而动态规划方法所处理的子问题相互交叉。直接用递归法来求解具有重叠子问题性质的后一类问题时，常常要大量重复计算公共的子问题；而动态规划对每个子问题仅仅求解一次，并将结果填写到若干张表中，下次计算同一子问题时直接利用表中的结果。 动态规划的具体形式虽然多种多样，但它们一般都具有“填表”这一基本模式。,北京大学信息学院 版权所有，转载或翻印必究 Page 61,动态规划的应用,动态规划方法通常由于解决优化问题。这一类问题往往具有多个可行解，每一个解对应一个值。我们希望找到其中一个具有最优值（最大值或
30、最小值）的解，称为最优解（可能存在多个最优解具有同一个最优值）。,北京大学信息学院 版权所有，转载或翻印必究 Page 62,动态规划算法的步骤,设计一个动态规划算法的步骤如下： （1）刻画最优解的结构特征 （2）递归定义最优值 （3）以自底向上的方式计算出最优值 （4）根据计算过程的信息构造一个最优解 步骤（1）-（3）是动态规划方法求解最优值的基本步骤。如果需要求得最优解，则需要进一步记录计算过程的信息并执行步骤（4）。,北京大学信息学院 版权所有，转载或翻印必究 Page 63,动态规划算法求解例子,设计一个时间 的算法，找出由n个数组成的序列的最长单调递增子序列。将这个 的算法的优化为
31、 的算法 设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和Land
32、is发明了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树中的结点
33、平衡因子之可能取值为0，1和-1,北京大学信息学院 版权所有，转载或翻印必究 Page 68,AVL树结点的插入,插入与BST一样 新结点作叶结点 需要调整 相应子树的根结点变化大致有三类 结点原来是平衡的，现在成为左重或右重的 修改相应前驱结点的平衡因子 结点原来是某一边重的，而现在成为平衡的了 树的高度未变，不修改 结点原来就是左重或右重的，而新结点又加到重的一边 不平衡 “危急结点”,北京大学信息学院 版权所有，转载或翻印必究 Page 69,恢复平衡,插入17后导致不平衡,重新调整为平衡结构,北京大学信息学院 版权所有，转载或翻印必究 Page 70,不平衡的情况,正常情况下，一个结点
34、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型是对称的 不平衡的结点一定在根结点与新加入结点之间的路径
35、上 它的平衡因子只能是2或者-2 如果是2，它在插入前的平衡因子是1 如果是-2，它在插入前的平衡因子是-1,北京大学信息学院 版权所有，转载或翻印必究 Page 73,解决不平衡的方法旋转,我们可以使用一系列称为旋转( rotation )的局部操作解决这个问题 LL和RR的情况可以通过单旋转( single rotation )来解决 RL和LR的情况可以通过双旋转( double rotation )来解决 调整的整个过程称之为重构（restructuring）,北京大学信息学院 版权所有，转载或翻印必究 Page 74,单旋转,如果加入一个新结点后需要对根为结点a的子树进行单旋转，假设
36、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是一样的,北京大学信息学院
37、版权所有，转载或翻印必究 Page 79,RL型双旋转第一步,北京大学信息学院 版权所有，转载或翻印必究 Page 80,RL型双旋转第二步,北京大学信息学院 版权所有，转载或翻印必究 Page 81,旋转运算的实质,以RR型图示为例，总共有7个部分 三个结点：a、b、c 四棵子树a的左子树T0 b的左子树T1 c的左子树T2 和右子树T3 加重的是c为根的子树，但是其结构其实没有变化 因此，可以整体地看作b的右子树 目的：重新组成一个新的AVL结构 平衡 保留了中序周游的性质 T0 a T1 b T2 c T3,北京大学信息学院 版权所有，转载或翻印必究 Page 82,旋转运算的实质（续）
38、,把树做任何一种旋转（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
39、;/左右指针 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 avlN
40、ode:add(avlNode* ,北京大学信息学院 版权所有，转载或翻印必究 Page 87,return -bf; / bf=(0, +1)的情况，不需要调整树，只要修改bf else if (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 ,北京大学信息学院 版权所有，转载或翻印必究 P