最優(yōu)二叉搜索樹

關(guān)于最優(yōu)二叉搜索樹第一頁，共五十二頁，2022年，8月28日13.5最優(yōu)二叉搜索樹

OptimalBinarySearchTrees第二頁，共五十二頁，2022年，8月28日21二叉搜索樹2最優(yōu)二叉搜索樹3最優(yōu)二叉搜索樹問題描述4最優(yōu)子結(jié)構(gòu)性質(zhì)5遞歸計算最優(yōu)值6算法第三頁，共五十二頁，2022年，8月28日3是一棵空樹或者滿足以下的性質(zhì)：每個結(jié)點作為搜索對象，它的關(guān)鍵字是互不相同的。對于樹上的所有結(jié)點，如果它有左子樹，那么左子樹上所有結(jié)點的關(guān)鍵字都小于該結(jié)點的關(guān)鍵字。對于樹上的所有結(jié)點，如果它有右子樹，那么右子樹上所有結(jié)點的關(guān)鍵字都大于該結(jié)點的關(guān)鍵字。1二叉搜索樹第四頁，共五十二頁，2022年，8月28日4xalwanwilwenwimwulzolyozomxulyumxemyonzi搜索過程：從根結(jié)點開始，如果根為空，則搜索不成功；否則使用待搜索值與根結(jié)點比較，如果待搜索值等于根結(jié)點關(guān)鍵字，則搜索成功返回，如果小于根結(jié)點，則向左子樹搜索；如果大于根結(jié)點，則向右子樹搜索。1二叉搜索樹第五頁，共五十二頁，2022年，8月28日5對于一個給定的關(guān)鍵字集合，可能有若干不同的二分檢索樹如對保留字的子集

Name：12345foriflooprepeatwhile的兩棵二分檢索樹為ifforwhilelooprepeatifwhilelooprepeatforab考慮a圖和b圖中最壞比較次數(shù)和平均比較次數(shù)1二叉搜索樹第六頁，共五十二頁，2022年，8月28日6

構(gòu)造不同的二叉搜索樹就有不同的性能特征。二叉搜索樹a在最壞情況下找一個標(biāo)識符需要4次比較，而b表示的二分檢索樹最壞情況下只需3次比較。假設(shè)只作成功的檢索并且檢索每個標(biāo)識符的概率相同，則兩棵二分檢索樹在平均情況下各需要12/5和11/5次比較。ifforwhilelooprepeatifwhilelooprepeatforab1二叉搜索樹第七頁，共五十二頁，2022年，8月28日72、最優(yōu)二叉搜索樹存在的兩個問題1在實際中也會遇到不成功檢索的情況。2在實際中，不同標(biāo)識符會有不同的檢索概率。對給定的標(biāo)識符集合，希望給出構(gòu)造二分搜索樹的方法，使得所構(gòu)造的二分搜索樹具有最優(yōu)的性能。2最優(yōu)二叉搜索樹第八頁，共五十二頁，2022年，8月28日8擴充二叉樹：當(dāng)二叉樹里出現(xiàn)空的子樹時，就增加新的、特殊的結(jié)點——空樹葉。對于原來二叉樹里度數(shù)為1的分支結(jié)點，在它下面增加一個空樹葉；對于原來二叉樹的樹葉，在它下面增加兩個空樹葉。擴充二叉樹是滿二叉樹，新增加的空樹葉（以下稱外部結(jié)點）的個數(shù)等于原來二叉樹的結(jié)點（以下稱內(nèi)部結(jié)點）個數(shù)加1。在實際中也會遇到不成功檢索的情況2最優(yōu)二叉搜索樹第九頁，共五十二頁，2022年，8月28日9xalwanwilwenwimwulzolyozomxulyumxemyonziAA代表其值處于wim和wul之間的可能關(guān)鍵碼集合2最優(yōu)二叉搜索樹第十頁，共五十二頁，2022年，8月28日10設(shè)S={x1,x2,···,xn}是一個有序集合，且x1,x2,···,xn表示有序集合的二叉搜索樹利用二叉樹的頂點存儲有序集中的元素，而且具有性質(zhì)：存儲于每個頂點中的元素x

