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

1、13.5 最優(yōu)二叉搜索樹(shù)最優(yōu)二叉搜索樹(shù)Optimal Binary Search Trees2 1二叉搜索樹(shù)二叉搜索樹(shù) 2最優(yōu)二叉搜索樹(shù)最優(yōu)二叉搜索樹(shù) 3最優(yōu)二叉搜索樹(shù)問(wèn)題描述最優(yōu)二叉搜索樹(shù)問(wèn)題描述 4最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì) 5遞歸計(jì)算最優(yōu)值遞歸計(jì)算最優(yōu)值 6算法算法3是一棵空樹(shù)或者滿足以下的性質(zhì)：是一棵空樹(shù)或者滿足以下的性質(zhì)： 每個(gè)結(jié)點(diǎn)作為搜索對(duì)象，它的關(guān)鍵字是每個(gè)結(jié)點(diǎn)作為搜索對(duì)象，它的關(guān)鍵字是互不相同互不相同的。的。 對(duì)于樹(shù)上的所有結(jié)點(diǎn)，如果它有對(duì)于樹(shù)上的所有結(jié)點(diǎn)，如果它有，那么左子樹(shù)，那么左子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字都上所有結(jié)點(diǎn)的關(guān)鍵字都小于小于該結(jié)點(diǎn)的關(guān)鍵字。該結(jié)點(diǎn)的關(guān)鍵字。對(duì)于樹(shù)上

2、的所有結(jié)點(diǎn)，如果它有對(duì)于樹(shù)上的所有結(jié)點(diǎn)，如果它有，那么右子樹(shù)，那么右子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字都上所有結(jié)點(diǎn)的關(guān)鍵字都大于大于該結(jié)點(diǎn)的關(guān)鍵字。該結(jié)點(diǎn)的關(guān)鍵字。1 二叉搜索樹(shù)二叉搜索樹(shù)4xalwanwilwenwimwulzolyozomxulyumxemyonzi搜索過(guò)程：從根結(jié)點(diǎn)開(kāi)始，如果根為空，則搜索搜索過(guò)程：從根結(jié)點(diǎn)開(kāi)始，如果根為空，則搜索不成功；否則使用待搜索值與根結(jié)點(diǎn)比較，如不成功；否則使用待搜索值與根結(jié)點(diǎn)比較，如果待搜索值等于根結(jié)點(diǎn)關(guān)鍵字，則搜索成功返果待搜索值等于根結(jié)點(diǎn)關(guān)鍵字，則搜索成功返回，如果小于根結(jié)點(diǎn)，則向左子樹(shù)搜索；如果回，如果小于根結(jié)點(diǎn)，則向左子樹(shù)搜索；如果大于根結(jié)點(diǎn)，則向右

3、子樹(shù)搜索。大于根結(jié)點(diǎn)，則向右子樹(shù)搜索。1 二叉搜索樹(shù)二叉搜索樹(shù)5 對(duì)于一個(gè)給定的關(guān)鍵字集合，可能有若干不同的對(duì)于一個(gè)給定的關(guān)鍵字集合，可能有若干不同的二分檢索樹(shù)二分檢索樹(shù) 如對(duì)保留字的子集如對(duì)保留字的子集 Name： 1 2 3 4 5 for if loop repeat while的兩棵二分檢索樹(shù)為的兩棵二分檢索樹(shù)為ifforwhilelooprepeatifwhilelooprepeatforab考慮考慮a圖和圖和b圖中最圖中最壞比較次數(shù)和平均壞比較次數(shù)和平均比較次數(shù)比較次數(shù)1 二叉搜索樹(shù)二叉搜索樹(shù)6 構(gòu)造不同的二叉搜索樹(shù)就有不同的性能特征。構(gòu)造不同的二叉搜索樹(shù)就有不同的性能特征。 二叉

