算法設(shè)計(jì)與分析 課件 5.9-動態(tài)規(guī)劃應(yīng)用-最優(yōu)二叉搜索樹

信息工程大學(xué)算法設(shè)計(jì)與分析動態(tài)規(guī)劃—最優(yōu)二叉搜索樹國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版二叉搜索樹的定義：（1）是一棵二叉樹；（2）若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；（3）若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；（4）它的左、右子樹也分別為二叉搜索樹。4512533100在二叉搜索樹上查找不成功所需的比較次數(shù)是：虛擬結(jié)點(diǎn)的深度在二叉搜索樹上查找成功所需的比較次數(shù)是：結(jié)點(diǎn)的深度+1查找100的過程：與45比較；與53比較；與100比較；查找成功。查找40的過程：與45比較；與12比較；查找不成功。4553123100<33<x<1212<x<4545<x<53x>10053<x<100a1a2a3a4a5b0b1b2b3b4b5單選題。在下圖所示的二叉搜索樹上，查找90需要比較的次數(shù)是（）。A.3B.4C.24553123100<33<x<1212<x<4545<x<53x>10053<x<100a1a2a3a4a5b0b1b2b3b4b5

實(shí)例：假定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個(gè)結(jié)點(diǎn)的二叉搜索樹的個(gè)數(shù)為P(n)，由于每個(gè)二叉搜索樹都可以分解為左子樹、根和右子樹，而左、右子樹都是二叉搜索樹，因此有：最優(yōu)二叉搜索樹滿足最優(yōu)子結(jié)構(gòu)性質(zhì)嗎？假設(shè)右圖是在給定序列S=<k1,k2,k3,k4,k5>,搜索概率為P=<q0,p1,q1,p2,q2,…,p5,q5>的最優(yōu)二叉搜索樹，那么其左子樹是以序列S1=<k1>及相應(yīng)概率對應(yīng)的最優(yōu)二叉搜索樹，其右子樹是以序列S2=<k3,k4,k5>及相應(yīng)概率對應(yīng)的最優(yōu)二叉搜索樹。反證法證明。定義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)：

對應(yīng)S(i,j)和P(i,j)的最優(yōu)二叉搜索樹的平均比較次數(shù)。1.找出最優(yōu)解性質(zhì)，刻畫結(jié)構(gòu)特征2.遞歸地定義最優(yōu)值3.以自底向上的方式計(jì)算最優(yōu)值123…n123…nm(i,j)1個(gè)結(jié)點(diǎn)2個(gè)結(jié)點(diǎn)3個(gè)結(jié)點(diǎn)…n個(gè)結(jié)點(diǎn)實(shí)例：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）首先計(jì)算1個(gè)結(jié)點(diǎn)的二叉搜索樹的平均比較次數(shù)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）計(jì)算有2個(gè)結(jié)點(diǎn)的二叉搜索樹的最少平均比較次數(shù)m(1,2)、m(2,3)、m(3,4)、m(4,5)。實(shí)例：S=<3,12,45,53,100>。124512<x<4545<x<53a23<x<1212<x<4545123<x<1245<x<53m(2,3)：以a2為根結(jié)點(diǎn)a2a3a3b1b2b3b1b2b3m(2,3)：以a3為根結(jié)點(diǎn)（3）計(jì)算有3個(gè)結(jié)點(diǎn)的二叉搜索樹的最少平均比較次數(shù)m(1,3)、m(2,4)、m(3,5)。實(shí)例：S=<3,12,45,53,100>。1253a2a4b1b4b1b35312a4a2b4a345b2b345a3a453b4b312a2b1b245a3b2m(2,4)：以a4為根結(jié)點(diǎn)m(2,4)：以a3為根結(jié)點(diǎn)m(2,4)：以a2為根結(jié)點(diǎn)實(shí)例：S=<3,12,45,53,100>。（4）計(jì)算有4個(gè)結(jié)點(diǎn)的二叉搜索樹的最少平均比較次數(shù)m(1,4)、m(2,5)。1253a2a4b1b1b35312a4a2b4a345b2b345a3a453b5b312a2b1b245a3b2a5100b5100a5b4100a5b5b4100b1b345a5a212a3b253a4b5b4m(2,5)：以a2為根結(jié)點(diǎn)m(2,5)：以a3為根結(jié)點(diǎn)m(2,5)：以a4為根結(jié)點(diǎn)m(2,5)：以a5為根結(jié)點(diǎn)

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實(shí)例：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數(shù)組

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

2233i=3

344i=4

44i=5

54.根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解記錄q(i,j)=k，k是m(i,j)獲得最小值時(shí)對應(yīng)的根結(jié)點(diǎ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>。q數(shù)組voidoptimalBT(double*p，double*w,intn，double**m，int**q){……w[0]=0;for(i=1;i<=n;i++){/*計(jì)算w[i]*/w[i]=w[i-1]+p[2*i-2]+p[2*i-1];for(i=1;i<=n;i++){/*初始化結(jié)點(diǎn)數(shù)目為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++){/*結(jié)點(diǎn)數(shù)目從2到n*/for(i=1;i<=n-r+1;i++){/*i表示結(jié)點(diǎn)的起始編號*/j=i+r-1;/*j表示結(jié)點(diǎn)的終止編號*/

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;/*計(jì)算根結(jié)點(diǎn)編號是i+1~j處的平均比較次數(shù)，并記錄根結(jié)點(diǎn)編號*/for(k=i+1;k<=j;k++){t=m[i][k-1]+m[k+1][j]+w_i_j;/*找到較小比較次數(shù)，更新