大于其左子樹中任一個頂點中存儲的元素，小于其右子樹中任意頂點中存儲的元素。二叉樹中的葉頂點是形如(xi,xi+1)

的開區(qū)間。在二叉搜索樹中搜索一個元素x(1)在二叉樹的內(nèi)部頂點處找到：x=xi(2)在二叉樹的葉頂點中確定：x∈(xi,xi+1)2最優(yōu)二叉搜索樹第十一頁，共五十二頁，2022年，8月28日11在實際中，不同標(biāo)識符會有不同的檢索概率。

設(shè)Pi是對ai檢索的概率。設(shè)qi是對滿足ai<X<ai+1,0in的標(biāo)識符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最優(yōu)二叉搜索樹第十二頁，共五十二頁，2022年，8月28日12最優(yōu)二叉搜索樹利用動態(tài)規(guī)劃構(gòu)造對標(biāo)識符集合{a1,a2,…,an}的最優(yōu)二叉搜索樹算法（包括成功檢索和不成功檢索）。2最優(yōu)二叉搜索樹第十三頁，共五十二頁，2022年，8月28日13例標(biāo)識符集{1,2,3}＝{do,if,stop}可能的二分檢索樹為：(a)321

231

(c)312(d)

(b)312

321

(e)設(shè)每個內(nèi)、外結(jié)點檢索的概率相同：pi=qi=1/7，求每棵樹的平均比較次數(shù)（成本）。若P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05，求每棵樹的平均比較次數(shù)（成本）。第十四頁，共五十二頁，2022年，8月28日14在檢索過程中，每進行一次比較，就進入下面一層，對于成功的檢索，比較的次數(shù)就是所在的層數(shù)加1。對于不成功的檢索，被檢索的關(guān)鍵碼屬于那個外部結(jié)點代表的可能關(guān)鍵碼集合，比較次數(shù)就等于此外部結(jié)點的層數(shù)。2最優(yōu)二叉搜索樹第十五頁，共五十二頁，2022年，8月28日15例：P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05123q0q1q2q3123q0q1q2q3q0123q1q2q3123q0q1q2q3123q0q1q2q3考慮平均搜索次數(shù)，也叫做平均路長Pa(n)=1×p1+2×p2+3×p3+1×q0+2×q1+3×(q2+q3)=1×0.5+2×0.1+3×0.05+1×0.05+2×0.1+3×(0.05+0.05)=1.52最優(yōu)二叉搜索樹abcde第十六頁，共五十二頁，2022年，8月28日16分析對于圖的內(nèi)結(jié)點而言，第0層需要比較操作次數(shù)為1，第1層需要比較2次，第2層需要3次Pb(n)=1×p1+2×p3+3×p2+1×q0+3×(q2+q3)=1×0.5+2×0.05+3×0.1

+1×0.15

+2×0.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+1×0.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+1×0.05+2×0.15+3×(0.1+0.05)=2.152最優(yōu)二叉搜索樹第十七頁，共五十二頁，2022年，8月28日17找到元素x=xi的概率為bi；確定x∈(xi,xi+1)的概率為ai。其中約定x0=－∞,xn+1=+∞,有2最優(yōu)二叉搜索樹第十八頁，共五十二頁，2022年，8月28日18在一個表示S的二叉樹T中，設(shè)存儲元素xi的結(jié)點深度為ci；葉結(jié)點（xj，xj＋1）的結(jié)點深度為dj