4、搜索樹(shù)二叉搜索樹(shù)a在在最壞情況最壞情況下找一個(gè)標(biāo)識(shí)符需要下找一個(gè)標(biāo)識(shí)符需要4次比次比較較，而，而b表示的二分檢索樹(shù)最壞情況下只需表示的二分檢索樹(shù)最壞情況下只需3次比較次比較。 假設(shè)只假設(shè)只作成功的檢索作成功的檢索并且并且檢索每個(gè)標(biāo)識(shí)符的概率相同檢索每個(gè)標(biāo)識(shí)符的概率相同，則兩棵二分檢索樹(shù)在平均情況下各需要?jiǎng)t兩棵二分檢索樹(shù)在平均情況下各需要12/5和和11/5次次比較。比較。ifforwhilelooprepeatifwhilelooprepeatforab1 二叉搜索樹(shù)二叉搜索樹(shù)72、最優(yōu)二叉搜索樹(shù)、最優(yōu)二叉搜索樹(shù)存在的兩個(gè)問(wèn)題存在的兩個(gè)問(wèn)題1 在實(shí)際中也會(huì)遇到在實(shí)際中也會(huì)遇到不成功不成功檢索的

5、情況。檢索的情況。2 在實(shí)際中，不同標(biāo)識(shí)符會(huì)有在實(shí)際中，不同標(biāo)識(shí)符會(huì)有不同不同的檢索概率。的檢索概率。 對(duì)給定的標(biāo)識(shí)符集合，希望給出構(gòu)造二分搜索對(duì)給定的標(biāo)識(shí)符集合，希望給出構(gòu)造二分搜索樹(shù)的方法，使得所構(gòu)造的二分搜索樹(shù)具有樹(shù)的方法，使得所構(gòu)造的二分搜索樹(shù)具有最優(yōu)最優(yōu)的性能的性能。2 最優(yōu)二叉搜索樹(shù)最優(yōu)二叉搜索樹(shù)8 擴(kuò)充二叉樹(shù)：當(dāng)二叉樹(shù)里出現(xiàn)空的子樹(shù)時(shí)，擴(kuò)充二叉樹(shù)：當(dāng)二叉樹(shù)里出現(xiàn)空的子樹(shù)時(shí)，就增加新的、特殊的結(jié)點(diǎn)就增加新的、特殊的結(jié)點(diǎn)空樹(shù)葉空樹(shù)葉。對(duì)。對(duì)于原來(lái)二叉樹(shù)里度數(shù)為于原來(lái)二叉樹(shù)里度數(shù)為1的分支結(jié)點(diǎn)，在它的分支結(jié)點(diǎn)，在它下面增加一個(gè)空樹(shù)葉；對(duì)于原來(lái)二叉樹(shù)的下面增加一個(gè)空樹(shù)葉；對(duì)于原來(lái)二叉樹(shù)的

6、樹(shù)葉，在它下面增加兩個(gè)空樹(shù)葉。樹(shù)葉，在它下面增加兩個(gè)空樹(shù)葉。 擴(kuò)充二叉樹(shù)是擴(kuò)充二叉樹(shù)是滿二叉樹(shù)滿二叉樹(shù)，新增加的空樹(shù)葉，新增加的空樹(shù)葉（以下稱外部結(jié)點(diǎn)）的個(gè)數(shù)等于原來(lái)二叉（以下稱外部結(jié)點(diǎn)）的個(gè)數(shù)等于原來(lái)二叉樹(shù)的結(jié)點(diǎn)（以下稱內(nèi)部結(jié)點(diǎn)）個(gè)數(shù)加樹(shù)的結(jié)點(diǎn)（以下稱內(nèi)部結(jié)點(diǎn)）個(gè)數(shù)加1。在實(shí)際中也會(huì)遇到在實(shí)際中也會(huì)遇到不成功不成功檢索的情況檢索的情況2 最優(yōu)二叉搜索樹(shù)最優(yōu)二叉搜索樹(shù)9xalwanwilwenwimwulzolyozomxulyumxemyonziAA代表其值處于代表其值處于wim和和wul之間的可能關(guān)鍵碼集合之間的可能關(guān)鍵碼集合2 最優(yōu)二叉搜索樹(shù)最優(yōu)二叉搜索樹(shù)10 設(shè)設(shè) S=x1, x2,

