第3章最优二叉搜索树ppt.ppt

13.5最优二叉搜索树最优二叉搜索树OptimalBinarySearchTrees21二叉搜索树二叉搜索树2最优二叉搜索树最优二叉搜索树3最优二叉搜索树问题描述最优二叉搜索树问题描述4最优子结构性质最优子结构性质5递归计算最优值递归计算最优值6算法算法3是一棵空树或者满足以下的性质：是一棵空树或者满足以下的性质：每个结点作为搜索对象，它的关键字是互不相同的。每个结点作为搜索对象，它的关键字是互不相同的。对于树上的所有结点，如果它有对于树上的所有结点，如果它有左子树左子树左子树左子树，那么左子树，那么左子树上所有结点的关键字都小于该结点的关键字。上所有结点的关键字都小于该结点的关键字。对于树上的所有结点，如果它有对于树上的所有结点，如果它有右子树右子树右子树右子树，那么右子树，那么右子树上所有结点的关键字都大于该结点的关键字。上所有结点的关键字都大于该结点的关键字。1二叉搜索树二叉搜索树4xalwanwilwenwimwulzolyozomxulyumxemyonzi搜索过程：从根结点开始，如果根为空，则搜索搜索过程：从根结点开始，如果根为空，则搜索不成功；否则使用待搜索值与根结点比较，如不成功；否则使用待搜索值与根结点比较，如果待搜索值等于根结点关键字，则搜索成功返果待搜索值等于根结点关键字，则搜索成功返回，如果小于根结点，则向左子树搜索；如果回，如果小于根结点，则向左子树搜索；如果大于根结点，则向右子树搜索。大于根结点，则向右子树搜索。1二叉搜索树二叉搜索树5对于一个给定的关键字集合，可能有若干不同的对于一个给定的关键字集合，可能有若干不同的二分检索树二分检索树如对保留字的子集如对保留字的子集Name：12345foriflooprepeatwhile的两棵二分检索树为的两棵二分检索树为ifforwhilelooprepeatifwhilelooprepeatforab考虑考虑a图和图和b图中最图中最坏比较次数和平均坏比较次数和平均比较次数比较次数1二叉搜索树二叉搜索树6构造不同的二叉搜索树就有不同的性能特征。构造不同的二叉搜索树就有不同的性能特征。二叉搜索树二叉搜索树a在最坏情况下找一个标识符需要在最坏情况下找一个标识符需要4次比较，次比较，而而b表示的二分检索树最坏情况下只需表示的二分检索树最坏情况下只需3次比较。次比较。假设只作成功的检索并且检索每个标识符的概率相同，假设只作成功的检索并且检索每个标识符的概率相同，则两棵二分检索树在平均情况下各需要则两棵二分检索树在平均情况下各需要12/5和和11/5次次比较。比较。ifforwhilelooprepeatifwhilelooprepeatforab1二叉搜索树二叉搜索树72、最优二叉搜索树、最优二叉搜索树存在的两个问题存在的两个问题1在实际中也会遇到不成功检索的情况。在实际中也会遇到不成功检索的情况。2在实际中，不同标识符会有不同的检索概率。在实际中，不同标识符会有不同的检索概率。对给定的标识符集合，希望给出构造二分搜索对给定的标识符集合，希望给出构造二分搜索树的方法，使得所构造的二分搜索树具有最优树的方法，使得所构造的二分搜索树具有最优的性能。的性能。2最优二叉搜索树最优二叉搜索树8扩充二叉树：当二叉树里出现空的子树时，扩充二叉树：当二叉树里出现空的子树时，就增加新的、特殊的结点就增加新的、特殊的结点空树叶。对空树叶。对于原来二叉树里度数为于原来二叉树里度数为1的分支结点，在它的分支结点，在它下面增加一个空树叶；对于原来二叉树的下面增加一个空树叶；对于原来二叉树的树叶，在它下面增加两个空树叶。树叶，在它下面增加两个空树叶。扩充二叉树是满二叉树，新增加的空树叶扩充二叉树是满二叉树，新增加的空树叶（以下称外部结点）的个数等于原来二叉（以下称外部结点）的个数等于原来二叉树的结点（以下称内部结点）个数加树的结点（以下称内部结点）个数加1。在实际中也会遇到不成功检索的情况在实际中也会遇到不成功检索的情况2最优二叉搜索树最优二叉搜索树9xalwanwilwenwimwulzolyozomxulyumxemyonziAA代表其值处于代表其值处于wim和和wul之间的可能关键码集合之间的可能关键码集合2最优二叉搜索树最优二叉搜索树10设设S=x1,x2,xn是一个有序集合，且是一个有序集合，且x1,x2,xn表示有序集合的二叉搜索树利用二叉树的表示有序集合的二叉搜索树利用二叉树的顶点存储有序集中的元素，而且具有性质：顶点存储有序集中的元素，而且具有性质：存储于每个顶点中的元素存储于每个顶点中的元素x大于其左子树中任一个大于其左子树中任一个顶点中存储的元素，小于其右子树中任意顶点中存顶点中存储的元素，小于其右子树中任意顶点中存储的元素。二叉树中的叶顶点是形如储的元素。二叉树中的叶顶点是形如(xi,xi+1)的开的开区间。区间。在二叉搜索树中搜索一个元素在二叉搜索树中搜索一个元素x(1)在二叉树的内部顶点处找到：在二叉树的内部顶点处找到：x=xi(2)在二叉树的叶顶点中确定：在二叉树的叶顶点中确定：x(xi,xi+1)2最优二叉搜索树最优二叉搜索树11在实际中，不同标识符会有不同的检索概率。在实际中，不同标识符会有不同的检索概率。设设Pi是对是对ai检索的概率。检索的概率。设设qi是对满足是对满足aiXai+1,0 i n的标识符的标识符X检索的概率，检索的概率，(假定假定a0=-且且an+1=)。a1Q(0)E0P(1)a2E1Q(1)P(2)aiP(i)ai+1EiQ(i)P(i+1)anP(n)EnQ(n)2最优二叉搜索树最优二叉搜索树12最优二叉搜索树最优二叉搜索树利用动态规划构造对标识符集合利用动态规划构造对标识符集合a1,a2,an的最优二叉搜索树算法的最优二叉搜索树算法（包括成功检索和不成功检索）。（包括成功检索和不成功检索）。2最优二叉搜索树最优二叉搜索树13例例标识符集标识符集1,2,3do,if,stop可能的二可能的二分检索树为：分检索树为：(a)321 231 (c)312(d)(b)312 321 (e)设每个内、外结点检索的概率相同：设每个内、外结点检索的概率相同：pi=qi=1/7，求每棵树的平均比较次数（成本）。求每棵树的平均比较次数（成本）。若若P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05，求每棵树的平均比较，求每棵树的平均比较次数（成本）。次数（成本）。14在检索过程中，每进行一次比较，就进入下面一层，在检索过程中，每进行一次比较，就进入下面一层，对于成功的检索，比较的次数就是所在的层数加对于成功的检索，比较的次数就是所在的层数加1。对于不成功的检索，被检索的关键码属于那个外部结对于不成功的检索，被检索的关键码属于那个外部结点代表的可能关键码集合，比较次数就等于此外部结点代表的可能关键码集合，比较次数就等于此外部结点的层数。点的层数。2最优二叉搜索树最优二叉搜索树15例：P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05123q0q1q2q3123q0q1q2q3q0123q1q2q3123q0q1q2q3123q0q1q2q3考虑平均搜索次数，也叫做考虑平均搜索次数，也叫做平均路长平均路长Pa(n)=1p1+2p2+3p3+1q0+2q1+3(q2+q3)=10.5+20.1+30.05+10.05+20.1+3(0.05+0.05)=1.52最优二叉搜索树最优二叉搜索树abcde16分析对于图的内结点而言，第对于图的内结点而言，第0层需要比较操作次数为层需要比较操作次数为1，第，第1层需要比较层需要比较2次，第次，第2层层需要需要3次次Pb(n)=1 p1+2 p3+3 p2+1q0+3(q2+q3)=1 0.5+2 0.05+3 0.1+10.15+20.05+3(0.05+0.05)=1.6Pc(n)=1 p2+2 (p1+p3)+2(q0+q1+q2+q3)=1 0.1+2 (0.5+0.05)+2(0.15+0.1+0.05+0.05)=1.9Pd(n)=1 p3+2 p1+3 p2+1 q3+2 q0+3 (q1+q2)=1 0.05+2 0.5+3 0.1+10.05+2 0.15+3 (0.1+0.05)=2.15Pe(n)=1 p3+2 p1+3 p2+1 q3+2 q0+3 (q1+q2)=1 0.05+2 0.5+3 0.1+10.05+2 0.15+3 (0.1+0.05)=2.152最优二叉搜索树最优二叉搜索树17找到元素找到元素x=xi的概率为的概率为bi；确定；确定x(xi,xi+1)的的概率为概率为ai。其中约定其中约定x0=,xn+1=+,有有2最优二叉搜索树最优二叉搜索树18在一个表示在一个表示S的二叉树的二叉树T中，设存储元素中，设存储元素xi的结点深的结点深度为度为ci；叶结点（；叶结点（xj，xj1）的结点深度为）的结点深度为dj 。表示在二叉搜索树表示在二叉搜索树T中作一次搜索所需的平均比中作一次搜索所需的平均比较次数。较次数。P又称为二叉搜索树又称为二叉搜索树T的平均路长，在的平均路长，在一般情况下，不同的二叉搜索树的平均路长是不一般情况下，不同的二叉搜索树的平均路长是不同的。同的。2最优二叉搜索树最优二叉搜索树193、最优二叉搜索树问题描述、最优二叉搜索树问题描述对于有序集对于有序集S及其存取概率分布及其存取概率分布（a0,b1,a1,bn,an），在所有表示有序集），在所有表示有序集S的二叉搜索树中找出一棵具有最小平均路的二叉搜索树中找出一棵具有最小平均路长的二叉搜索树。长的二叉搜索树。结点在二叉搜索树中的层次越深，需要比结点在二叉搜索树中的层次越深，需要比较的次数就越多，因此要构造一棵最小二较的次数就越多，因此要构造一棵最小二叉树，一般尽量把搜索概率较高的结点放叉树，一般尽量把搜索概率较高的结点放在较高的层次。在较高的层次。3最优二叉搜索树问题最优二叉搜索树问题204、最优子结构性质、最优子结构性质假设选择假设选择k为树根，则为树根，则1,2,k-1和和a0,a1,ak-1都将位于左子树都将位于左子树L上，其余上，其余结点结点(k+1,n和和ak,ak+1,an)位于位于右子树右子树R上。上。k L R 1,2,k-1 a0,a1,ak-1k+1,n ak,ak+1,an4最优子结构性质最优子结构性质21511472063353976425431399844最优子结构性质最优子结构性质22511472063353976425431399844最优子结构性质最优子结构性质23设设COST(L)和和COST(R)分别是二分检索树分别是二分检索树T的左子树和右子树的成本。的左子树和右子树的成本。则检索树则检索树T的成本是：的成本是：P(k)+COST(L)+COST(R)+若若T是最优的，则上式及是最优的，则上式及COST(L)和和COST(R)必定都取最小值。必定都取最小值。4最优子结构性质最优子结构性质24最优子结构性质证明最优子结构性质证明二叉搜索树二叉搜索树T的一棵含有顶点的一棵含有顶点xi,xj和叶顶点和叶顶点 (xi-1,xi),(xj,xj+1)的子树可以看作是有序集的子树可以看作是有序集 xi,xj 关于全集为关于全集为 xi-1,xj1 的一棵二叉搜索树的一棵二叉搜索树（T 自身可以看作是有序集自身可以看作是有序集)。根据根据S 的存取分布概率，在子树的顶点处被搜索到的的存取分布概率，在子树的顶点处被搜索到的概率是：概率是：4最优子结构性质最优子结构性质25左子树左子树的搜索的搜索概率概率右子树右子树的搜索的搜索概率概率设设Tij是有序集是有序集xi,xj关于存储概率分布为关于存储概率分布为ai-1,bi,bj,aj 的一棵最优二叉搜索树，其平均路长的一棵最优二叉搜索树，其平均路长为为pij，Tij的根顶点存储的元素的根顶点存储的元素xm，其左子树，其左子树Tl和右子树和右子树Tr的平均路长分别为的平均路长分别为pl和和pr。由于。由于Tl和和Tr中顶点深度是它中顶点深度是它们在们在Tij中的深度减中的深度减1，所以得到，所以得到xi,xj的存储概率分布为的存储概率分布为ai-1,bi,bj,aj，其，其中，中，ah，bk分别是下面的条件概率：分别是下面的条件概率：4最优子结构性质最优子结构性质26构造最优二叉搜索树时，可以选构造最优二叉搜索树时，可以选择先构造其左右子树，使其左右择先构造其左右子树，使其左右子树最优，然后构造整棵树。子树最优，然后构造整棵树。4最优子结构性质最优子结构性质275、递归计算最优值最优二叉搜索树最优二叉搜索树Tij的平均路长为的平均路长为pij，则所求的，则所求的最优值为最优值为p1,n。由二叉树的花费公式。由二叉树的花费公式根据最优二叉搜索树问题的最优子结构性质可根据最优二叉搜索树问题的最优子结构性质可建立计算建立计算pij的递归式如下的递归式如下初始时初始时5递归计算最优值递归计算最优值28记记 wi,j pi,j 为为m(i,j)递归计算最优值递归计算最优值5递归计算最优值递归计算最优值29根据该公式，计算树根据该公式，计算树Tij的花费只用到了的花费只用到了Tik-1，Tk+1j,可得到具体求解过程如下：可得到具体求解过程如下：1）构造只有）构造只有1个内部结点的最优二叉搜索树个内部结点的最优二叉搜索树T11,T22,Tnn，可以求得，可以求得mii同时同时可以用一个数组存做根结点元素为：可以用一个数组存做根结点元素为：s11=1,s22=2snn=n2)构造具有构造具有2个内部结点的最优二叉搜索树个内部结点的最优二叉搜索树30例给出标识符集给出标识符集1,2,3do,if,stop存取存取概率概率若若P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05构造一棵最优二叉搜索树构造一棵最优二叉搜索树5递归计算最优值递归计算最优值31q0=0.15,P1=0.5,q1=0.1,P2=0.1,q2=0.05,P3=0.05,q3=0.051q0q1T11w11=0.75m11=0.752q1q2T22w22=0.25m22=0.253q2q3T33w33=0.15m33=0.1512q0q1q212q0q1q2T12w12=0.9m12=0.9+m11+m32=1.65w12=0.9m12=0.9+m10+m22=1.15q0T10w10=0.15m10=0q1T21w21=0.1m21=0q2T32w32=0.05m32=0q3T43w43=0.05m43=032q0=0.15,P1=0.5,q1=0.1,P2=0.1,q2=0.05,P3=0.05,q3=0.051q0q1T11w11=0.75m11=0.752q1q2T22w22=0.25m22=0.253q2q3T33w33=0.15m33=0.1512q0q1q212q0q1q2T12w12=0.9m12=0.9+m11+m32=1.65w12=0.9m12=0.9+m10+m22=1.1523q1q2q323q1q2q3T23w23=0.5m23=0.5m23=0.633q0=0.15,P1=0.5,q1=0.1,P2=0.1,q2=0.05,P3=0.05,q3=0.051q0q1T11w11=0.75m11=0.752q1q2T22w22=0.25m22=0.253q2q3T33w33=0.15m33=0.1512q0q1q212q0q1q2T12w12=0.9m12=0.9+m11+m32=1.65w12=0.9m12=0.9+m10+m22=1.1523q1q2q323q1q2q3T23w23=0.35m23=0.5m23=0.634T12m12=1.1512q0q1q223q1q2q3T23m23=0.523q2q31q0q1T13W13=1m13=1.523q2q31q0q1m13=1.923q2q31q0q1m13=2.15q0=0.15,P1=0.5,q1=0.1,P2=0.1,q2=0.05,P3=0.05,q3=0.0535T12m12=1.1512q0q1q223q1q2q3T23m23=0.523q2q31q0q1T13W13=1m13=1.523q2q31q0q1m13=1.923q2q31q0q1m13=2.15q0=0.15,P1=0.5,q1=0.1,P2=0.1,q2=0.05,P3=0.05,q3=0.05360123123000040 1 2 31234W(i,j)0 1 2 3123400000.150.10.050.050.750.7510.250.150.250.15230.91.1510.3510.521.51m(i,j)s(i,j)q0=0.15,P1=0.5,q1=0.1,P2=0.1,q2=0.05,P3=0.05,q3=0.0537具体求解过程具体求解过程1)递归出口，没有内部节点时，构造递归出口，没有内部节点时，构造T10T21,T32，Tn+1n2)构造具有构造具有2个、个、3个、个、n个内部结点的最优二叉个内部结点的最优二叉搜索树搜索树r（起止下标的差）起止下标的差）0T11,T22,，Tnn，1T12,T23,，Tn-1n，2T13,T24,，Tn-2n，rT1r+1,T2r+2,，Tii+r，Tn-rnn-1T1n5递归计算最优值递归计算最优值38voidOBST(int*a,int*b,intn,int*m,int*s,int*w)for(inti=0;i=n;i+)wi+1i=ai;mi+1i=0;/初始化，构造没有内部节点时的情况初始化，构造没有内部节点时的情况for(intr=0;rn;r+)for(inti=1;i=n-r;i+)intj=i+r;构造构造Tij，填写，填写wij,mij,sij39构造构造TijTij表示用第表示用第i到第到第j个内部节点构造的树，做根的结个内部节点构造的树，做根的结点可以是第点可以是第i，i+1,j中任意一个。中任意一个。1)首选首选i作为根，其左子树空，右子树为结点作为根，其左子树空，右子树为结点i+1,i+2j构成即构成即Ti+1j。mij=wij+0+mi+1jsij=i2)不选不选i做根，设做根，设k为其根，则为其根，则k=i+1,j,左子树为结左子树为结点点i,i+1,k-1,右子树为右子树为k+1,k+2,jt=wij+mik-1+mk+1jif(tmij)mij=t;sij=k;3)k=k+1,跳回跳回25递归计算最优值递归计算最优值40voidOptimalBinarySearchTree(int*a,int*b,intn,int*m,int*s,int*w)for(inti=0;i=n;i+)wi+1i=ai;mi+1i=0;for(intr=0;rn;r+)for(inti=1;i=n-r;i+)intj=j+r;wij=wij-1+aj+bj;mij=mi+1j;sij=i;for(intk=i+1;k=j;k+)intt=mik-1+mk+1j;if(tmij)mij=t;sij=k;mij+=wij;初始化初始化对角线赋值对角线赋值i为起始元素下标为起始元素下标j为终止元素下标为终止元素下标加第加第j个结点后，个结点后，权值权值w改变改变如第如第i个结点作根的个结点作根的值值取第取第k个结点作根个结点作根5递归计算最优值递归计算最优值416、构造最优解6构造最优解构造最优解427、计算复杂性43练习练习设设n=4，且，且(1,2,3,4)=(do,if,read,while)。又设又设b(1:4)=(3,3,1,1)和和a(0:4)=(2,3,1,1,1)(这些这些b,a都乘了都乘了16。)写出数组写出数组wij,mij,sij及最后的最优及最后的最优二叉搜索树。二叉搜索树。44作业P843-1545ExercisesDeterminethecostandstructureofanoptimalbinarysearchtreeforasetofn=7keyswiththefollowingprobabilities:i:01234567pi0.04,0.06,0.08,0.02,0.10,0.12,0.14qi0.06,0.06,0.06,0.06,0.05,0.05,0.05,0.0546动态规划总结动态规划总结一、动态规划的基本思想：一、动态规划的基本思想：将问题分解为若干小问题，解子问题，然后将问题分解为若干小问题，解子问题，然后从子问题得到原问题的解。从子问题得到原问题的解。47二、动态规划特点二、动态规划特点将问题分解为子问题，这些子问题往往不相将问题分解为子问题，这些子问题往往不相互独立。（如果可以用分治法求解，分解互独立。（如果可以用分治法求解，分解的子问题太多，因此，用分治法时间代价的子问题太多，因此，用分治法时间代价太高，消耗指数时间）太高，消耗指数时间）48三、动态规划思路三、动态规划思路如果能够保存已解决的子问题的答案，而在需要如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。重复计算，节省时间。动态规划方法用一个表来记录所有已解的子问题动态规划方法用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。但它们具有相同的填表格式。49四、动态规划问题的特征：四、动态规划问题的特征：动态规划算法的有效性依赖于问题本身所具有的动态规划算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性两个重要性质：最优子结构性质和子问题重叠性质。质。1、最优子结构：当问题的最优解包含了其子问题、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。的最优解时，称该问题具有最优子结构性质。2、重叠子问题：在用递归算法自顶向下解问题、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。能多地利用这些子问题的解。50五、应用五、应用往往求解具有某种最优性质的问题，此类往往求解具有某种最优性质的问题，此类问题往往具有多个解，我们要找到具有最问题往往具有多个解，我们要找到具有最优值的那个解。优值的那个解。51六、设计动态规划法的步骤：六、设计动态规划法的步骤：1、找出最优解的性质，并刻画其结构特征；、找出最优解的性质，并刻画其结构特征；2、递归地定义最优值（写出动态规划方程）；、递归地定义最优值（写出动态规划方程）；3、以自底向上的方式计算出最优值；、以自底向上的方式计算出最优值；4、根据计算最优值时得到的信息，构造一个最优解。、根据计算最优值时得到的信息，构造一个最优解。步骤步骤1-3是动态规划算法的基本步骤。在只需要求出最是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤优值的情形，步骤4可以省略，步骤可以省略，步骤3中记录的信息中记录的信息也较少；若需要求出问题的一个最优解，则必须执也较少；若需要求出问题的一个最优解，则必须执行步骤行步骤4，步骤，步骤3中记录的信息必须足够多以便构造中记录的信息必须足够多以便构造最优解。最优解。