。表示在二叉搜索樹T中作一次搜索所需的平均比較次數(shù)。P又稱為二叉搜索樹T的平均路長，在一般情況下，不同的二叉搜索樹的平均路長是不同的。2最優(yōu)二叉搜索樹第十九頁，共五十二頁，2022年，8月28日193、最優(yōu)二叉搜索樹問題描述對于有序集S及其存取概率分布（a0,b1,a1,···,bn,an），在所有表示有序集S的二叉搜索樹中找出一棵具有最小平均路長的二叉搜索樹。結(jié)點在二叉搜索樹中的層次越深，需要比較的次數(shù)就越多，因此要構(gòu)造一棵最小二叉樹，一般盡量把搜索概率較高的結(jié)點放在較高的層次。3最優(yōu)二叉搜索樹問題第二十頁，共五十二頁，2022年，8月28日204、最優(yōu)子結(jié)構(gòu)性質(zhì)假設(shè)選擇k為樹根，則1,2,…,k-1和a0,a1,…,ak-1

都將位于左子樹L上，其余結(jié)點(k+1,…,n和ak,ak+1,…,an)位于右子樹R上。k

L

R1,2,…,k-1

a0,a1,…,ak-1k+1,…,n

ak,ak+1,…,an4最優(yōu)子結(jié)構(gòu)性質(zhì)第二十一頁，共五十二頁，2022年，8月28日21511472063353976425431399844最優(yōu)子結(jié)構(gòu)性質(zhì)第二十二頁，共五十二頁，2022年，8月28日22511472063353976425431399844最優(yōu)子結(jié)構(gòu)性質(zhì)第二十三頁，共五十二頁，2022年，8月28日23設(shè)COST(L)

和COST(R)

分別是二分檢索樹T的左子樹和右子樹的成本。則檢索樹T的成本是：

P(k)+COST(L)+COST(R)+……若T

是最優(yōu)的，則上式及COST(L)和COST(R)必定都取最小值。4最優(yōu)子結(jié)構(gòu)性質(zhì)第二十四頁，共五十二頁，2022年，8月28日24最優(yōu)子結(jié)構(gòu)性質(zhì)證明二叉搜索樹T的一棵含有頂點xi,···,xj和葉頂點

(xi-1,xi),···,(xj,xj+1)的子樹可以看作是有序集{xi,···,xj}關(guān)于全集為{xi-1,xj＋1

}的一棵二叉搜索樹（T自身可以看作是有序集)。根據(jù)S

的存取分布概率，在子樹的頂點處被搜索到的概率是：4最優(yōu)子結(jié)構(gòu)性質(zhì)第二十五頁，共五十二頁，2022年，8月28日25左子樹的搜索概率右子樹的搜索概率設(shè)Tij是有序集{xi

,···,xj}關(guān)于存儲概率分布為{ai-1,bi,

…,bj,aj}的一棵最優(yōu)二叉搜索樹，其平均路長為pij，Tij的根頂點存儲的元素xm，其左子樹Tl和右子樹Tr的平均路長分別為pl和pr。由于Tl和Tr中頂點深度是它們在Tij中的深度減1，所以得到{xi

,···,xj}的存儲概率分布為{ai-1,bi,

…,bj,aj}，其中，ah，bk分別是下面的條件概率：4最優(yōu)子結(jié)構(gòu)性質(zhì)第二十六頁，共五十二頁，2022年，8月28日26構(gòu)造最優(yōu)二叉搜索樹時，可以選擇先構(gòu)造其左右子樹，使其左右子樹最優(yōu)，然后構(gòu)造整棵樹。4最優(yōu)子結(jié)構(gòu)性質(zhì)第二十七頁，共五十二頁，2022年，8月28日275、遞歸計算最優(yōu)值最優(yōu)二叉搜索樹Tij的平均路長為pij，則所求的最優(yōu)值為p1,n。由二叉樹的花費公式根據(jù)最優(yōu)二叉搜索樹問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可建立計算pij的遞歸式如下初始時5遞歸計算最優(yōu)值第二十八頁，共五十二頁，2022年，8月28日28記wi,jpi,j為m(i,j)