7、, xn 是一個(gè)有序集合，且是一個(gè)有序集合，且x1, x2, , xn表示有序集合的二叉搜索樹(shù)利用二叉表示有序集合的二叉搜索樹(shù)利用二叉樹(shù)的頂點(diǎn)存儲(chǔ)有序集中的元素，而且具有性質(zhì)：樹(shù)的頂點(diǎn)存儲(chǔ)有序集中的元素，而且具有性質(zhì)： 存儲(chǔ)于每個(gè)頂點(diǎn)中的元素存儲(chǔ)于每個(gè)頂點(diǎn)中的元素x 大于其左子樹(shù)中任一個(gè)大于其左子樹(shù)中任一個(gè)頂點(diǎn)中存儲(chǔ)的元素，小于其右子樹(shù)中任意頂點(diǎn)中存頂點(diǎn)中存儲(chǔ)的元素，小于其右子樹(shù)中任意頂點(diǎn)中存儲(chǔ)的元素。二叉樹(shù)中的葉頂點(diǎn)是形如儲(chǔ)的元素。二叉樹(shù)中的葉頂點(diǎn)是形如(xi, xi+1) 的開(kāi)的開(kāi)區(qū)間。區(qū)間。在二叉搜索樹(shù)中搜索一個(gè)元素在二叉搜索樹(shù)中搜索一個(gè)元素x(1) 在二叉樹(shù)的內(nèi)部頂點(diǎn)處找到：在二叉樹(shù)的

8、內(nèi)部頂點(diǎn)處找到： x = xi(2) 在二叉樹(shù)的葉頂點(diǎn)中確定：在二叉樹(shù)的葉頂點(diǎn)中確定： x (xi , xi+1)2 最優(yōu)二叉搜索樹(shù)最優(yōu)二叉搜索樹(shù)11在實(shí)際中，不同標(biāo)識(shí)符會(huì)有在實(shí)際中，不同標(biāo)識(shí)符會(huì)有不同不同的檢索概率。的檢索概率。 設(shè)設(shè)Pi是對(duì)是對(duì)ai檢索的概率。檢索的概率。 設(shè)設(shè)qi是對(duì)滿足是對(duì)滿足aiXai+1,0 i n的標(biāo)識(shí)符的標(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ōu)二叉搜索樹(shù)12最優(yōu)二叉搜索樹(shù)最優(yōu)二叉搜索樹(shù)利用動(dòng)態(tài)

9、規(guī)劃構(gòu)造對(duì)標(biāo)識(shí)符集合利用動(dòng)態(tài)規(guī)劃構(gòu)造對(duì)標(biāo)識(shí)符集合a1, a2, , an的的最優(yōu)二叉搜索樹(shù)最優(yōu)二叉搜索樹(shù)算法算法（包括包括成功檢索成功檢索和和不成功檢索不成功檢索）。）。2 最優(yōu)二叉搜索樹(shù)最優(yōu)二叉搜索樹(shù)13 例例 標(biāo)識(shí)符集標(biāo)識(shí)符集1, 2, 3do, if, stop可能的二可能的二分檢索樹(shù)為：分檢索樹(shù)為：(a)321 231 (c)312(d) (b)312 321 (e) 設(shè)每個(gè)內(nèi)、外結(jié)點(diǎn)檢索的概率相同：設(shè)每個(gè)內(nèi)、外結(jié)點(diǎn)檢索的概率相同：pi=qi=1/7， 求每棵樹(shù)的平均比較次數(shù)（成本）。求每棵樹(shù)的平均比較次數(shù)（成本）。 若若P1=0.5, P2=0.1, P3=0.05, q0=0.15

