最优二叉搜索树

1、关于最优二叉搜索树1现在学习的是第一页，共52页23.5 最优二叉搜索树最优二叉搜索树Optimal Binary Search Trees现在学习的是第二页，共52页3 1二叉搜索树二叉搜索树 2最优二叉搜索树最优二叉搜索树 3最优二叉搜索树问题描述最优二叉搜索树问题描述 4最优子结构性质最优子结构性质 5递归计算最优值递归计算最优值 6算法算法现在学习的是第三页，共52页4是一棵空树或者满足以下的性质：是一棵空树或者满足以下的性质： 每个结点作为搜索对象，它的关键字是每个结点作为搜索对象，它的关键字是互不相同互不相同的。的。 对于树上的所有结点，如果它有对于树上的所有结点，如果它有，那么左

2、子树上，那么左子树上所有结点的关键字都所有结点的关键字都小于小于该结点的关键字。该结点的关键字。对于树上的所有结点，如果它有对于树上的所有结点，如果它有，那么右子树上所，那么右子树上所有结点的关键字都有结点的关键字都大于大于该结点的关键字。该结点的关键字。1 二叉搜索树二叉搜索树现在学习的是第四页，共52页5xalwanwilwenwimwulzolyozomxulyumxemyonzi搜索过程：从根结点开始，如果根为空，则搜索搜索过程：从根结点开始，如果根为空，则搜索不成功；否则使用待搜索值与根结点比较，如不成功；否则使用待搜索值与根结点比较，如果待搜索值等于根结点关键字，则搜索成功返果待搜

3、索值等于根结点关键字，则搜索成功返回，如果小于根结点，则向左子树搜索；如果回，如果小于根结点，则向左子树搜索；如果大于根结点，则向右子树搜索。大于根结点，则向右子树搜索。1 二叉搜索树二叉搜索树现在学习的是第五页，共52页6 对于一个给定的关键字集合，可能有若干不同的二对于一个给定的关键字集合，可能有若干不同的二分检索树分检索树 如对保留字的子集如对保留字的子集 Name： 1 2 3 4 5 for if loop repeat while的两棵二分检索树为的两棵二分检索树为ifforwhilelooprepeatifwhilelooprepeatforab考虑考虑a图和图和b图中最坏图中最

4、坏比较次数和平均比较比较次数和平均比较次数次数1 二叉搜索树二叉搜索树现在学习的是第六页，共52页7 构造不同的二叉搜索树构造不同的二叉搜索树就有不同的性能特征。就有不同的性能特征。 二叉搜索树二叉搜索树a在在最坏情况最坏情况下找一个标识符需要下找一个标识符需要4次比较次比较，而，而b表示的二分检索树最坏情况下只需表示的二分检索树最坏情况下只需3次比较次比较。 假设只假设只作成功的检索作成功的检索并且并且检索每个标识符的概率相同检索每个标识符的概率相同，则两，则两棵二分检索树在平均情况下各需要棵二分检索树在平均情况下各需要12/5和和11/5次比较。次比较。ifforwhilelooprepe

5、atifwhilelooprepeatforab1 二叉搜索树二叉搜索树现在学习的是第七页，共52页82、最优二叉搜索树、最优二叉搜索树存在的两个问题存在的两个问题1 在实际中也会遇到在实际中也会遇到不成功不成功检索的情况。检索的情况。2 在实际中，不同标识符会有在实际中，不同标识符会有不同不同的检索概率。的检索概率。 对给定的标识符集合，希望给出构造二分搜索树的对给定的标识符集合，希望给出构造二分搜索树的方法，使得所构造的二分搜索树具有方法，使得所构造的二分搜索树具有最优的性能最优的性能。2 最优二叉搜索树最优二叉搜索树现在学习的是第八页，共52页9 扩充二叉树：当二叉树里出现空的子树时，扩