遞歸計算最優(yōu)值5遞歸計算最優(yōu)值第二十九頁，共五十二頁，2022年，8月28日29根據(jù)該公式，計算樹T[i][j]的花費只用到了T[i][k-1]，T[k+1][j],可得到具體求解過程如下：1）構(gòu)造只有1個內(nèi)部結(jié)點的最優(yōu)二叉搜索樹T[1][1],T[2][2]…,T[n][n]，可以求得m[i][i]同時可以用一個數(shù)組存做根結(jié)點元素為：

s[1][1]=1,s[2][2]=2…s[n][n]=n2)構(gòu)造具有2個內(nèi)部結(jié)點的最優(yōu)二叉搜索樹第三十頁，共五十二頁，2022年，8月28日30例給出標(biāo)識符集{1,2,3}＝{do,if,stop}存取概率若P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05構(gòu)造一棵最優(yōu)二叉搜索樹5遞歸計算最優(yōu)值第三十一頁，共五十二頁，2022年，8月28日31q0=0.15,P1=0.5,q1=0.1,P2=0.1,q2=0.05,P3=0.05,q3=0.051q0q1T[1][1]w[1][1]=0.75m[1][1]=0.752q1q2T[2][2]w[2][2]=0.25m[2][2]=0.253q2q3T[3][3]w[3][3]=0.15m[3][3]=0.1512q0q1q212q0q1q2T[1][2]w[1][2]=0.9m[1][2]=0.9+m[1][1]+m[3][2]=1.65w[1][2]=0.9m[1][2]=0.9+m[1][0]+m[2][2]=1.15q0T[1][0]w[1][0]=0.15m[1][0]=0q1T[2][1]w[2][1]=0.1m[2][1]=0q2T[3][2]w[3][2]=0.05m[3][2]=0q3T[4][3]w[4][3]=0.05m[4][3]=0第三十二頁，共五十二頁，2022年，8月28日32q0=0.15,P1=0.5,q1=0.1,P2=0.1,q2=0.05,P3=0.05,q3=0.051q0q1T[1][1]w[1][1]=0.75m[1][1]=0.752q1q2T[2][2]w[2][2]=0.25m[2][2]=0.253q2q3T[3][3]w[3][3]=0.15m[3][3]=0.1512q0q1q212q0q1q2T[1][2]w[1][2]=0.9m[1][2]=0.9+m[1][1]+m[3][2]=1.65w[1][2]=0.9m[1][2]=0.9+m[1][0]+m[2][2]=1.1523q1q2q323q1q2q3T[2][3]w[2][3]=0.5m[2][3]=0.5m[2][3]=0.6第三十三頁，共五十二頁，2022年，8月28日33q0=0.15,P1=0.5,q1=0.1,P2=0.1,q2=0.05,P3=0.05,q3=0.051q0q1T[1][1]w[1][1]=0.75m[1][1]=0.752q1q2T[2][2]w[2][2]=0.25m[2][2]=0.253q2q3T[3][3]w[3][3]=0.15m[3][3]=0.1512q0q1q212q0q1q2T[1][2]w[1][2]=0.9m[1][2]=0.9+m[1][1]+m[3][2]=1.65w[1][2]=0.9m[1][2]=0.9+m[1][0]+m[2][2]=1.1523q1q2q323q1q2q3T[2][3]w[2][3]=0.35m[2][3]=0.5m[2][3]=0.6第三十四頁，共五十二頁，2022年，8月28日34T[1][2]m[1][2]=1.1512q0q1q223q1q2q3T[2][3]m[2][3]=0.523q2q31q0q1T[1][3]W[1][3]=1m[1][3]=1.523q2q31q0q1m[1][3]=1.923q2q31q0q1m[1][3]=2.15q0=0.15,P1=0.5,q1=0.1,P2=0.1,q2=0.05,P3=0.05,q3=0.05第三十五頁，共五十二頁，2022年，8月28日35T[1][2]m[1][2]=1.1512q0q1q223q1q2q3T[2][3]m[2][3]=0.523q2q31q0q1T[1][3]W[1][3]=1m[1][3]=1.523q2q31q0q1m[1][3]=1.923q2q31q0q1m[1][3]=2.15q0=0.15,P1=0.5,q1=0.1,P2=0.1,q2=0.05,P3=0.05,q3=0.05第三十六頁，共五十二頁，2022年，8月28日3601231230000401231234W(i,j)0123123400000.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.05第三十七頁，共五十二頁，2022年，8月28日37具體求解過程遞歸出口，沒有內(nèi)部節(jié)點時，構(gòu)造T[1][0]T[2][1],T[3][2]……，T[n+1][n]2)構(gòu)造具有2個、3個、……、n個內(nèi)部結(jié)點的最優(yōu)二叉搜索樹r