10、, q1=0.1, q2=0.05, q3=0.05，求每棵樹(shù)的平均比較，求每棵樹(shù)的平均比較次數(shù)（成本）。次數(shù)（成本）。14在檢索過(guò)程中，每進(jìn)行一次比較，就進(jìn)入下面一層，在檢索過(guò)程中，每進(jìn)行一次比較，就進(jìn)入下面一層， 對(duì)于成功的檢索，對(duì)于成功的檢索，比較的次數(shù)就是所在的層數(shù)加比較的次數(shù)就是所在的層數(shù)加1。 對(duì)于不成功的檢索，被檢索的關(guān)鍵碼屬于那個(gè)外部結(jié)對(duì)于不成功的檢索，被檢索的關(guān)鍵碼屬于那個(gè)外部結(jié)點(diǎn)代表的可能關(guān)鍵碼集合，點(diǎn)代表的可能關(guān)鍵碼集合，比較次數(shù)就等于此外部結(jié)比較次數(shù)就等于此外部結(jié)點(diǎn)的層數(shù)。點(diǎn)的層數(shù)。2 最優(yōu)二叉搜索樹(shù)最優(yōu)二叉搜索樹(shù)15例：P1=0.5, P2=0.1, P3=0.05,

11、 q0=0.15, q1=0.1, q2=0.05, q3=0.05123q0q1q2q3123q0q1q2q3q0123q1q2q3123q0q1q2q3123q0q1q2q3考慮平均搜索次數(shù)，也叫做考慮平均搜索次數(shù)，也叫做平均路長(zhǎng)平均路長(zhǎng)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 最優(yōu)二叉搜索樹(shù)最優(yōu)二叉搜索樹(shù)a b c d e16分析對(duì)于圖的內(nèi)結(jié)點(diǎn)而言，第對(duì)于圖的內(nèi)結(jié)點(diǎn)而言，第0層需要比較操作次數(shù)為層需要比較操作次數(shù)為1，

12、第，第1層需要比較層需要比較2次，第次，第2層層需要需要3次次Pb(n)=1 p1 + 2 p3+3 p2 + 1q0 + 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.

13、5 + 3 0.1 + 10.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 + 10.05 + 2 0.15 + 3 (0.1 + 0.05) =2.152 最優(yōu)二叉搜索樹(shù)最優(yōu)二叉搜索樹(shù)17 找到元素找到元素x = xi的概率為的概率為bi；確定；確定x (xi , xi+1)的的概率為概率為ai。其中約定其中約定x0= , xn+1= + ,有有2 最優(yōu)二叉搜索樹(shù)最優(yōu)二叉搜索樹(shù)18 在一個(gè)表示在一個(gè)表示S的二叉樹(shù)的二叉樹(shù)T中，設(shè)

14、存儲(chǔ)元素中，設(shè)存儲(chǔ)元素xi的結(jié)點(diǎn)深的結(jié)點(diǎn)深度為度為ci；葉結(jié)點(diǎn)（；葉結(jié)點(diǎn)（xj，xj1）的結(jié)點(diǎn)深度為）的結(jié)點(diǎn)深度為dj 。 表示在二叉搜索樹(shù)表示在二叉搜索樹(shù)T中作一次搜索所需的平均比中作一次搜索所需的平均比較次數(shù)。較次數(shù)。P又稱為二叉搜索樹(shù)又稱為二叉搜索樹(shù)T的平均路長(zhǎng)，在的平均路長(zhǎng)，在一般情況下，不同的二叉搜索樹(shù)的平均路長(zhǎng)是一般情況下，不同的二叉搜索樹(shù)的平均路長(zhǎng)是不同的。不同的。2 最優(yōu)二叉搜索樹(shù)最優(yōu)二叉搜索樹(shù)193、最優(yōu)二叉搜索樹(shù)問(wèn)題描述、最優(yōu)二叉搜索樹(shù)問(wèn)題描述 對(duì)于有序集對(duì)于有序集S及其存取概率分布及其存取概率分布 （a0, b1, a1, , bn, an），在所有表示有序集），在所有表