6、充二叉树：当二叉树里出现空的子树时，就增加新的、特殊的结点就增加新的、特殊的结点空树叶空树叶。对。对于原来二叉树里度数为于原来二叉树里度数为1的分支结点，在它的分支结点，在它下面增加一个空树叶；对于原来二叉树的下面增加一个空树叶；对于原来二叉树的树叶，在它下面增加两个空树叶。树叶，在它下面增加两个空树叶。 扩充二叉树是扩充二叉树是满二叉树满二叉树，新增加的空树叶，新增加的空树叶（以下称外部结点）的个数等于原来二叉（以下称外部结点）的个数等于原来二叉树的结点（以下称内部结点）个数加树的结点（以下称内部结点）个数加1。在实际中也会遇到在实际中也会遇到不成功不成功检索的情况检索的情况2 最优二叉搜索

7、树最优二叉搜索树现在学习的是第九页，共52页10 xalwanwilwenwimwulzolyozomxulyumxemyonziAA代表其值处于代表其值处于wim和和wul之间的可能关键码集合之间的可能关键码集合2 最优二叉搜索树最优二叉搜索树现在学习的是第十页，共52页11 设设 S=x1, x2, , xn 是一个有序集合，且是一个有序集合，且x1, x2, , xn表示有序集合的二叉搜索树利用二叉表示有序集合的二叉搜索树利用二叉树的顶点存储有序集中的元素，而且具有性质：树的顶点存储有序集中的元素，而且具有性质： 存储于每个顶点中的元素存储于每个顶点中的元素x 大于其左子树中任一个大于其

8、左子树中任一个顶点中存储的元素，小于其右子树中任意顶点中存顶点中存储的元素，小于其右子树中任意顶点中存储的元素。二叉树中的叶顶点是形如储的元素。二叉树中的叶顶点是形如(xi, xi+1) 的开的开区间。区间。在二叉搜索树中搜索一个元素在二叉搜索树中搜索一个元素x(1) 在二叉树的内部顶点处找到：在二叉树的内部顶点处找到： x = xi(2) 在二叉树的叶顶点中确定：在二叉树的叶顶点中确定： x (xi , xi+1)2 最优二叉搜索树最优二叉搜索树现在学习的是第十一页，共52页12在实际中，不同标识符会有在实际中，不同标识符会有不同不同的检索概率。的检索概率。 设设Pi是对是对ai检索的概率。

9、检索的概率。 设设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 最优二叉搜索树最优二叉搜索树现在学习的是第十二页，共52页13最优二叉搜索树最优二叉搜索树利用动态规划构造对标识符集合利用动态规划构造对标识符集合a1, a2, , an的的最优二叉搜索树最优二叉搜索树算法算法（包括（包括成功检索成功检索和和不成功检索不成功检索）。）。2 最优二叉搜索树最优二叉搜索树现在学习的是第十三页，共52页

10、14 例例 标识符集标识符集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，求每棵树的平均比较次数（，求每棵树的平均比较次数（成本）。成本）。现在学习的是第十四页，共52页15在检索过程中，每进行一次比较，就进入下面一层，在检索

11、过程中，每进行一次比较，就进入下面一层， 对于成功的检索，对于成功的检索，比较的次数就是所在的层数加比较的次数就是所在的层数加1。 对于不成功的检索，被检索的关键码属于那个外部结对于不成功的检索，被检索的关键码属于那个外部结点代表的可能关键码集合，点代表的可能关键码集合，比较次数就等于此外部结比较次数就等于此外部结点的层数。点的层数。2 最优二叉搜索树最优二叉搜索树现在学习的是第十五页，共52页16例：P1=0.5, P2=0.1, P3=0.05, q0=0.15, q1=0.1, q2=0.05, q3=0.05123q0q1q2q3123q0q1q2q3q0123q1q2q3123q0q

