1、一、什么是最優二叉查找樹最優二叉查找樹：給定n個互異的關鍵字組成的序列 k=<k1,k2,kn> ,且關鍵字有序 (k1<k2<.<kn ),我們想從這些關鍵字中構造一棵二叉查找樹。對每個關鍵字ki, 一次搜索搜索到的概率為 pi。可能有一些搜索的值不在 k內，因此還有n+1個“虛擬鍵” d0,d1,dn ,他們代表不在k內的 值。具體：d0代表所有小于k1的值，dn代表所有大于kn的值。而 對于i = 1,2,n-1,虛擬鍵di代表所有位于ki和ki+1之間的值。對于 每個虛擬鍵，一次搜索對應于 di的概率為qi。要使得查找一個節點的 期望代價(代價可以定義為：

2、比如從根節點到目標節點的路徑上節點數 目)最小，就需要建立一棵最優二叉查找樹。圖一顯示了給定上面的概率分布 pi、qi,生成的兩個二叉查找樹的例子。 圖二就是在這種情況下一棵最優二叉查找樹。(b)概率分布：i 012345pi 0.15 0.10 0.05 0.10 0.20qi 0.05 0.10 0.05 0.05 0.05 0.10已知每個關鍵字以及虛擬鍵被搜索到的概率，可以計算出一個給定二叉查找樹內一次搜索的期望代價。 假設一次搜索的實際代價為檢查的節點的個數，即所發現的節點的深度加 1.計算一次搜索的期望代價等式為：h*e search cw tn fj 山pl% laj 4 ”四

3、4 £工小網）1 + h - ifi b* =1 + £drpi即（i. i - a + 叩叫 3, ”5 .建立一棵二叉查找樹，如果是的上式最小，那么這棵二叉查找樹就是最 優二叉查找樹。而且有下式成立:二、最優二叉查找樹的最優子結構最優子結構：如果一棵最優二叉查找樹 t有一棵包含關鍵字ki,.,kj的子樹t,那么這 可子樹t'對于關鍵字ki,.,kj和虛擬鍵di-1,.dj的子問題也必定是最優 的。可以應用剪貼法證明。根據最優子結構，尋找最優解:-可編輯修改-o給定關鍵字ki,kj，假設kr(i<=r<=j)是包含這些鍵的一棵最優子樹的 根。其左子樹包

4、含關鍵字ki,kr-1和虛擬鍵di-1,dr-1 ,右子樹包含 關鍵字kr+1,kj和虛擬鍵dr,dj。我們檢查所有的候選根kr,就保證可以找到一棵最優二叉查找樹。遞歸解：定義ei,j為包含關鍵字ki,kj的最優二叉查找樹的期望代價，最終要計算的是e1,n。當上二i - 1時，此時子樹中只有虛擬鍵，期望搜索代價為ei,i -1 = qi-1.當j >= i時，需要從ki,kj中選擇一個根kr,然后分別構造其左子樹 和右子樹。下面需要計算以kr為根的樹的期望搜索代價。然后選擇導 致最小期望搜索代價的kr做根。現在需要考慮的是，當一棵樹成為一個節點的子樹時，期望搜索代價怎么變化？子樹中每個節

5、點深度都增加1.期望搜索代價增加量為子樹中所有概率的總和。對一棵關鍵字ki,kj的子樹，定義其概率總和為：jj= z pt + z 納 ” m穆沁i因此，以kr為根的子樹的期望搜索代價為：帝 h = %+ (ep； r-1 + r- 1)+ (efr+ 1 .月 + 1.加而力=碓 r 1) + p+ 9 +因此ei,j可以進一步寫為:近力=e1j. r - i + «r + l _/ + w(?t jl這樣推導出最終的遞歸公式為：忖_if ; = j - 1 tdl/ l = min 巾+r - 1! +中+ l+獷伍川iy j.三、代碼實現(c+ ):cpp view plain

6、copyprint?1. 最優二叉查找樹2.3. #include <iostream>4.5. using namespace std;6.7. constint maxval=9999;8.9. constint n=5;10. 搜索到根節點和虛擬鍵的概率11. doublepn+1=-1,0.15,0.1,0.05,0.1,0.2;12. doubleqn+1=0.05,0.1,0.05,0.05,0.05,0.1;13.14. int rootn + 1n + 1;/ 記錄根節點15. doublewn + 2n + 2;/ 子樹概率總和16. doubleen + 2n

7、+ 2;/ 子樹期望代價17.18. void optimalbst( double *p, double *q, int n)19. 20. /初始化只包括虛擬鍵的子樹21. for (int i = 1;i <= n +1;+i)22. 23. wii - 1 = qi - 1;24. eii - 1 = qi - 1;25. 26.27. /由下到上，由左到右逐步計算28. for (int len = 1;len <= n;+len)29. -可編輯修改-30.31.32.33.34.35.for (int i = 1;i <= n - len + 1;+i)int

8、j = i + len - 1;eij = maxval;w皿=wij - 1 + pj + qj;/求取最小代價的子樹的根36.37.38.39.40.41.42.43.44.45.46. 47. for (int k = i;k <= j;+k)double temp = eik - 1 + ek + 1j + if (temp < eij)eij = temp;rootij = k;wij48.49. /輸出最優二叉查找樹所有子樹的根50.51.52.53.54.55.56.57.58.59.60.61.62.63.64.65.void printroot()cout <

9、;< "各子樹的根："<< endl;for (int i = 1;i <= n;+i)for (int j = 1;j <= n;+j) cout << rootij << "" cout << endl; cout << endl;/打印最優二叉查找樹的結構/打印出i,j子樹，它是根r的左子樹和右子樹66. void printoptimalbst( int i,int j,int r)67. 68. introotchild=rootij;/子樹根節點69. if(roo

10、tchild=root1n)70. 71. 輸出整棵樹的根72. cout << "k" << rootchild<< "是根"<<73. printoptimalbst(i,rootchild- 1,rootchild);endl;74.75.76.77.78.79.80.81.82.83.84.85.86.87.88.89.90.91.92.93.94.95.96.97.98.99.printoptimalbst(rootchild + 1,j,rootchild); return ;if (j <

11、; i - 1)return ;else if (j = i - 1)遇到虛擬鍵 if (j < r)cout << "d" << j << elsecout << "d" << j << return ;else /遇到內部結點"是"<< "k" <<"是"<< "k" <<if (rootchild < r) cout << &q

12、uot;k" << rootchild<< endl; elsecout << "k" << rootchild<< "是"<<<< "是"<<r << "的左孩子"<< endl;r << "的右孩子"<< endl;"k" << r << "的左孩子"k" <&

13、lt; r << "的右孩子<< endl;100. 101.102. printoptimalbst(i,rootchild103. printoptimalbst(rootchild-1,rootchild);+ 1,j,rootchild);104.105.106. int main()107. 108. optimalbst(p,q,n);109. printroot();110. cout << "最優二叉樹結構："<< endl;111. printoptimalbst(1,n,-1);112.我們將表e、w以及root旋轉45。，便于查看上述程序的計算過程。上述代碼核心在于函數optimalbst，其計算順序是從下到上、從左到右。 首先是依據概率數組pi、qi初始化：給最下面的一行賦值。然后是三 個for循環：從下到上計算表中每一行的值，可以充分利用前面