15、示有序集S的二叉搜索樹(shù)中找出一棵具有最小平均路的二叉搜索樹(shù)中找出一棵具有最小平均路長(zhǎng)的二叉搜索樹(shù)。長(zhǎng)的二叉搜索樹(shù)。 結(jié)點(diǎn)在二叉搜索樹(shù)中的層次越深，需要比結(jié)點(diǎn)在二叉搜索樹(shù)中的層次越深，需要比較的次數(shù)就越多，因此要構(gòu)造一棵最小二較的次數(shù)就越多，因此要構(gòu)造一棵最小二叉樹(shù)，一般盡量把搜索概率較高的結(jié)點(diǎn)放叉樹(shù)，一般盡量把搜索概率較高的結(jié)點(diǎn)放在較高的層次。在較高的層次。3 最優(yōu)二叉搜索樹(shù)問(wèn)題最優(yōu)二叉搜索樹(shù)問(wèn)題204、最優(yōu)子結(jié)構(gòu)性質(zhì)、最優(yōu)子結(jié)構(gòu)性質(zhì) 假設(shè)選擇假設(shè)選擇 k為樹(shù)根，則為樹(shù)根，則 1, 2, , k-1 和和a0, a1, , ak-1 都將位于左子樹(shù)都將位于左子樹(shù) L 上，其余上，其余結(jié)點(diǎn)結(jié)點(diǎn)

16、(k+1, , n 和和 ak, ak+1, , an)位于位于右子樹(shù)右子樹(shù) R 上。上。k L R 1, 2, , k-1 a0, a1, , ak-1k+1, , n ak, ak+1, , an4 最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)21511472063353976425431399844 最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)22511472063353976425431399844 最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)23 設(shè)設(shè)COST(L) 和和COST(R) 分別是二分檢索樹(shù)分別是二分檢索樹(shù)T的左子樹(shù)和右子樹(shù)的的左子樹(shù)和右子樹(shù)的成本。成本。 則檢索樹(shù)則檢索樹(shù)T的成本是：的成本是： P(k)+ COST(

17、L) + COST(R) + 若若 T 是最優(yōu)的，則上式及是最優(yōu)的，則上式及 COST(L) 和和COST(R) 必定都取最小值。必定都取最小值。4 最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)24最優(yōu)子結(jié)構(gòu)性質(zhì)證明最優(yōu)子結(jié)構(gòu)性質(zhì)證明 二叉搜索樹(shù)二叉搜索樹(shù)T 的一棵含有頂點(diǎn)的一棵含有頂點(diǎn)xi , , xj和葉頂點(diǎn)和葉頂點(diǎn) (xi-1 , xi ) , , ( xj , xj+1)的子樹(shù)可以看作是有序集的子樹(shù)可以看作是有序集 xi , , xj 關(guān)于全集為關(guān)于全集為 xi-1 , xj1 的一棵二叉搜索的一棵二叉搜索樹(shù)（樹(shù)（T 自身可以看作是有序集自身可以看作是有序集) 。根據(jù)根據(jù)S 的存取分布概率，在子樹(shù)的頂

