4.5最優(yōu)檢索樹.ppt

1、1,5. 最優(yōu)檢索樹,- 檢索，search就是member(a, S), 序列是一系列的member指令。,2,有一個造樹的問題，用誰做根？,例如：,因為不但要檢索aS，而是一般地要檢索aU （S是U中的一個子集）。 對于全集U中所有元素a，給出指令Member(a，S)在中出現(xiàn)的概率。為S設(shè)計一棵二叉查找樹，以期望的最小比較次數(shù)在線處理Member指令序列。 -二叉查找樹的代價cost,3,設(shè)S: a1,a2,an 且aiai+1(升序排列，假設(shè)無相等元) 令， Pi代表MEMBER(ai,S)指令（aS）在中出現(xiàn)的頻率， qi代表MEMBER(a,S)指令(a S)在中出現(xiàn)的頻率,其定義

2、為： q0 MEMBER(a, S) aa1 qi MEMBER(a, S) aiaai+1 qn MEMBER(a, S) aan,4,例如， 有U： 0、begin、1、else、2、end、3、if、4、then、5 有S： begin、else、end、if、then （i 是U-S中的元，0in）,為了定義二叉查找樹的代價cost，可加入n1個葉子，以便構(gòu)造集合U-S中元素的映射，稱這些葉子為0，1，n,5,下面定義二叉查找樹的代價,顯然： 如果aS，例如，a=l(v)， 那么，比較次數(shù)=depth(v)+1；（加1為比較根的花費） 如果a S，那么，比較次數(shù)=depth(i)； （

3、 i是葉，且是U-S中的元）,我們定義可期比較次數(shù)為T的費用CT ，,6,以上面的例子，假定|S|=5，且假定|U-S|=6 即，有U： 0、begin、1、else、2、end、3、if、4、then、5 有S： begin、else、end、if、then 其中，小于和大于S的元共2個：|0|+|5|=2 滿足aiaai+1的元共4個：|1|+|2|+|3|+|4|=4 那么， ， ， ， 似乎是等概率，但實際情況并非如此！,7,如何使費用CT最??？- 動態(tài)規(guī)劃 設(shè)Tij為T的最優(yōu)子樹，其節(jié)點為： ai+1,aj 0ijn Cij為Tij的費用； rij 根； wij . 權(quán)；weight

4、（即出現(xiàn)概率之和） wij = qi + ( pi+1 + qi+1 ) + , + ( pj + qj ),8,例如，end的子樹begin，有w02,w02 = q0 + ( p1 + q1 ) + ( p2 + q2 ) T12是begin的子樹，Tii是空樹， Cii=0, 但是wii= qi, i個元在U-S中，還有可能MEMBER(i, S)在中出現(xiàn)， 但其費用Cii=0，（i子樹的深度為0）,9,一般情況，需考慮2n個子樹，每個子樹有2個可能根。 樹Tij：,若rij為akS，那么它有2個子樹，2個子樹的每個節(jié)的深度Depth在Tij（母樹）中都增加1. Cij = Ci,k-1

5、 + Ck,j + Wi,k-1 + Pk + Wk,j,10,其中，（Wi,k-1 + Pk + Wk,j）為深度加1所增加的，也可認為是查找Root的花費。 wi,k-1= qi + ( pi+1 + qi+1 ) + , + ( pk-1 + qk-1 ) wk,j = qk + ( pk+1 + qk+1 ) + , + ( pj + qj ) pk = pk 以上三式相加： wi,k-1 + wk,j + pk = wij Tij 的費用： Cij = Ci,k-1 + Ck,j + Wij,11,要Cij最小，將找出k（ikj） ,使Ci,k-1 + Ck,j 最小。也就是要找出一

6、個根ak使Cij最小。 算法4.2: 構(gòu)造最優(yōu)二元檢索樹 輸入：S= a1,a2,an , 假設(shè) a1a2an，（1in,且無相等元） 輸出：最小花費的二元檢索樹。 方法：.用動態(tài)規(guī)劃計算出Cij，并得rij .以rij為根，生成最優(yōu)樹。,12,Begin （P.73） 1. for i0 until n do (初始化) begin 2. wii qi； 3. Cii0 end 4. for l1 until n do (執(zhí)行n次) 5. for i0 until n-l do begin 6. j i+l； 7. wijwi,j-1+ pj+ qj； /ikj 8. 設(shè)m是最小Cij =

7、Ci,k-1 + Ck,j + Wi,j中的k值; 9. Cij Ci,m-1 + Cm,j + Wi,j； 10. rij am end end,13,取得最小Cij = Ci,k-1 + Ck,j + Wi,j中的k值m后，調(diào)用 BUILDTREE (i, j) 生成最優(yōu)樹。,Procedure BUILDTREE(i, j) (P.73) begin 1. 創(chuàng)建以vij為根的樹Tij； 2. 以rij標記vij； 3. 設(shè)m是rij的腳標（例如，rij=am）； 4. if im-1 then 調(diào)BUILDTREE (i, m-1)建vij的左子樹； 5. if mj then 調(diào)BUI

8、LDTREE (m, j)建vij的右子樹 end,14,例4.5 設(shè)有，|S|=4, a1a2a3a4, (P.72) 其中， q0= , q1= , q2=q3=q4= , p1= , p2= , p3=p4= , 即， 0 a1 1 a2 2 a3 3 a4 4 q0 p1 q1 p2 q2 p3 q3 p4 q4,15,注意： q0 + p1 + q1 + p2 + q2 + p3 + q3 + p4 + q4 = =1,16,根據(jù)公式： wij= wi,k-1 + wk,j + pk Cij= Ci,k-1 + Ck,j + Wij 可得到圖 Fig. 4.11(書 P.73)中數(shù)據(jù)

9、。,17,例如： 1. 求解C04, 由ikj，有 C00 + C14 = 0 + 18 = 18 C01 + C24 = 9 + 8 = 17 C02 + C34 = 18 + 3 = 21 C03 + C44 = 25 + 0 = 25 取當(dāng)k=2時，C04 有最小值,即 C04 = C01 + C24 + W04 = 9 + 8 + 16 = 33,由公式：Cij= Ci,k-1 + Ck,j + Wij,18,2. 當(dāng)選擇r04時， 由ikj，再根據(jù)公式，可作如下比較： k=1： C04 = C00 + C14 + W04 = 0 + 18 + W04 = 18 + W04 k=2：

10、C04 = C01 + C24 + W04 = 9 + 8 + W04 = 17 + W04 k=3： C04 = C02 + C34 + W04 = 18 + 3 + W04 = 21 + W04 k=4： C04 = C03 + C44 + W04 = 25 + 0 + W04 = 25 + W04,公式：Cij= Ci,k-1 + Ck,j + Wij,19,3. 再考察r14時， 由ikj，再根據(jù)公式，可作如下比較： k=2： C14 = C11 + C24 + W14 = 0 + 8 + W14 = 8 + W14 k=3： C14 = C12 + C34 + W14 = 6 + 3 + W14 = 9 + W14 k=4： C14 = C13 + C44 + W14 = 11 + 0 + W14 = 11 + W14,公式：Cij= Ci,k-1 + Ck,j + Wij,20, 在k=2時，Ci