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

關(guān)于最優(yōu)二叉搜索樹(shù)1第一頁(yè)，共五十二頁(yè)，編輯于2023年，星期一23.5最優(yōu)二叉搜索樹(shù)

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

Name：12345foriflooprepeatwhile的兩棵二分檢索樹(shù)為ifforwhilelooprepeatifwhilelooprepeatforab考慮a圖和b圖中最壞比較次數(shù)和平均比較次數(shù)1二叉搜索樹(shù)第六頁(yè)，共五十二頁(yè)，編輯于2023年，星期一7

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

大于其左子樹(shù)中任一個(gè)頂點(diǎn)中存儲(chǔ)的元素，小于其右子樹(shù)中任意頂點(diǎn)中存儲(chǔ)的元素。二叉樹(shù)中的葉頂點(diǎn)是形如(xi,xi+1)

的開(kāi)區(qū)間。在二叉搜索樹(shù)中搜索一個(gè)元素x(1)在二叉樹(shù)的內(nèi)部頂點(diǎn)處找到：x=xi(2)在二叉樹(shù)的葉頂點(diǎn)中確定：x∈(xi,xi+1)2最優(yōu)二叉搜索樹(shù)第十一頁(yè)，共五十二頁(yè)，編輯于2023年，星期一12在實(shí)際中，不同標(biāo)識(shí)符會(huì)有不同的檢索概率。

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

231

(c)312(d)

(b)312

321

(e)設(shè)每個(gè)內(nèi)、外結(jié)點(diǎn)檢索的概率相同：pi=qi=1/7，求每棵樹(shù)的平均比較次數(shù)（成本）。若P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05，求每棵樹(shù)的平均比較次數(shù)（成本）。第十四頁(yè)，共五十二頁(yè)，編輯于2023年，星期一15在檢索過(guò)程中，每進(jìn)行一次比較，就進(jìn)入下面一層，對(duì)于成功的檢索，比較的次數(shù)就是所在的層數(shù)加1。對(duì)于不成功的檢索，被檢索的關(guān)鍵碼屬于那個(gè)外部結(jié)點(diǎn)代表的可能關(guān)鍵碼集合，比較次數(shù)就等于此外部結(jié)點(diǎn)的層數(shù)。2最優(yōu)二叉搜索樹(shù)第十五頁(yè)，共五十二頁(yè)，編輯于2023年，星期一16例：P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05123q0q1q2q3123q0q1q2q3q0123q1q2q3123q0q1q2q3123q0q1q2q3考慮平均搜索次數(shù)，也叫做平均路長(zhǎng)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)二叉搜索樹(shù)abcde第十六頁(yè)，共五十二頁(yè)，編輯于2023年，星期一17分析對(duì)于圖的內(nèi)結(jié)點(diǎn)而言，第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)二叉搜索樹(shù)第十七頁(yè)，共五十二頁(yè)，編輯于2023年，星期一18找到元素x=xi的概率為bi；確定x∈(xi,xi+1)的概率為ai。其中約定x0=－∞,xn+1=+∞,有2最優(yōu)二叉搜索樹(shù)第十八頁(yè)，共五十二頁(yè)，編輯于2023年，星期一19在一個(gè)表示S的二叉樹(shù)T中，設(shè)存儲(chǔ)元素xi的結(jié)點(diǎn)深度為ci；葉結(jié)點(diǎn)（xj，xj＋1）的結(jié)點(diǎn)深度為dj

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

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

L

R1,2,…,k-1

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

ak,ak+1,…,an4最優(yōu)子結(jié)構(gòu)性質(zhì)第二十一頁(yè)，共五十二頁(yè)，編輯于2023年，星期一22511472063353976425431399844最優(yōu)子結(jié)構(gòu)性質(zhì)第二十二頁(yè)，共五十二頁(yè)，編輯于2023年，星期一23511472063353976425431399844最優(yōu)子結(jié)構(gòu)性質(zhì)第二十三頁(yè)，共五十二頁(yè)，編輯于2023年，星期一24設(shè)COST(L)

和COST(R)

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

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