18、點(diǎn)處被搜索到的的存取分布概率，在子樹(shù)的頂點(diǎn)處被搜索到的概率是：概率是：4 最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)25jipwpww)(pww)(pwpwr,jmli,mijr,jmm,mli,mijij 111111左子樹(shù)左子樹(shù)的搜索的搜索概率概率右子樹(shù)右子樹(shù)的搜索的搜索概率概率設(shè)設(shè)Tij是有序集是有序集xi , , xj關(guān)于存儲(chǔ)概率分布為關(guān)于存儲(chǔ)概率分布為ai-1, bi, , bj, aj 的一棵最優(yōu)二叉搜索樹(shù)，其平均路長(zhǎng)的一棵最優(yōu)二叉搜索樹(shù)，其平均路長(zhǎng)為為pij，Tij的根頂點(diǎn)存儲(chǔ)的元素的根頂點(diǎn)存儲(chǔ)的元素xm，其左子樹(shù)，其左子樹(shù)Tl和右子樹(shù)和右子樹(shù)Tr的平均路長(zhǎng)分別為的平均路長(zhǎng)分別為pl和和pr。

19、由于。由于Tl和和Tr中頂點(diǎn)深度是中頂點(diǎn)深度是它們?cè)谒鼈冊(cè)赥ij中的深度減中的深度減1，所以得到，所以得到xi , , xj的存儲(chǔ)概率分布為的存儲(chǔ)概率分布為ai-1, bi, , bj, aj ，其，其中，中，ah，bk分別是下面的條件概率：分別是下面的條件概率：4 最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)26構(gòu)造最優(yōu)二叉搜索樹(shù)時(shí)，可以選構(gòu)造最優(yōu)二叉搜索樹(shù)時(shí)，可以選擇先構(gòu)造其左右子樹(shù)，使其左右擇先構(gòu)造其左右子樹(shù)，使其左右子樹(shù)最優(yōu)，然后構(gòu)造整棵樹(shù)。子樹(shù)最優(yōu)，然后構(gòu)造整棵樹(shù)。4 最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)275、遞歸計(jì)算最優(yōu)值 最優(yōu)二叉搜索樹(shù)最優(yōu)二叉搜索樹(shù)Tij的平均路長(zhǎng)為的平均路長(zhǎng)為pij，則所求的，則所

20、求的最優(yōu)值為最優(yōu)值為p1,n。由二叉樹(shù)的花費(fèi)公式。由二叉樹(shù)的花費(fèi)公式 根據(jù)最優(yōu)二叉搜索樹(shù)問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)可根據(jù)最優(yōu)二叉搜索樹(shù)問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)可建立計(jì)算建立計(jì)算pij的遞歸式如下的遞歸式如下初始時(shí)初始時(shí)jipwpww)(pww)(pwpw,jk,jki,ki,kij,jk,jkk,ki,ki,kijij 11111111115 遞歸計(jì)算最優(yōu)值遞歸計(jì)算最優(yōu)值28記記 wi,j pi,j 為為m( i, j ) 遞歸計(jì)算最優(yōu)值遞歸計(jì)算最優(yōu)值5 遞歸計(jì)算最優(yōu)值遞歸計(jì)算最優(yōu)值29根據(jù)該公式，計(jì)算樹(shù)根據(jù)該公式，計(jì)算樹(shù)Tij的花費(fèi)只用到了的花費(fèi)只用到了Tik-1，Tk+1j, 可得到具體求解過(guò)程如下

21、：可得到具體求解過(guò)程如下：1）構(gòu)造只有）構(gòu)造只有1個(gè)內(nèi)部結(jié)點(diǎn)的最優(yōu)二叉搜索樹(shù)個(gè)內(nèi)部結(jié)點(diǎn)的最優(yōu)二叉搜索樹(shù)T11,T22, Tnn，可以求得，可以求得mii 同時(shí)同時(shí)可以用一個(gè)數(shù)組存做根結(jié)點(diǎn)元素為：可以用一個(gè)數(shù)組存做根結(jié)點(diǎn)元素為： s11=1, s22=2snn=n2) 構(gòu)造具有構(gòu)造具有2個(gè)內(nèi)部結(jié)點(diǎn)的最優(yōu)二叉搜索樹(shù)個(gè)內(nèi)部結(jié)點(diǎn)的最優(yōu)二叉搜索樹(shù)30例 給出標(biāo)識(shí)符集給出標(biāo)識(shí)符集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構(gòu)造一棵最優(yōu)二叉搜索樹(shù)構(gòu)造一棵最優(yōu)二叉搜索樹(shù)5 遞歸

