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

關(guān)于最優(yōu)二叉搜索樹1第1頁(yè)，共52頁(yè)，2023年，2月20日，星期四23.5最優(yōu)二叉搜索樹

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

Name：12345foriflooprepeatwhile的兩棵二分檢索樹為ifforwhilelooprepeatifwhilelooprepeatforab考慮a圖和b圖中最壞比較次數(shù)和平均比較次數(shù)1二叉搜索樹第6頁(yè)，共52頁(yè)，2023年，2月20日，星期四7

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

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

的開(kāi)區(qū)間。在二叉搜索樹中搜索一個(gè)元素x(1)在二叉樹的內(nèi)部頂點(diǎn)處找到：x=xi(2)在二叉樹的葉頂點(diǎn)中確定：x∈(xi,xi+1)2最優(yōu)二叉搜索樹第11頁(yè)，共52頁(yè)，2023年，2月20日，星期四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)二叉搜索樹第12頁(yè)，共52頁(yè)，2023年，2月20日，星期四13最優(yōu)二叉搜索樹利用動(dòng)態(tài)規(guī)劃構(gòu)造對(duì)標(biāo)識(shí)符集合{a1,a2,…,an}的最優(yōu)二叉搜索樹算法（包括成功檢索和不成功檢索）。2最優(yōu)二叉搜索樹第13頁(yè)，共52頁(yè)，2023年，2月20日，星期四14例標(biāo)識(shí)符集{1,2,3}＝{do,if,stop}可能的二分檢索樹為：(a)321

231

(c)312(d)

(b)312

321

(e)設(shè)每個(gè)內(nèi)、外結(jié)點(diǎn)檢索的概率相同：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ù)（成本）。第14頁(yè)，共52頁(yè)，2023年，2月20日，星期四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)二叉搜索樹第15頁(yè)，共52頁(yè)，2023年，2月20日，星期四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)二叉搜索樹abcde第16頁(yè)，共52頁(yè)，2023年，2月20日，星期四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)二叉搜索樹第17頁(yè)，共52頁(yè)，2023年，2月20日，星期四18找到元素x=xi的概率為bi；確定x∈(xi,xi+1)的概率為ai。其中約定x0=－∞,xn+1=+∞,有2最優(yōu)二叉搜索樹第18頁(yè)，共52頁(yè)，2023年，2月20日，星期四19在一個(gè)表示S的二叉樹T中，設(shè)存儲(chǔ)元素xi的結(jié)點(diǎn)深度為ci；葉結(jié)點(diǎn)（xj，xj＋1）的結(jié)點(diǎn)深度為dj

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

都將位于左子樹L上，其余結(jié)點(diǎn)(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ì)第21頁(yè)，共52頁(yè)，2023年，2月20日，星期四22511472063353976425431399844最優(yōu)子結(jié)構(gòu)性質(zhì)第22頁(yè)，共52頁(yè)，2023年，2月20日，星期四23511472063353976425431399844最優(yōu)子結(jié)構(gòu)性質(zhì)第23頁(yè)，共52頁(yè)，2023年，2月20日，星期四24設(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ì)第24頁(yè)，共52頁(yè)，2023年，2月20日，星期四25最優(yōu)子結(jié)構(gòu)性質(zhì)證明二叉搜索樹T的一棵含有頂點(diǎn)xi,···,xj和葉頂點(diǎn)

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

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

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

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

…,bj,aj}的一棵最優(yōu)二叉搜索樹，其平均路長(zhǎng)為pij，Tij的根頂點(diǎn)存儲(chǔ)的元素xm，其左子樹Tl和右子樹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ì)第26頁(yè)，共52頁(yè)，2023年，2月20日，星期四27構(gòu)造最優(yōu)二叉搜索樹時(shí)，可以選擇先構(gòu)造其左右子樹，使其左右子樹最優(yōu)，然后構(gòu)造整棵樹。4最優(yōu)子結(jié)構(gòu)性質(zhì)第27頁(yè)，共52頁(yè)，2023年，2月20日，星期四285、遞歸計(jì)算最優(yōu)值最優(yōu)二叉搜索樹Tij的平均路長(zhǎng)為pij，則所求的最優(yōu)值為p1,n。由二叉樹的花費(fèi)公式根據(jù)最優(yōu)二叉搜索樹問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)可建立計(jì)算pij的遞歸式如下初始時(shí)5遞歸計(jì)算最優(yōu)值第28頁(yè)，共52頁(yè)，2023年，2月20日，星期四29記wi,jpi,j為m(i,j)

遞歸計(jì)算最優(yōu)值5遞歸計(jì)算最優(yōu)值第29頁(yè)，共52頁(yè)，2023年，2月20日，星期四30根據(jù)該公式，計(jì)算樹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)二叉搜索樹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)二叉搜索樹第30頁(yè)，共52頁(yè)，2023年，2月20日，星期四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)二叉搜索樹5遞歸計(jì)算最優(yōu)值第31頁(yè)，共52頁(yè)，2023年，2月20日，星期四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第32頁(yè)，共52頁(yè)，2023年，2月20日，星期四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第33頁(yè)，共52頁(yè)，2023年，2月20日，星期四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第34頁(yè)，共52頁(yè)，2023年，2月20日，星期四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第35頁(yè)，共52頁(yè)，2023年，2月20日，星期四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第36頁(yè)，共52頁(yè)，2023年，2月20日，星期四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第37頁(yè)，共52頁(yè)，2023年，2月20日，星期四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)二叉搜索樹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)值第38頁(yè)，共52頁(yè)，2023年，2月20日，星期四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]，填寫w[i][j],m[i][j],s[i][j]}}第39頁(yè)，共52頁(yè)，2023年，2月20日，星期四40構(gòu)造T[i][j]T[i][j]表示用第i到第j個(gè)內(nèi)部節(jié)點(diǎn)構(gòu)造的樹，做根的結(jié)點(diǎn)可以是第i，i+1,…,j中任意一個(gè)。1)首選i作為根，其左子樹空，右子樹為結(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,左子樹為結(jié)點(diǎn)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遞歸計(jì)算最優(yōu)值第40頁(yè)，共52頁(yè)，2023年，2月20日，星期四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)值第41頁(yè)，共52頁(yè)，2023年，2月20日，星期四426、構(gòu)造最優(yōu)解6構(gòu)造最優(yōu)解第42頁(yè)，共52頁(yè)，2023年，2月20日，星期四437、計(jì)算復(fù)雜性第43頁(yè)，共52頁(yè)，2023年，2月20日，星期四44練習(xí)設(shè)n=4，且

(1,2,3,4)=(do,if,read,while)。又設(shè)b