北京大学：《数据结构与算法》课程教学资源（实验班讲义）第十二章 高级树结构

数据结构与算法 主要内容 第十二章高级树结构 12.1Trie和 Patricia结构 122改进的BsT 任课教员:张铭 最佳二叉搜索树 http://db.pku.edu.cn/mzhang/ds nzhang@db.pku.edu.cn 伸展树 北京大学信息科学与技术学院 12.3空间树结构 网络与信息系统研究所 ■12.4决策树和博弈树 版权所有,转载或翻印必究 北大恤血_邮c前有,轨成邮邮究 12.1Trie结构和 Patricia树 Trie结构 ■引子:BST(二叉搜索树)不是平衡的树 关键码对象空间分解 树结构与输入数据的顺序有很大的关系 “trie”这个词来源于“ retrieva” 主要应用 信息检索( information retrieva) 自然语言大规模的英文词典 叉Trie树 输入顺序:7、5、4、6、8 用每个字母的二进制编码来代表 编码只有0和1 输入顺序:4、5、6、7、8 真太恤鑫张陪。权所有,成即究 北大血信张帖 有:轨收些究 二叉Trie结构 英文字符树2Tie 元素为2、5、9、17、41、45、63 an”子树代表具 0(16)O1c16xO、1c48) 8)18)O l(44) 一棵子树代衰具有相同前缀的关键码的集合 张帖质有,轨成邮

1 数据结构与算法 第十二章 高级树结构 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 2 主要内容 „ 12.1 Trie和Patricia 结构 „ 12.2 改进的BST „ 最佳二叉搜索树 „ AVL树 „ 伸展树 „ 12.3 空间树结构 „ 12.4 决策树和博弈树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 3 12.1Trie结构和Patricia树 „ 引子：BST（二叉搜索树）不是平衡的树 „ 树结构与输入数据的顺序有很大的关系 4 5 6 7 8 7 5 8 4 6 输入顺序: 4、5、6、7、8 输入顺序: 7、5、4、6、8 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 4 Trie结构 „ 关键码对象空间分解 „ “trie”这个词来源于“retrieval” „ 主要应用 „ 信息检索（information retrieval） „ 自然语言大规模的英文词典 „ 二叉Trie树 „ 用每个字母的二进制编码来代表 „ 编码只有0和1 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 5 二叉Trie结构 元素为2、5、9、17、41、45、63 0(32) 0(16) 0(48) 1(>8) 1(>4) 2 5 9 17 41 1(>40) 63 45 0(44) 0(<48) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 6 英文字符树——26叉Trie „ 一棵子树代表具有相同前缀的关键码的集合 存单词 and、ant、bad、bee a n d t b a d e e and ant bad bee “an”子树代表具有 相同前缀an-的关 键码集合{and， ant}

字符树的改进(续) Trie字符树的特点 存储单词 an, and ant bad bee Trie结构也不是平衡的 ■t子树下的分支比z子树下的多 26个分支因子庞大的26叉树 bad bee 北大驰恤鑫 孔帖●叙肌有 申些究 北大恤血_邮c前有,轨成邮邮究 PATRICIA结构 PATRICIA结构图 a"Practical Algorithm To Retrieve Information Coded In Alphanumeric D Morrision发明的Irie结构变体 IXxxx Ixxxx iXxxx 根据关键码二进制位的编码来划分 LXxx lxxx 二叉Trie树 1010xx 1011xx MIOIxx 17:01000141;10100145:10110163;ill 真太恤鑫张陪。权所有,成即究 学单 压缩 PATRICIA结构 PATRICIA的特点 ■改进后的压缩 PATRICIA树是满二叉树 Lxxx lox lxXx 每个内部结点都代表一个位的比较 必然产生两个子结点 CXXx Dulux 次检索不超过关键码的位个数 编码:2:00105:0001019:001001 17:0100014l:101001 101101 63: llllll