22、計(jì)算最優(yōu)值遞歸計(jì)算最優(yōu)值31q0=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.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=032q0=0.1

23、5, 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.1512q0q1q212q0q1q2T12w12=0.9m12=0.9+ m11+m32 =1.65w12=0.9m12=0.9+ m10+m22 =1.1523q1q2q323q1q2q3T23w23=0. 5m23=0.5m23=0.633q0=0.15, P1=0.5, q1=0.1, P2=0.1, q2=0.05, P3=0.05, q3=0.

24、051q0q1T11w11=0.75m11=0.752q1q2T22w22=0.25m22=0.253q2q3T33w33=0.15m33=0.1512q0q1q212q0q1q2T12w12=0.9m12=0.9+ m11+m32 =1.65w12=0.9m12=0.9+ m10+m22 =1.1523q1q2q323q1q2q3T23w23=0. 35m23=0.5m23=0.634T12m12=1.1512q0q1q223q1q2q3T23m23=0.523q2q31q0q1T13W13=1m13=1.523q2q31q0q1m13=1.923q2q31q0q1m13=2.15q0=0.

25、15, P1=0.5, q1=0.1, P2=0.1, q2=0.05, P3=0.05, q3=0.0535T12m12=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.05360123123000040 1 2 31234W(i, j)0 1 2 3123400000.150.10.050.050.750.7510.250.150.250.15

26、230.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.0537具體求解過(guò)程具體求解過(guò)程遞歸出口，沒(méi)有內(nèi)部節(jié)點(diǎn)時(shí)，構(gòu)造遞歸出口，沒(méi)有內(nèi)部節(jié)點(diǎn)時(shí)，構(gòu)造T10 T21,T32，Tn+1n2) 構(gòu)造具有構(gòu)造具有2個(gè)、個(gè)、3個(gè)、個(gè)、n個(gè)內(nèi)部結(jié)點(diǎn)的最優(yōu)二個(gè)內(nèi)部結(jié)點(diǎn)的最優(yōu)二叉搜索樹(shù)叉搜索樹(shù)r （ 起止下標(biāo)的差）起止下標(biāo)的差）0 T11, T22 , ， Tnn，1 T12, T23, ，Tn-1n，2 T13, T24, ，Tn-2n，r T1r+1, T2r+2, ，Tii

27、+r，Tn-rnn-1 T1n 5 遞歸計(jì)算最優(yōu)值遞歸計(jì)算最優(yōu)值38void 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; /初始化，構(gòu)造沒(méi)有內(nèi)部節(jié)點(diǎn)時(shí)的情況初始化，構(gòu)造沒(méi)有內(nèi)部節(jié)點(diǎn)時(shí)的情況for(int r=0; rn; r+) for(int i =1; i=n-r; i+) int j= i+r; 構(gòu)造構(gòu)造Tij，填寫(xiě)，填寫(xiě)wij,mij,sij 39構(gòu)造構(gòu)造TijTij表示用第表示用第i到第到第j個(gè)內(nèi)部節(jié)點(diǎn)構(gòu)造的樹(shù)，做根的結(jié)個(gè)內(nèi)部節(jié)點(diǎn)構(gòu)造的樹(shù)，