12、1q2q3123q0q1q2q3考虑平均搜索次数，也叫做考虑平均搜索次数，也叫做平均路长平均路长Pa(n)=1 p1 + 2 p2+3 p3 + 1q0 +2q1+ 3( q2 + q3 ) =1 0.5+ 2 0.1+3 0.05 + 10.05 +20.1+ 3( 0.05 + 0.05 ) =1.52 最优二叉搜索树最优二叉搜索树a b c d e现在学习的是第十六页，共52页17分析对于图的内结点而言，第对于图的内结点而言，第0层需要比较操作次数为层需要比较操作次数为1，第，第1层需要比较层需要比较2次，第次，第2层需要层需要3次次Pb(n)=1 p1 + 2 p3+3 p2 + 1q

13、0 + 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 p

14、3 + 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 最优二叉搜索树最优二叉搜索树现在学习的是第十七页，共52页18 找到元素找到元素x = xi的概率为的概率为bi；确定；确定x (xi , xi+1)的概的概率为率为ai。其中约定其中约定x0= , xn+1= + ,有有2 最优二叉搜索树最优二叉搜索树现在学习的是第十八页，共52页19 在一个表示在一个表示S的二叉树的二叉树T中，设存储元素中，设存储元素xi的结点深度的结点深度为为ci；

15、叶结点（；叶结点（xj，xj1）的结点深度为）的结点深度为dj 。 表示在二叉搜索树表示在二叉搜索树T中作一次搜索所需的平均比较中作一次搜索所需的平均比较次数。次数。P又称为二叉搜索树又称为二叉搜索树T的平均路长，在一般情的平均路长，在一般情况下，不同的二叉搜索树的平均路长是不同的。况下，不同的二叉搜索树的平均路长是不同的。2 最优二叉搜索树最优二叉搜索树现在学习的是第十九页，共52页203、最优二叉搜索树问题描述、最优二叉搜索树问题描述 对于有序集对于有序集S及其存取概率分布及其存取概率分布 （a0, b1, a1, , bn, an），在所有表示有序集），在所有表示有序集S的二叉搜索树中找

16、出一棵具有最小平均路的二叉搜索树中找出一棵具有最小平均路长的二叉搜索树。长的二叉搜索树。 结点在二叉搜索树中的层次越深，需要比结点在二叉搜索树中的层次越深，需要比较的次数就越多，因此要构造一棵最小二较的次数就越多，因此要构造一棵最小二叉树，一般尽量把搜索概率较高的结点放叉树，一般尽量把搜索概率较高的结点放在较高的层次。在较高的层次。3 最优二叉搜索树问题最优二叉搜索树问题现在学习的是第二十页，共52页214、最优子结构性质、最优子结构性质 假设选择假设选择 k为树根，则为树根，则 1, 2, , k-1 和和a0, a1, , ak-1 都将位于左子树都将位于左子树 L 上，其余上，其余结点结

