最佳二叉搜索树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