2 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 7 字符树的改进（续） 存储单词an、and、ant、bad、bee a n d t b a e and ant bad bee an * 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 8 Trie字符树的特点 „ Trie结构也不是平衡的 „ t子树下的分支比z子树下的多 „ 26个分支因子——庞大的26叉树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 9 PATRICIA 结构 „ “Practical Algorithm To Retrieve Information Coded In Alphanumeric” „ D.Morrision发明的Trie结构变体 „ 根据关键码二进制位的编码来划分 „ 二叉Trie树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 10 PATRICIA 结构图 101xxx 10xxxx 0000xx 001xxx 0001xx 编码： 2：000010 5：000101 9：001001 17：010001 41：101001 45：101101 63：111111 0 1 1 2 2 3 0xxxxx 1xxxxx 00xxxx 01xxxx 11xxxx 000xxx 2 5 9 17 41 63 3 1010xx 1011xx 45 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 11 压缩PATRICIA 结构 17 01xxxx 10xxxx 001xxx 0000xx 0001xx 编码：2：000010 5：000101 9：001001 17：010001 41：101001 45：101101 63：111111 0 1 1 2 3 3 0xxxxx 1xxxxx 00xxxx 11xxxx 2 5 9 41 63 45 1011xx 1010xx 000xxx 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 12 PATRICIA的特点 „ 改进后的压缩PATRICIA树是满二叉树 „ 每个内部结点都代表一个位的比较 „ 必然产生两个子结点 „ 一次检索不超过关键码的位个数

后缀树( Suffix tree MALAYALAM$的后缀 后辍树是表示一个字符串S所有后缀申的树 MALAYALAM 结点表示开始的字符(或压缩字符串) ALAYALAM 边标注为子串—该字符申在原串中的起止位置 S LAYALA M 所有根到树叶结点的路径,可以表示率S的所有后氧 AYALAM YALAM 压Tre,得到字符串的后树 M 北大物些 有,轴即叠究 物啦 铭权有,轨量邮多究 对后缀串排序 后缀树 s· MALAYALAMS ALA M ALAM 12345678910 ALAYALAM ALAYALAM AYALAM AYALAM LAYALAM MALAYALAM MALAYALAM YALAM YALAM 北京大学值歌张写所有即究 边信息 s· MALAYALAMS 建树算法 2345678910 ■对于长度为n的语料建立后缀树,直 接的方法时间复杂度为o(n*n) 1973年 Weiner提出线性时间算法 1976年 McCreigh提出更节约内存 的算法 1995年 Ukkonen提出线性时间建 树算法

3 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 13 后缀树(Suffix Tree) „ 后缀树是表示一个字符串 S 所有后缀串的树 „ 结点表示开始的字符(或压缩字符串) „ 边标注为子串——该字符串在原串中的起止位置 „ 边表示不同字符分支 „ 所有根到树叶结点的路径，可以表示串 S 的所有后缀串 „ 通俗地说： „ 一个字符串的所有后缀 „ 这些后缀组成Trie „ 压缩Trie，得到字符串的后缀树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 14 MALAYALAM$ 的后缀 „ M A L A Y A L A M „ A L A Y A L A M „ L A Y A L A M „ A Y A L A M „ Y A L A M „ A L A M „ L A M „ A M „ M „ $ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 15 对后缀串排序 „ A L A M „ A L A Y A L A M „ A M „ A Y A L A M „ L A M „ L A Y A L A M „ M A L A Y A L A M „ M „ Y A L A M „ $ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 16 S = M A L A Y A L A M $ 1 2 3 4 5 6 7 8 9 10 YA $ LAM$ M $ ALAYALAM$ $M YALAM$ $M YALAM$ $M YALAM$ A AL LA 6 2 8 47 3 1 9 5 10 后缀树 „ A L A M „ A L A Y A L A M „ A M „ A Y A L A M „ L A M „ L A Y A L A M „ M A L A Y A L A M „ M „ Y A L A M „ $ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 17 (10, (5 10) , 10) (1, 1) (10, 10 ( ) 2, 10) (3, 4) (5, 10) (9, 10) (2, 2) (5, 10) (9, 10) (3, 4) (9, 10) (5, 10) 6 2 8 4 7 31 9 5 10 边信息 S = M A L A Y A L A M $ 1 2 3 4 5 6 7 8 9 10 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 18 建树算法 „ 对于长度为n的语料建立后缀树，直 接的方法时间复杂度为O（n*n） „ 1973年Weiner提出线性时间算法 „ 1976年McCreigh提出更节约内存 的算法 „ 1995年Ukkonen提出线性时间建 树算法

GsT通用后缀树( Generalized) 对于长度为n的字符串建立后缀树, WINDOWS INDIGOS 1234567 1234567 直接的方法时间复杂度为o(n*n) 1973年 Weiner提出线性时间算法 ·1976年 Mccreigh提出更节约内存 的算法 1995年 Ukkonen提出线性时间建 树算法 123)(L,4) 8只岛。 北大物些 有,轴即叠究 帖·有,轨盘即彭究 单词粒度的后缀树 后缀树的应用 “ I know you know$” ■查找字符串中的子串 ■统计S中出现T的次数 ■找出S中最长的重复子串 出现了两次以上的子串 know 两个字符串的公共子串 最长共同前缀(LcP) 回文串 北京大学值歌张写所有即究 后缀树的应用 后缀数组 ■中文切词 字符串S的后缀数组SA 关联分析 发现经常共同出现的短语 对s的所有后缀的指针排序 ■频繁模式挖掘 即后缀树叶结点的字典序 STC聚类 m后缀树ST=后缀数组SA+ ■基因/蛋白序列对比/分类 LcP数组