17、点 (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 最优子结构性质最优子结构性质现在学习的是第二十一页，共52页22511472063353976425431399844 最优子结构性质最优子结构性质现在学习的是第二十二页，共52页23511472063353976425431399844 最优子结构性质最优子结构性质现在学习的是第二十三页，共52页24 设设COST(L) 和和COST(R) 分别是二分检索树分别是二分检索树T的左子树和右

18、子树的的左子树和右子树的成本。成本。 则检索树则检索树T的成本是：的成本是： P(k)+ COST(L) + COST(R) + 若若 T 是最优的，则上式及是最优的，则上式及 COST(L) 和和COST(R) 必定都取最小值。必定都取最小值。4 最优子结构性质最优子结构性质现在学习的是第二十四页，共52页25最优子结构性质证明最优子结构性质证明 二叉搜索树二叉搜索树T 的一棵含有顶点的一棵含有顶点xi , , xj和叶顶点和叶顶点 (xi-1 , xi ) , , ( xj , xj+1)的子树可以看作是有序集的子树可以看作是有序集 xi , , xj 关于全集为关于全集为 xi-1 ,

19、xj1 的一棵二叉搜索树的一棵二叉搜索树（T 自身可以看作是有序集自身可以看作是有序集) 。根据根据S 的存取分布概率，在子树的顶点处被搜索到的概的存取分布概率，在子树的顶点处被搜索到的概率是：率是：4 最优子结构性质最优子结构性质现在学习的是第二十五页，共52页26jipwpww)(pww)(pwpwr,jmli,mijr,jmm,mli,mijij 111111左子树的左子树的搜索概率搜索概率右子树右子树的搜索的搜索概率概率设设Tij是有序集是有序集xi , , xj关于存储概率分布为关于存储概率分布为ai-1, bi, , bj, aj 的一棵最优二叉搜索树，其平均路长为的一棵最优二叉搜

20、索树，其平均路长为pij，Tij的根顶点存储的元素的根顶点存储的元素xm，其左子树，其左子树Tl和右子树和右子树Tr的平的平均路长分别为均路长分别为pl和和pr。由于。由于Tl和和Tr中顶点深度是它们在中顶点深度是它们在Tij中中的深度减的深度减1，所以得到，所以得到xi , , xj的存储概率分布为的存储概率分布为ai-1, bi, , bj, aj ，其，其中，中，ah，bk分别是下面的条件概率：分别是下面的条件概率：4 最优子结构性质最优子结构性质现在学习的是第二十六页，共52页27构造最优二叉搜索树时，可以选择构造最优二叉搜索树时，可以选择先构造其左右子树，使其左右子树先构造其左右子树

21、，使其左右子树最优，然后构造整棵树。最优，然后构造整棵树。4 最优子结构性质最优子结构性质现在学习的是第二十七页，共52页285、递归计算最优值 最优二叉搜索树最优二叉搜索树Tij的平均路长为的平均路长为pij，则所求的，则所求的最优值为最优值为p1,n。由二叉树的花费公式。由二叉树的花费公式 根据最优二叉搜索树问题的最优子结构性质可根据最优二叉搜索树问题的最优子结构性质可建立计算建立计算pij的递归式如下的递归式如下初始时初始时jipwpww)(pww)(pwpw,jk,jki,ki,kij,jk,jkk,ki,ki,kijij 11111111115 递归计算最优值递归计算最优值现在学习的

22、是第二十八页，共52页29记记 wi,j pi,j 为为m( i, j ) 递归计算最优值递归计算最优值5 递归计算最优值递归计算最优值现在学习的是第二十九页，共52页30根据该公式，计算树根据该公式，计算树Tij的花费只用到了的花费只用到了Tik-1，Tk+1j, 可得到具体求解过程如下：可得到具体求解过程如下：1）构造只有）构造只有1个内部结点的最优二叉搜索树个内部结点的最优二叉搜索树T11,T22, Tnn，可以求得，可以求得mii 同时同时可以用一个数组存做根结点元素为：可以用一个数组存做根结点元素为： s11=1, s22=2snn=n2) 构造具有构造具有2个内部结点的最优二叉搜索

23、树个内部结点的最优二叉搜索树现在学习的是第三十页，共52页31例 给出标识符集给出标识符集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 递归计算最优值递归计算最优值现在学习的是第三十一页，共52页32q0=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.253q2q

24、3T33w33=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=0现在学习的是第三十二页，共52页33q0=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.253q2q3T33

25、w33=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.6现在学习的是第三十三页，共52页34q0=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.1512q0q1q212q0q1q2T1

26、2w12=0.9m12=0.9+ m11+m32 =1.65w12=0.9m12=0.9+ m10+m22 =1.1523q1q2q323q1q2q3T23w23=0. 35m23=0.5m23=0.6现在学习的是第三十四页，共52页35T12m12=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.05现在学习的是第三十五页，共52页36T12m1