是最優(yōu)的，則上式及COST(L)和COST(R)必定都取最小值。4最優(yōu)子結(jié)構(gòu)性質(zhì)第二十四頁(yè)，共五十二頁(yè)，編輯于2023年，星期一25最優(yōu)子結(jié)構(gòu)性質(zhì)證明二叉搜索樹(shù)T的一棵含有頂點(diǎn)xi,···,xj和葉頂點(diǎn)

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

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

的存取分布概率，在子樹(shù)的頂點(diǎn)處被搜索到的概率是：4最優(yōu)子結(jié)構(gòu)性質(zhì)第二十五頁(yè)，共五十二頁(yè)，編輯于2023年，星期一26左子樹(shù)的搜索概率右子樹(shù)的搜索概率設(shè)Tij是有序集{xi

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

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

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

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

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

s[1][1]=1,s[2][2]=2…s[n][n]=n2)構(gòu)造具有2個(gè)內(nèi)部結(jié)點(diǎn)的最優(yōu)二叉搜索樹(shù)第三十頁(yè)，共五十二頁(yè)，編輯于2023年，星期一31例給出標(biāo)識(shí)符集{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)二叉搜索樹(shù)5遞歸計(jì)算最優(yōu)值第三十一頁(yè)，共五十二頁(yè)，編輯于2023年，星期一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.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第三十二頁(yè)，共五十二頁(yè)，編輯于2023年，星期一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.5m[2][3]=0.5m[2][3]=0.6第三十三頁(yè)，共五十二頁(yè)，編輯于2023年，星期一34q0=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第三十四頁(yè)，共五十二頁(yè)，編輯于2023年，星期一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第三十五頁(yè)，共五十二頁(yè)，編輯于2023年，星期一36T[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第三十六頁(yè)，共五十二頁(yè)，編輯于2023年，星期一3701231230000401231234W(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第三十七頁(yè)，共五十二頁(yè)，編輯于2023年，星期一38具體求解過(guò)程遞歸出口，沒(méi)有內(nèi)部節(jié)點(diǎn)時(shí)，構(gòu)造T[1][0]T[2][1],T[3][2]……，T[n+1][n]2)構(gòu)造具有2個(gè)、3個(gè)、……、n個(gè)內(nèi)部結(jié)點(diǎn)的最優(yōu)二叉搜索樹(shù)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遞歸計(jì)算最優(yōu)值第三十八頁(yè)，共五十二頁(yè)，編輯于2023年，星期一39voidOBST(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)造沒(méi)有內(nèi)部節(jié)點(diǎn)時(shí)的情況for(intr=0;r<n;r++)for(inti=1;i<=n-r;i++){intj=i+r;

構(gòu)造T[i][j]，填寫(xiě)w[i][j],m[i][j],s[i][j]}}第三十九頁(yè)，共五十二頁(yè)，編輯于2023年，星期一40構(gòu)造T[i][j]T[i][j]表示用第i到第j個(gè)內(nèi)部節(jié)點(diǎn)構(gòu)造的樹(shù)，做根的結(jié)點(diǎn)可以是第i，i+1,…,j中任意一個(gè)。1)首選i作為根，其左子樹(shù)空，右子樹(shù)為結(jié)點(diǎn)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,左子樹(shù)為結(jié)點(diǎn)i,i+1,…,k-1,右子樹(shù)為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遞歸計(jì)算最優(yōu)值第四十頁(yè)，共五十二頁(yè)，編輯于2023年，星期一41voidOptimalBinarySearchTree(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];}}初始化對(duì)角線賦值i為起始元素下標(biāo)j為終止元素下標(biāo)加第j個(gè)結(jié)點(diǎn)后，權(quán)值w改變?nèi)绲趇個(gè)結(jié)點(diǎn)作根的值取第k個(gè)結(jié)點(diǎn)作根5遞歸計(jì)算最優(yōu)值第四十一頁(yè)，共五十二頁(yè)，編輯于2023年，星期一426、構(gòu)造最優(yōu)解6構(gòu)造最優(yōu)解第四十二頁(yè)，共五十二頁(yè)，編輯于2023年，星期一437、計(jì)算復(fù)雜性第四十三頁(yè)，共五十二頁(yè)，編輯于2023年，星期一44練習(xí)設(shè)n=4，且

(1,2,3,4)=(do,if,read,while)。又