4 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 19 z 对于长度为n的字符串建立后缀树， 直接的方法时间复杂度为O（n*n） z 1973年Weiner提出线性时间算法 z 1976年McCreigh提出更节约内存 的算法 z 1995年Ukkonen提出线性时间建 树算法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 20 GST——通用后缀树(Generalized) $ O ND W I $OG D $OGI OW$ $OG ND $OGI OW$ $OGI OW$ $W $ INDOW$ $ (2, 3) (1, 4) (2, 5) (2, 4) (2, 1) (1, 2) (2, 2) (1, 3) (1, 5) (2, 6) (1, 6) (1, 1) (1, 7) (2, 7) WINDOW$ INDIGO$ 1234567 1234567 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 21 单词粒度的后缀树 z “I know you know $ ” 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 22 后缀树的应用 „ 查找字符串中的子串 „ 统计S中出现T的次数 „ 找出S中最长的重复子串 „ 出现了两次以上的子串 „ 两个字符串的公共子串 „ 最长共同前缀(LCP) „ 回文串 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 23 后缀树的应用 „ 中文切词 „ 关联分析 „ 发现经常共同出现的短语 „ 频繁模式挖掘 „ STC 聚类 „ 基因/蛋白序列对比/分类 „ …… 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 24 后缀数组 „ 字符串S的后缀数组SA „ 对S的所有后缀的指针排序 „ 即后缀树叶结点的字典序 „ 后缀树ST = 后缀数组SA + LCP数组

数组( Suffix Array) 代价分析 6 ALAMS MALAYALAM [2 ALAYALAMS 目标长n=S,模式长m=/P 23456789 空间代价 [62|843195101P 建数据结构时间代价 后缀数组 B112010o]9 查找子串时间代价 最长公共 SA O(m log n 后緞2和8共事 LcP总是相邻的 北大物些 有,轴即叠究 物啦 铭权有,轨量邮多究 后级树小结 122二叉树结构的改进 后缀树和后缀数组提供了很好的 最佳二叉排序树 全索引结构 平衡的二叉搜索树 适合于各种字符串算法 伸展树 ■大量后缀树的变种 尽力减少其空间消耗 北京大学值歌张写所有即究 ASL(n) 最佳二叉搜索树的动态规划 ■最佳子结构、重复子结构 任何子树都是最佳二又搜索树 动态规划过程 第一步:构造包含1个结点的最佳二叉搜索树 5D3○H 第二步构造包含2个结点的最佳二叉搜索树 找t(0,2),t1,3),…,tn-2,n) 再构造包含3,4,…个结点的最佳二叉搜索树 最后构造t(0,n 5

5 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 25 数组(Suffix Array) 10 $ 5 YALAM$ 9 M$ 1 MALAYALAM$ 3 LAYALAM$ 7 LAM$ 4 AYALAM$ 8 AM$ 2 ALAYALAM$ 6 ALAM$ M A L A Y A L A M $ 1 2 3 4 5 6 7 8 9 10 6 2 8 4 7 3 1 9 5 10 后缀数组 3 1 1 0 2 0 1 0 0 - 最长公共前缀数组 后缀6和2共享 “ALA” 后缀2和8共享 “A” LCP总是相邻的 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 26 代价分析 „ 目标长n=|S|，模式长m=|P|) „ 空间代价 „ ST 20n „ SA 4n „ 建数据结构时间代价 „ ST O(n) „ SA O(nlogn) „ 查找子串时间代价 „ ST O(m) • SA O(m log n) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 27 后缀树小结 „ 后缀树和后缀数组提供了很好的 全索引结构 „ 适合于各种字符串算法 „ 大量后缀树的变种 „ 尽力减少其空间消耗 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 28 12.2 二叉树结构的改进 „ 最佳二叉排序树 „ 平衡的二叉搜索树 „ 伸展树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 29 1 B 5 4 3 F H 2 1 5 4 3 D 1 1 0 1 ( ) (1 1) n n ii i i i ASL n p q l W = = ⎡ ⎤ = ++ ′ ⎢ ⎥ ⎣ ⎦ ∑ ∑ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 30 最佳二叉搜索树的动态规划 „ 最佳子结构、重复子结构 „ 任何子树都是最佳二叉搜索树 „ 动态规划过程 „ 第一步：构造包含1个结点的最佳二叉搜索树 „ 找t(0，1)，t(1，2)，…，t(n-1，n) „ 第二步构造包含2个结点的最佳二叉搜索树 „ 找t(0，2)，t(1，3)，…，t(n-2，n) „ 再构造包含3，4，…个结点的最佳二叉搜索树 „ 最后构造t(0，n)