28、做根的結(jié)點(diǎn)可以是第點(diǎn)可以是第i，i+1,j中任意一個(gè)。中任意一個(gè)。1) 首選首選i作為根，其左子樹(shù)空，右子樹(shù)為結(jié)點(diǎn)作為根，其左子樹(shù)空，右子樹(shù)為結(jié)點(diǎn)i+1,i+2j構(gòu)成即構(gòu)成即Ti+1j。 mij=wij+0+mi+1j sij= i2) 不選不選i做根，設(shè)做根，設(shè)k為其根，則為其根，則k= i+1,j,左子樹(shù)為結(jié)左子樹(shù)為結(jié)點(diǎn)點(diǎn)i, i+1,k-1, 右子樹(shù)為右子樹(shù)為k+1, k+2, ,j t= wij+mik-1+mk+1j if(t mij) mij=t; sij=k; 3)k= k+1, 跳回跳回25 遞歸計(jì)算最優(yōu)值遞歸計(jì)算最優(yōu)值40void OptimalBinarySearchTre

29、e( 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; 初始化初始化對(duì)角線賦值對(duì)角線賦值i為起始元素下標(biāo)為起始元素下

30、標(biāo)j為終止元素下標(biāo)為終止元素下標(biāo)加第加第j個(gè)結(jié)點(diǎn)后，個(gè)結(jié)點(diǎn)后，權(quán)值權(quán)值w改變改變?nèi)绲谌绲趇個(gè)結(jié)點(diǎn)作根的個(gè)結(jié)點(diǎn)作根的值值取第取第k個(gè)結(jié)點(diǎn)作根個(gè)結(jié)點(diǎn)作根5 遞歸計(jì)算最優(yōu)值遞歸計(jì)算最優(yōu)值416、構(gòu)造最優(yōu)解6 構(gòu)造最優(yōu)解構(gòu)造最優(yōu)解427、計(jì)算復(fù)雜性43練習(xí)練習(xí)設(shè)設(shè)n=4，且，且 (1, 2, 3, 4) = (do, if, read, while)。又設(shè)又設(shè)b(1 : 4)=(3, 3, 1, 1)和和a(0 : 4)=(2,3,1,1,1)(這些這些b,a都乘了都乘了16。) 寫(xiě)出數(shù)組寫(xiě)出數(shù)組wij,mij,sij及最后的最優(yōu)及最后的最優(yōu)二叉搜索樹(shù)。二叉搜索樹(shù)。44作業(yè)P84 3-1545Exer

31、cises 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.0546動(dòng)態(tài)規(guī)劃總結(jié)動(dòng)態(tài)規(guī)劃總結(jié)一、動(dòng)態(tài)規(guī)劃的基本思想：一、動(dòng)態(tài)規(guī)劃的基本思想： 將問(wèn)題分解為若干小問(wèn)題，解子問(wèn)題，然后將問(wèn)題分解為若干小問(wèn)題，解子問(wèn)題，然后從子問(wèn)題

32、得到原問(wèn)題的解。從子問(wèn)題得到原問(wèn)題的解。 47二、動(dòng)態(tài)規(guī)劃特點(diǎn)二、動(dòng)態(tài)規(guī)劃特點(diǎn)將問(wèn)題分解為子問(wèn)題，這些子問(wèn)題往往不相將問(wèn)題分解為子問(wèn)題，這些子問(wèn)題往往不相互獨(dú)立。（如果可以用分治法求解，分解互獨(dú)立。（如果可以用分治法求解，分解的子問(wèn)題太多，因此，用分治法時(shí)間代價(jià)的子問(wèn)題太多，因此，用分治法時(shí)間代價(jià)太高，消耗指數(shù)時(shí)間）太高，消耗指數(shù)時(shí)間） 48三、動(dòng)態(tài)規(guī)劃思路三、動(dòng)態(tài)規(guī)劃思路 如果能夠保存已解決的子問(wèn)題的答案，而在需要如果能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，這樣就可以避免大量的時(shí)再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，節(jié)省時(shí)間。重復(fù)計(jì)算，節(jié)省時(shí)間。 動(dòng)態(tài)規(guī)劃方法用一個(gè)表來(lái)記錄所有已解的子問(wèn)題動(dòng)態(tài)規(guī)劃方法用一個(gè)表來(lái)