（起止下標(biāo)的差）0T[1][1],T[2][2],…，T[n][n]，1T[1][2],T[2][3],…，T[n-1][n]，2T[1][3],T[2][4],…，T[n-2][n]，rT[1][r+1],T[2][r+2],…，T[i][i+r]，…，T[n-r][n]n-1T[1][n]5遞歸計算最優(yōu)值第三十八頁，共五十二頁，2022年，8月28日38voidOBST(int*a,int*b,intn,int**m,int**s,int**w)

{for(inti=0;i<=n;i++){w[i+1][i]=a[i];m[i+1][i]=0;}//初始化，構(gòu)造沒有內(nèi)部節(jié)點時的情況for(intr=0;r<n;r++)for(inti=1;i<=n-r;i++){intj=i+r;

構(gòu)造T[i][j]，填寫w[i][j],m[i][j],s[i][j]}}第三十九頁，共五十二頁，2022年，8月28日39構(gòu)造T[i][j]T[i][j]表示用第i到第j個內(nèi)部節(jié)點構(gòu)造的樹，做根的結(jié)點可以是第i，i+1,…,j中任意一個。1)首選i作為根，其左子樹空，右子樹為結(jié)點i+1,i+2…j構(gòu)成即T[i+1][j]。

m[i][j]=w[i][j]+0+m[i+1][j]s[i][j]=i2)不選i做根，設(shè)k為其根，則k=i+1,…,j,左子樹為結(jié)點i,i+1,…,k-1,右子樹為k+1,k+2,…,jt=w[i][j]+m[i][k-1]+m[k+1][j]if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}3)k=k+1,跳回25遞歸計算最優(yōu)值第四十頁，共五十二頁，2022年，8月28日40voidOptimalBinarySearchTree(int*a,int*b,intn,int**m,int**s,int**w){for(inti=0;i<=n;i++){w[i+1][i]=a[i];m[i+1][i]=0;}for(intr=0;r<n;r++)for(inti=1;i<=n-r;i++){intj=j+r;w[i][j]=w[i][j-1]+a[j]+b[j];m[i][j]=m[i+1][j];s[i][j]=i;

for(intk=i+1;k<=j;k++){intt=m[i][k-1]+m[k+1][j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}m[i][j]+=w[i][j];}}初始化對角線賦值i為起始元素下標(biāo)j為終止元素下標(biāo)加第j個結(jié)點后，權(quán)值w改變?nèi)绲趇個結(jié)點作根的值取第k個結(jié)點作根5遞歸計算最優(yōu)值第四十一頁，共五十二頁，2022年，8月28日416、構(gòu)造最優(yōu)解6構(gòu)造最優(yōu)解第四十二頁，共五十二頁，2022年，8月28日427、計算復(fù)雜性第四十三頁，共五十二頁，2022年，8月28日43練習(xí)設(shè)n=4，且

(1,2,3,4)=(do,if,read,