最佳二叉搜索树t(i,j 包含关键码key+1,key+2,…,key为内 部结点(0≤i≤j≤n 以key为根 结点的权为(q,p1+1q+1 ■左子树包含key+1,…,keyx1 根为r( c(i,k-1) 1 开销为c(,,即∑n+D)+∑g ■右子树包含keyk+,keyk+ ack,刀)已求出 权的总和为W(i,j= C(,j) P+1+…+p+q+q+1+…+q w(i,j)+ min(c(i, k-1)+C(k, D) 北真大张陪曲写 有,轴即叠究 物啦 写●有:即当亮 01234 姓上2, 开销30 S71 白宁 白宁 北京大学值歌张写所有即究 cN+1][N+1] 1]intw[N+1N+1]) for(int i=O; i<=n; i ++) 3 for(intj=0小j<=nj++)//初始化 B SRD 3 RH 需出=0 IRB RI for(i-0; i<-n; i++)I willi]- blip for(int j-i+1j<-n:j++)/)求出权和wijl 花费 wlilll-wliI[j-1+all+bll for(intj=1j<n:j++){∥确定一个结点的 BestBST

6 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 31 最佳二叉搜索树t(i，j) „ 包含关键码keyi+1，keyi+2，…，keyj 为内 部结点(0≤i≤j≤n) „ 结点的权为(qi ，pi+1， qi+1，…，pj ，qj )， „ 根为r(i，j) „ 开销为C(i，j)，即 „ 权的总和为W(i，j) = pi+1+…+pj +qi +qi+1+…+qj 1 (1 1) j j x x xx xi xi p ql =+ = ∑ ∑ + + ′ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 32 „ 以keyk为根 „ 左子树包含keyi+1，…，keyk-1 „ C(i， k-1) „ 右子树包含keyk+l，keyk+2，…，keyj „ C(k，j)已求出 „ C(i，j) = W(i，j)+ (C(i，k-1)+C(k，j)) i k j min < ≤ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 33 j i 0 1 2 3 4 0 1 2 3 4 0 1 2 2 2 0 2 2 3 0 3 3 0 4 0 r(i ,j) j i 0 1 2 3 4 0 1 2 3 4 0 10 28 43 57 0 12 27 40 0 9 19 0 6 0 C(i ,j) j i 0 1 2 3 4 0 1 2 3 4 5 10 18 21 28 4 12 18 22 3 9 3 3 6 1 W(i ,j) 第 B 一 步 花费 总权 1 5 4 10 10 D 5 4 3 12 12 F 4 3 2 9 9 H 3 2 1 6 6 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 34 1 B 5 5 4 3 5 D 3 1 5 4 第 二 步 开销 总权 30 18 28 18 5 D 4 4 3 2 4 F 2 5 4 3 27 18 30 18 D B F D 4 F 3 3 2 1 3 1 4 3 2 19 13 22 13 H F H 第 三 步 花费 总权 1 B 5 5 4 4 D 5 1 5 4 24 F 3 2 4 3 2 B D F 43 24 1 F 3 5 1 2 D 5 4 B 52 24 5 D 4 4 4 3 F 4 1 4 3 41 22 H 2 1 3 2 1 D F H 40 22 3 H 4 5 4 1 D 3 2 F 49 24 第 1 5 4 3 51 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 35 第 四 步 花费 总权 1 B 5 4 3 F 5 1 5 4 68 28 H 2 1 4 3 B D F 57 28 3 5 1 D 5 4 3 D 3 2 1 H 4 5 3 1 3 2 D F H 1 5 4 B 62 28 4 F 3 2 1 5 4 B H 71 28 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 36 void OptimalBST(int a[], int b[], int n, int c[N+1][N+1], int r[N+1][N+1], int w[N+1][N+1]) { for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) {// 初始化 c[i][j]=0; r[i][j]=0; w[i][j]=0; } for (i = 0; i <=n; i++) { w[i][i] = b[i]; for(int j=i+1;j<=n;j++) //求出权和w[i.j] w[i][j]=w[i][j-1]+a[j]+b[j]; } for(int j=1;j<=n;j++) { //确定一个结点的BestBST c[j-1][j]=w[j-1][j]; r[j-1][j]=j; }

int m kO.k: for(intd=2;d<=n;d++){确定d个结点 for(int j=d; j<=n: j++)i 1222平衡的二叉搜索树△VL [nI 轴入顺序为4、5、6、7、8 BST受输入顺序影响 k0=i+1 for(k=计+2;k<=j;k++){ 最好Oogn) if(clillk-1F+c[k[jl<m)i ■最坏O(m) ooo m=[ik-1+clkllil Adelson-Velskii和 Landis发明了AⅥ树 入序为7、5、↓、6、8 cllwllm; r[[lk0 平衡的二叉搜索树 始终保持ogn量级Q 北大物些 有,轴即叠究 物啦 铭权有,轨量邮多究 AVL树的性质 AVL树举例 可以为空 具有n个结点的AVL树,高度为 O(og n) ■如果T是一棵AVL树 那么它的左右子树T、T也是AVL树 并且h1-h1≤1 h1、hg是它的左右子树的高度 北京大学值歌张写所有即究 斗平衡因子 AⅥL树结点的插入 平衡因子,b/(x) 插入与BST一样 b八(xx的右子树的高度一x的左子树的高皮 新结点作叶结点 对于一个AVL树中的结点平衡因子之可能取值 需要调整 ■相应子树的根结点变化 结点原来是平衡的,现在成为左重或右重的 修改相应前驱结点的平衡因 结点原来是某一边重的,而现在成为平衡的了 的高度未变,不修改 结点原来就是左重或右重的,又加到重的一边 “危急结点

7 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 37 int m,k0,k; for(int d=2;d<=n;d++) {//确定d个结点 for(int j=d;j<=n;j++) { i=j-d; m=c[i+1][j]; k0=i+1; for(k=i+2;k<=j;k++) { if(c[i][k-1]+c[k][j]<m) { m=c[i][k-1]+c[k][j]; k0=k; } } c[i][j]=w[i][j]+m; r[i][j]=k0; } } } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 38 12.2.2 平衡的二叉搜索树(AVL) „ BST受输入顺序影响 „ 最好O(log n) „ 最坏O(n) „ Adelson-Velskii 和 Landis发明了AVL树 „ 平衡的二叉搜索树 „ 始终保持O(log n)量级 输入顺序为 4、5、6、7、8 4 5 6 7 8 7 5 8 4 6 输入顺序为 7、5、4、6、8 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 39 AVL树的性质 „ 可以为空 „ 具有n个结点的AVL树，高度为 O(log n) „ 如果T是一棵AVL树 „ 那么它的左右子树TL、TR也是AVL树 „ 并且| hL-hR|≤1 „ hL、hR 是它的左右子树的高度 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 40 AVL树举例 T1 T3 T2 T4 Ti-1 Ti-2 Ti 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 41 平衡因子 „ 平衡因子，bf(x)： „ bf(x)= x的右子树的高度 – x的左子树的高度 „ 对于一个AVL树中的结点平衡因子之可能取值 为0，1和-1 9 1 1 8 3 12 10 15 11 -1 0 0 0 -1 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 42 AVL树结点的插入 „ 插入与BST一样 „ 新结点作叶结点 „ 需要调整 „ 相应子树的根结点变化 „ 结点原来是平衡的，现在成为左重或右重的 „ 修改相应前驱结点的平衡因子 „ 结点原来是某一边重的，而现在成为平衡的了 „ 树的高度未变，不修改 „ 结点原来就是左重或右重的，又加到重的一边 „ 不平衡 „ “危急结点

恢复平衡 衡情况发生在插入新结点后 ■BST把新结点插入到叶结点 ■假设a是离插入结点最近,且平衡因子绝 对值不等于0的结点 3 新插入的关键码为key的结点s要么在它的左 树中,要么在其右子树中 假设插入在右边,原平衡因子 插入17后导致不平衡 重新训整为平衡结构 (2)a->bf=0 (3)a->bf=+1 北真大张陪曲写 有,轴即叠究 帖·有,轨盘即彭究 都插入在右边 ■假设a离插入结点最近,且平衡因子绝对值不等于0 (1)a>bf=-1=)0(2)a->bf=0=>+1 新插入的结点s(关健码为key)要么在a的左子树 中,要么在其右子树中 Da 假设在右边,因为从s(新插入结点)到a的除s和a以 外的结点都要从原bf=0变为|bf|=+1,对于结点a 2)bRR型 b RL2 1.a->bf=-1,则a->bf=0,以a为根的子树高度 2.a->bf=0,则a->bf=+1,以a为的子树树高 (3)a->bf=+1=>+2 3.a->bf=+1,则a->bf=+2,需要调整 北京大学值歌张写所有即究 不平衡的情况 不平衡的图示 AV树任意结点A的平衡因子只能是0,1,-1 A本来左重,Abf=-1,插入一个结点导致A.bf 变为2 到A的左子树的左子树 到A的左子树的右子树 左十右,Ab度变为2 ■类似地,A.bf=1,插入新结点使得A.b变为2 RR型:导致不平衡的结点为A的右子树的右结点 LL型 型 RL型:导致不平衡的结点为A的右子树的左结点

8 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 43 恢复平衡 插入17后导致不平衡 重新调整为平衡结构 1 10 -1 8 0 3 2 12 1 15 0 17 0 10 -1 8 0 3 0 15 0 17 0 12 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 44 „ 不平衡情况发生在插入新结点后 „ BST把新结点插入到叶结点 „ 假设a是离插入结点最近，且平衡因子绝 对值不等于0的结点 „ 新插入的关键码为key的结点s要么在它的左 子树中，要么在其右子树中 „ 假设插入在右边，原平衡因子 „ (1) a->bf = -1 „ (2) a->bf = 0 „ (3) a->bf = +1 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 45 都插入在右边 - - / - - \ - - (3)a->bf=+1 \ - - a a a a b b c c (1)a->bf=-1 =>+2 RR型 RL型 =〉0 =>+1 (2)a->bf=0 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 46 „ 假设a离插入结点最近，且平衡因子绝对值不等于0 „ 新插入的结点s（关键码为key）要么在a的左子树 中，要么在其右子树中 „ 假设在右边，因为从s(新插入结点)到a的除s和a以 外的结点都要从原bf=0变为|bf|=+1，对于结点a „ 1. a->bf = -1，则a->bf = 0，以a为根的子树高度 不变 „ 2. a->bf = 0，则a->bf = +1，以a为根的子树树高 改变 „ 由a的定义(a->bf ≠ 0)，可知a是根 „ 3. a->bf = +1，则a->bf = +2，需要调整 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 47 不平衡的情况 „ AVL树任意结点A的平衡因子只能是0，1，-1 „ A本来左重，A.bf=＝-1，插入一个结点导致A.bf 变为-2 „ LL型：插入到A的左子树的左子树 „ 左重＋左重，A.bf变为-2 „ LR型： 插入到A的左子树的右子树 „ 左重＋右重，A.bf变为-2 „ 类似地， A.bf=＝1，插入新结点使得A.bf变为2 „ RR型：导致不平衡的结点为A的右子树的右结点 „ RL型：导致不平衡的结点为A的右子树的左结点 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 48 不平衡的图示 LL型 RR型 -2 a -1 b h h h+1 2 a 1 b h h h+1

不平衡情况总结 解决不平衡的方法—旋转 LL型和RR型是对称的,LR型和RL 我们可以使用一系列称为旋转( rotation) 型是对称的 的局部操作解决这个问题 入结点之间的路径上 定在根结点与新加 LL和R的情况可以通过单旋转( single rotation)来解决 ■RL和LR的情况可以通过双旋转( double 它的平衡因子只能是2或者2 rotation)来解决 如果是2,它在插入前的平衡因子是 ■调整的整个过程称之为重构 如果是2,它在插入前的平衡因子是1 restructuring 北大物些 有,轴即叠究 物啦 铭权有,轨量邮多究 单旋转 危机结点a 对根为结点的子树进行单旋转 b为包含新加入结点的a的子结点 c为包含新加入结点的b的子结点 单旋转 令b代替a成为新根,a和c作为其子结点 原来的子树保持不变 原来b中c结点的兄弟子树,作为a的子树 新结点插入到c的左或右子树 的磨点。是孕的祖先路径上,ab 访问顺序为a、b、c(编号,不是值大小) 北京大学值歌张写所有即究 L型单旋转 LL型单旋转 插入前 cbf保持 子树高h+2 原来的1或-1 Q或-1 插入后 或1 子树高h T2 銮结

9 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 49 不平衡情况总结 „ LL型和RR型是对称的，LR型和RL 型是对称的 „ 不平衡的结点一定在根结点与新加 入结点之间的路径上 „ 它的平衡因子只能是2或者-2 „ 如果是2，它在插入前的平衡因子是1 „ 如果是-2，它在插入前的平衡因子是-1 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 50 解决不平衡的方法——旋转 „ 我们可以使用一系列称为旋转( rotation ) 的局部操作解决这个问题 „ LL和RR的情况可以通过单旋转( single rotation )来解决 „ RL和LR的情况可以通过双旋转( double rotation )来解决 „ 调整的整个过程称之为重构 （restructuring） 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 51 单旋转 „ 对根为结点a的子树进行单旋转 „ b为包含新加入结点的a的子结点 „ c为包含新加入结点的b的子结点 „ 单旋转 „ 令b代替a成为新根，a和c作为其子结点 „ 原来c的子树保持不变 „ 原来b中c结点的兄弟子树，作为a的子树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 52 危机结点a T3 h T0 h-1 T1 h-1 T2 h -1 a 0 b 0 c 新结点插入到c的左或右子树 插入前，a是最靠近c的祖先路径上，a.bf!=0 的结点。a子树高h+2 访问顺序为a、b、c（编号，不是值大小） 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 53 LL型单旋转 T3 h T0 h-1 /h T1 h/ h-1 T2 h -2 a -1 b 1 c 或-1 插入前 a子树高h+2 插入后 a子树高h+3 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 54 LL型单旋转 a T3 h T0 h-1 /h T1 h/ h-1 T2 h b 0 0 c.bf保持 原来的１或-1 其实，不用 看结点C c 1 或-1

其实,不用看结点C 其实,不用看结点C 北大物些 有,轴即叠究 物啦 铭权有,轨量邮多究 RR型单旋转 RR型单旋转 c 或1 北京大学值歌张写所有即究 旋转运算的实质 双旋转 以R型图示为例,总共有7个部分 三个结点:a、b、c RL或者LR需要进行双旋转 四橾子树T。、T1、T2、T3 这两种情况是对称的 加重c为根的子树,但是其结构其实没有变化 T2、c、T可以整体地看作b的右子树 我们只讨论RL的情况 LR是一样的 目的:重新组成一个新的AVL结构 保留了中序周游的性质 TaT,bT2eT3 10

10 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 55 其实，不用看结点C T3 h h+1 T2 h -1 b -2 a T1 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 56 其实，不用看结点C a T3 h T2 h b 0 0 h+1 T1 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 57 RR型单旋转 T3 h/ h-1 1 b 2 a T2 h-1 /h T1 T0 h h 1 c 或-1 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 58 RR型单旋转 b T1 h a T0 h 0 0 1 c 或-1 T2 h-1 /h T3 h/ h-1 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 59 旋转运算的实质 „ 以RR型图示为例，总共有7个部分 „ 三个结点：a、b、c „ 四棵子树T0 、T1 、 T2 、 T3 „ 加重c为根的子树，但是其结构其实没有变化 „ T2 、c、 T3可以整体地看作b的右子树 „ 目的：重新组成一个新的AVL结构 „ 平衡 „ 保留了中序周游的性质 „ T0 a T1 b T2 c T3 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 60 双旋转 „ RL或者LR需要进行双旋转 „ 这两种情况是对称的 „ 我们只讨论 RL的情况 „ LR是一样的