算法设计与分析 课件 5.9-动态规划应用-最优二叉搜索树

信息工程大学算法设计与分析动态规划—最优二叉搜索树国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版二叉搜索树的定义：（1）是一棵二叉树；（2）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；（3）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；（4）它的左、右子树也分别为二叉搜索树。4512533100在二叉搜索树上查找不成功所需的比较次数是：虚拟结点的深度在二叉搜索树上查找成功所需的比较次数是：结点的深度+1查找100的过程：与45比较；与53比较；与100比较；查找成功。查找40的过程：与45比较；与12比较；查找不成功。4553123100<33<x<1212<x<4545<x<53x>10053<x<100a1a2a3a4a5b0b1b2b3b4b5单选题。在下图所示的二叉搜索树上，查找90需要比较的次数是（）。A.3B.4C.24553123100<33<x<1212<x<4545<x<53x>10053<x<100a1a2a3a4a5b0b1b2b3b4b5

实例：假定S=<3,12,45,53,100>，P=<0.05,0.10,0.15,0.10,0.05,0.15,0.04,0.12,0.08,0.07,0.09>。(a)T=2.39(b)T=2.381.穷举法有n个结点的二叉搜索树的个数为P(n)，由于每个二叉搜索树都可以分解为左子树、根和右子树，而左、右子树都是二叉搜索树，因此有：最优二叉搜索树满足最优子结构性质吗？假设右图是在给定序列S=<k1,k2,k3,k4,k5>,搜索概率为P=<q0,p1,q1,p2,q2,…,p5,q5>的最优二叉搜索树，那么其左子树是以序列S1=<k1>及相应概率对应的最优二叉搜索树，其右子树是以序列S2=<k3,k4,k5>及相应概率对应的最优二叉搜索树。反证法证明。定义S(i,j)=<ki,ki+1,…,kj

>概率分布P(i,j)=<qi-1,pi,qi,pi+1,…,pj，qj>w(i,j)=qi-1+pi+qi+pi+1+…+pj+qj

定义m(i,j)：

对应S(i,j)和P(i,j)的最优二叉搜索树的平均比较次数。1.找出最优解性质，刻画结构特征2.递归地定义最优值3.以自底向上的方式计算最优值123…n123…nm(i,j)1个结点2个结点3个结点…n个结点实例：S=<3,12,45,53,100>，P=<0.05,0.10,0.15,0.10,0.05,0.15,0.04,0.12,0.08,0.07,0.09>（1）首先计算1个结点的二叉搜索树的平均比较次数m(1,1)、m(2,2)、m(3,3)、m(4,4)、m(5,5)。1253453100<33<x<1212<x<4545<x<53x>10053<x<100a2a1a3a4a5b0b1b2b3b4b53<x<12b112<x<45b245<x<5353<x<100b4b3m(1,1)m(2,2)m(3,3)m(4,4)m(5,5)（2）计算有2个结点的二叉搜索树的最少平均比较次数m(1,2)、m(2,3)、m(3,4)、m(4,5)。实例：S=<3,12,45,53,100>。124512<x<4545<x<53a23<x<1212<x<4545123<x<1245<x<53m(2,3)：以a2为根结点a2a3a3b1b2b3b1b2b3m(2,3)：以a3为根结点（3）计算有3个结点的二叉搜索树的最少平均比较次数m(1,3)、m(2,4)、m(3,5)。实例：S=<3,12,45,53,100>。1253a2a4b1b4b1b35312a4a2b4a345b2b345a3a453b4b312a2b1b245a3b2m(2,4)：以a4为根结点m(2,4)：以a3为根结点m(2,4)：以a2为根结点实例：S=<3,12,45,53,100>。（4）计算有4个结点的二叉搜索树的最少平均比较次数m(1,4)、m(2,5)。1253a2a4b1b1b35312a4a2b4a345b2b345a3a453b5b312a2b1b245a3b2a5100b5100a5b4100a5b5b4100b1b345a5a212a3b253a4b5b4m(2,5)：以a2为根结点m(2,5)：以a3为根结点m(2,5)：以a4为根结点m(2,5)：以a5为根结点

j=0j=1j=2j=3j=4j=5i=100.300.751.181.822.38i=2

00.300.731.231.79i=3

00.240.681.08i=4

00.240.64i=5

00.24实例：S=<3,12,45,53,100>，P=<0.05,0.10,0.15,0.10,0.05,0.15,0.04,0.12,0.08,0.07,0.09>。m数组

j=0j=1j=2j=3j=4j=5i=1011222i=2

2233i=3

344i=4

44i=5

54.根据计算最优值时得到的信息，构造最优解记录q(i,j)=k，k是m(i,j)获得最小值时对应的根结点编号。S=<3,12,45,53,100>，P=<0.05,0.10,0.15,0.10,0.05,0.15,0.04,0.12,0.08,0.07,0.09>。q数组voidoptimalBT(double*p，double*w,intn，double**m，int**q){……w[0]=0;for(i=1;i<=n;i++){/*计算w[i]*/w[i]=w[i-1]+p[2*i-2]+p[2*i-1];for(i=1;i<=n;i++){/*初始化结点数目为0和1的二叉搜索树*/m[i][i]=w[i]-w[i-1]+p[2*i];q[i][i]=i;m[i][i-1]=0;}for(r=2;r<=n;r++){/*结点数目从2到n*/for(i=1;i<=n-r+1;i++){/*i表示结点的起始编号*/j=i+r-1;/*j表示结点的终止编号*/

w_i_j=w[j]-w[i-1]+p[2*j]m[i][j]=m[i+1][j]+w_i_j;q[i][j]=i;/*计算根结点编号是i+1~j处的平均比较次数，并记录根结点编号*/for(k=i+1;k<=j;k++){t=m[i][k-1]+m[k+1][j]+w_i_j;/*找到较小比较次数，更新