最優二叉搜尋樹 （我不是一顆普通的樹 我的别稱是 哈夫曼樹）
二叉搜尋樹
二叉查找樹（Binary Search Tree），（又：二叉搜尋樹，二叉排序樹）它或者是一棵空樹，或者是具有下列性質的二叉樹： 若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值； 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值； 它的左、右子樹也分别為二叉排序樹。
一、什麼是最優二叉查找樹
最優二叉查找樹：
給定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。要使得查找一個節點的期望代價（代價可以定義為：比如從根節點到目标節點的路徑上節點數目）最小，就需要建立一棵最優二叉查找樹。
圖一顯示了給定上面的機率分布pi、qi，生成的兩個二叉查找樹的例子。圖二就是在這種情況下一棵最優二叉查找樹。
| i | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| pi | 0.15 | 0.10 | 0.05 | 0.20 | ||
| qi |
已知每個關鍵字以及虛拟鍵被搜尋到的機率，可以計算出一個給定二叉查找樹内一次搜尋的期望代價。假設一次搜尋的實際代價為檢查的節點的個數，即所發現的節點的深度加1.計算一次搜尋的期望代價等式為：
建立一棵二叉查找樹，如果是的上式最小，那麼這棵二叉查找樹就是最優二叉查找樹。
而且有下式成立：
二、最優二叉查找樹的最優子結構
最優子結構：
如果一棵最優二叉查找樹T有一棵包含關鍵字ki,..,kj的子樹T'，那麼這可子樹T'對于關鍵字Ki,...,kj和虛拟鍵di-1,...dj的子問題也必定是最優的。可以應用剪貼法證明。
根據最優子結構，尋找最優解：
給定關鍵字ki,...,kj，假設kr(i<=r<=j)是包含這些鍵的一棵最優子樹的根。其左子樹包含關鍵字ki,...,kr-1和虛拟鍵di-1,...,dr-1，右子樹包含關鍵字kr+1,...,kj和虛拟鍵dr,...dj。我們檢查所有的候選根kr,就保證可以找到一棵最優二叉查找樹。
遞歸解：
定義e[i,j]為包含關鍵字ki,...,kj的最優二叉查找樹的期望代價，最終要計算的是e[1,n]。
當j = i - 1時，此時子樹中隻有虛拟鍵，期望搜尋代價為e[i,i - 1] = qi-1.
當j >= i時，需要從ki,...,kj中選擇一個根kr，然後分别構造其左子樹和右子樹。下面需要計算以kr為根的樹的期望搜尋代價。然後選擇導緻最小期望搜尋代價的kr做根。
現在需要考慮的是，當一棵樹成為一個節點的子樹時，期望搜尋代價怎麼變化？子樹中每個節點深度都增加1.期望搜尋代價增加量為子樹中所有機率的總和。
對一棵關鍵字ki,...,kj的子樹，定義其機率總和為：
是以，以kr為根的子樹的期望搜尋代價為：
而
是以e[i,j]可以進一步寫為：
這樣推導出最終的遞歸公式為：
1 #include <iostream>
2 #include <cstdio>
3 #define INF 0xFFFFF
4 using namespace std;
5 double p[21], q[21];
6 int root[21][21];//記錄最優子樹的根節點位置
7 double w[21][21];//w[i][j]:最優子樹機率總和
8 double e[21][21];//e[i][j]: （最優）子樹期望代價
9
10 void optimalBST(int n)
11 {
12 for(int i = 1; i<=n+1; i++)
13 {
14 w[i][i-1] = q[i-1];
15 e[i][i-1] = q[i-1];
16 }
17
18 for(int len = 1; len<=n; len++)
19 {
20 for(int i = 1; i<=n-len+1; i++)
21 {
22 int j = i+len-1;
23 e[i][j] = INF;
24 w[i][j] = w[i][j-1] + p[j] + q[j];
25 for(int r = i; r<=j; r++)
26 {
27 double t = e[i][r-1] + e[r+1][j] + w[i][j];
28 if(t<e[i][j])
29 {
30 e[i][j]=t;
31 root[i][j] = r;
32 }
33 }
34 }
35 }
36 }
37
38 int main()
39 {
40 int n;
41 while(scanf("%d", &n)!=EOF)
42 {
43 getchar();
44 for(int i = 1; i<=n; i++)
45 scanf("%lf", &p[i]);
46 getchar();
47 for(int i =0; i<=n; i++)
48 scanf("%lf", &q[i]);
49 getchar();
50 optimalBST(n);
51 printf("%.3lf\n", e[1][n]);
52 }
53 } View Code
參考代碼：
1 //最優二叉查找樹
2
3 #include <iostream>
4
5 using namespace std;
6
7 const int MaxVal = 9999;
8
9 const int n = 5;
10 //搜尋到根節點和虛拟鍵的機率
11 double p[n + 1] = {-1,0.15,0.1,0.05,0.1,0.2};
12 double q[n + 1] = {0.05,0.1,0.05,0.05,0.05,0.1};
13
14 int root[n + 1][n + 1];//記錄根節點
15 double w[n + 2][n + 2];//子樹機率總和
16 double e[n + 2][n + 2];//子樹期望代價
17
18 void optimalBST(double *p,double *q,int n)
19 {
20 //初始化隻包括虛拟鍵的子樹
21 for (int i = 1;i <= n + 1;++i)
22 {
23 w[i][i - 1] = q[i - 1];
24 e[i][i - 1] = q[i - 1];
25 }
26
27 //由下到上，由左到右逐漸計算
28 for (int len = 1;len <= n;++len)
29 {
30 for (int i = 1;i <= n - len + 1;++i)
31 {
32 int j = i + len - 1;
33 e[i][j] = MaxVal;
34 w[i][j] = w[i][j - 1] + p[j] + q[j];
35 //求取最小代價的子樹的根
36 for (int k = i;k <= j;++k)
37 {
38 double temp = e[i][k - 1] + e[k + 1][j] + w[i][j];
39 if (temp < e[i][j])
40 {
41 e[i][j] = temp;
42 root[i][j] = k;
43 }
44 }
45 }
46 }
47 }
48
49 //輸出最優二叉查找樹所有子樹的根
50 void printRoot()
51 {
52 cout << "各子樹的根：" << endl;
53 for (int i = 1;i <= n;++i)
54 {
55 for (int j = 1;j <= n;++j)
56 {
57 cout << root[i][j] << " ";
58 }
59 cout << endl;
60 }
61 cout << endl;
62 }
63
64 //列印最優二叉查找樹的結構
65 //列印出[i,j]子樹，它是根r的左子樹和右子樹
66 void printOptimalBST(int i,int j,int r)
67 {
68 int rootChild = root[i][j];//子樹根節點
69 if (rootChild == root[1][n])
70 {
71 //輸出整棵樹的根
72 cout << "k" << rootChild << "是根" << endl;
73 printOptimalBST(i,rootChild - 1,rootChild);
74 printOptimalBST(rootChild + 1,j,rootChild);
75 return;
76 }
77
78 if (j < i - 1)
79 {
80 return;
81 }
82 else if (j == i - 1)//遇到虛拟鍵
83 {
84 if (j < r)
85 {
86 cout << "d" << j << "是" << "k" << r << "的左孩子" << endl;
87 }
88 else
89 cout << "d" << j << "是" << "k" << r << "的右孩子" << endl;
90 return;
91 }
92 else//遇到内部結點
93 {
94 if (rootChild < r)
95 {
96 cout << "k" << rootChild << "是" << "k" << r << "的左孩子" << endl;
97 }
98 else
99 cout << "k" << rootChild << "是" << "k" << r << "的右孩子" << endl;
100 }
101
102 printOptimalBST(i,rootChild - 1,rootChild);
103 printOptimalBST(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循環：從下到上計算表中每一行的值，可以充分利用前面計算出來的結果。如果每當計算e[i][j]的時候都從頭開始計算w[i][j]，那麼需要O(j-i)步加法，但是将這些值儲存在表w[1...n+1][0...n]中，就避免這些複雜的計算。