27、2=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.05现在学习的是第三十六页，共52页370123123000040 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.1

28、5, P1=0.5, q1=0.1, P2=0.1, q2=0.05, P3=0.05, q3=0.05现在学习的是第三十七页，共52页38具体求解过程具体求解过程递归出口，没有内部节点时，构造递归出口，没有内部节点时，构造T10 T21,T32，Tn+1n2) 构造具有构造具有2个、个、3个、个、n个内部结点的最优二叉搜索个内部结点的最优二叉搜索树树r （ 起止下标的差）起止下标的差）0 T11, T22 , ， Tnn，1 T12, T23, ，Tn-1n，2 T13, T24, ，Tn-2n，r T1r+1, T2r+2, ，Tii+r，Tn-rnn-1 T1n 5 递归计算最优值递归计

29、算最优值现在学习的是第三十八页，共52页39void OBST ( int *a, int *b,int n, int *m, int *s, int *w) for( int i=0; i=n; i+) wi+1i=ai; mi+1i=0; /初始化，构造没有内部节点时的情况初始化，构造没有内部节点时的情况for(int r=0; rn; r+) for(int i =1; i=n-r; i+) int j= i+r; 构造构造Tij，填写，填写wij,mij,sij 现在学习的是第三十九页，共52页40构造构造TijTij表示用第表示用第i到第到第j个内部节点构造的树，做根的结点可个内部节

30、点构造的树，做根的结点可以是第以是第i，i+1,j中任意一个。中任意一个。1) 首选首选i作为根，其左子树空，右子树为结点作为根，其左子树空，右子树为结点i+1,i+2j构成即构成即Ti+1j。 mij=wij+0+mi+1j sij= i2) 不选不选i做根，设做根，设k为其根，则为其根，则k= i+1,j,左子树为结点左子树为结点i, i+1,k-1, 右子树为右子树为k+1, k+2, ,j t= wij+mik-1+mk+1j if(t mij) mij=t; sij=k; 3)k= k+1, 跳回跳回25 递归计算最优值递归计算最优值现在学习的是第四十页，共52页41void Opt

31、imalBinarySearchTree( int *a, int *b,int n, int *m, int *s, int *w) for( int i=0; i=n; i+) wi+1i=ai; mi+1i=0; for(int r=0; rn; r+) for(int i =1; i= n - r; i+) int j= j + r; wij=wij-1+aj+bj; mij=mi+1j; sij = i; for(int k = i+1; k=j; k+) int t=mik-1+mk+1j; if (tmij) mij=t; sij=k; mij+=wij; 初始化初始化对角线赋值

32、对角线赋值i为起始元素下标为起始元素下标j为终止元素下标为终止元素下标加第加第j个结点后，个结点后，权值权值w改变改变如第如第i个结点作根的个结点作根的值值取第取第k个结点作根个结点作根5 递归计算最优值递归计算最优值现在学习的是第四十一页，共52页426、构造最优解6 构造最优解构造最优解现在学习的是第四十二页，共52页437、计算复杂性现在学习的是第四十三页，共52页44练习练习设设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都乘了都乘

33、了16。) 写出数组写出数组wij,mij,sij及最后的最优及最后的最优二叉搜索树。二叉搜索树。现在学习的是第四十四页，共52页45作业P84 3-15现在学习的是第四十五页，共52页46Exercises Determine the cost and structure of an optimal binary search tree for a set of n = 7 keys with the following probabilities:i :01234567pi 0.04,0.06,0.08,0.02,0.10,0.12,0.14qi 0.06,0.06,0.06,0.06,0.05,0.05,0.05,0.05现在学习的是第四十六页，共52页47动态规划总结动态规划总结一、动态规划的基本思想：一、动态规划的基本思想： 将问题分解为若干小问题，解子问题，然后将问题分解为若干小问题，解子问题，然后从子问题得到原问题的解。从子问题得到原问题的解。