簡述

什么是二叉樹

下面的這棵樹，就是二叉搜索樹

相對于什么最優

這里考慮的是ASL（average search length）平均搜索長度。即根據概率來生成ASL最小的搜索樹。

---

到這里，最優二叉搜索樹的概念就已經清楚了。

---

解決方法

如果是遞歸來搜索也是可以的，但是很明顯需要做很多的重復的計算。
為了解決這個問題，所以我們采用動態規劃來做，很明顯，這樣能降低計算的復雜度。

• 處理方法：動態規劃

在非葉節點上時候，為特定的數值，在葉子節點上時候，是一個區間（這里不懂可以再看上面的圖）

顯然，我們需要先用遞歸的方式來理解一下這個問題。

• w[i][j] = a[i-1] + b[i] +.. + b[j] + a[j]
• 其中，a[i]表示的是第i個區間的概率，b[i]表示的是第i個節點的概率
• w[i][i] = a[i-1] + b[i] + a[i] 這不就是一個只有一個非葉子節點的二叉樹么？
• 如果是只有一個非葉子節點的二叉搜索樹的話：我們這里很好求
• 進行擴展：我們現在只考慮這么的一棵樹，中間點為具體數值，那么就是非葉子節點。然后根據這個節點(設為節點k)的進行推理ASL[i][j] = b[k] * 1 + (ASL_Left_tree + 1) * W[i][k-1] + (ASL_Right_tree + 1) * W[k+1][j]
• 注意到，中間有部分可以提出來，得到ASL[i][j] = W[i][j] + (ASL_Left_tree ) * W[i][k-1] + (ASL_Right_tree ) * W[k+1][j] （這里W[i][j] = 1）
• 但是我們這里其實考慮的整棵數，對于更一般的，我們要考慮一個樹的一部分。
• ASL[i][j] = 1 + (ASL_Left_tree ) * W[i][k-1] + (ASL_Right_tree ) * W[k+1][j] 這是上面的整理。下面再接著推理。
• W[i][j] * ASL[i][j] = W[i][j] + (ASL_Left_tree ) * W[i][k-1] + (ASL_Right_tree ) * W[k+1][j] 注意，這里的W[i][j]都是在全局的樹上算的，因為這時候把左邊的W[i][j] 就類似的得到的我們想要的條件概率下是計算算法。
• 做類似的變換很容易發現，所謂左樹和右樹也是可以用i,j來表示的。然后，就得到一個很重要的 遞推公式
• W[i][j] * ASL[i][j] = W[i][j] + ASL[i][k-1] * W[i][k-1] + ASL[k+1][j] * W[k+1][j] 但是我們注意到這里的 w[i][j] * ASL[i][j] 其實可以作為一個整體來計算的。這里就設置為M[i][j]
• 所以公式變為了m[i][j] = w[i][j] + m[i][k-1] + m[k+1][j]。注意到，我們這里是假設了采用的是以第k個點作為分割點來構建子樹的。但是實際上這個最優的究竟該怎么搞，肯定是需要遍歷所有的可能的k來得到結果的。
• 所以，其實m[i][j] = w[i][j] + min(m[i][k-1] + m[k+1][j])。但是我們這里需要注意到，我們想要的整棵數的ASL其實就是m[1][N]，而此時的概率為1了，所以得到的相等。

邊界條件討論：

• w[i+1][i] 這種情況究竟是算什么呢？我們這里設置為a[i]
• m[i+1][i]這種情況呢？我們令它為0。這樣，我們在利用上面的公式推理出來的結果的時候，就得到了m[i][i] = w[i][i]。
• 至于它為0，其實很好證明，由于在ASL[i+1][i]肯定要是0才對的。

程序實現細節

主要是注意一下，實現的時候，如何安排數據。建議的話，將b的那個數組前面空出一個來，這樣的話，就不需要修改太多的公式。
原因如下：

• w[i][j] = a[i-1] + b[i] +.. + b[j] + a[j]
• 為了避免程序實現的時候越界。（否則就需要修改公式了，這里先可以先完成之后，再考慮優化的問題）

---

看到這，如果你有去手動實現的話，你會意識到另外一個問題。這個可行的k究竟是什么？

• 由于我們之前已經談到了設置了時候，我們講b的那個數組第一個位置放空，那么來說i和j都是從1開始遍歷起的，終止當然就是以N作為終止點。
• 知道上面的這些之后，我們就很容易理清了，我們嘗試將i到j上的所有節點

C++代碼

注釋部分寫好了詳細的代碼說明~
main函數開始部分是自動生成數據來進行測試

#include <iostream> using namespace std; #include <string> #define N 15int S[N]; double b[N + 1]; double a[N + 1]; // w[i][j] 表示i,j段的概率 // double w[N + 2][N + 2]; // w[i][j] = a[i-1] + b[i] +...+b[j] + a[j] double m[N + 2][N + 2]; int divided_point[N + 1][N + 1]; string getAns(int begin, int end); int main() {double sum = 0;for (int i = 0; i < N; ++i) {S[i] = 2 * i + 1;b[i+1] = 0.6 / (N+1);a[i] = 0.4 / (N+1);sum += (a[i] + b[i+1]);}b[0] = 0;a[N] = 1 - sum;/*for (int i = 0; i < N; ++i) {S[i] = 2 * i + 1;a[i + 1] = 0.04;b[i + 1] = 0.06;}a[0] = 0.1;b[0] = 0;*/// 初始化for (int i = 0; i <= N; ++i) {w[i + 1][i] = a[i];m[i + 1][i] = 0;// ASL[i][i-1]為0！}// r表示的是長度for (int r = 0; r < N; ++r)for (int i = 1; i <= N-r; i++) {// i表示的是起始點int j = i + r; // j表示的是終點// 由w[i][j]構造函數很容易得到w[i][j] = w[i][j - 1] + a[j] + b[j];m[i][j] = m[i + 1][j]; // 因為m[i][i-1]為0divided_point[i][j] = i;// 中間劃分點設為b[i] k為滑動的移動點for (int k = i + 1; k <= j; k++) {double t = m[i][k - 1] + m[k + 1][j];if (t < m[i][j]) { m[i][j] = t; divided_point[i][j] = k;}}m[i][j] += w[i][j];}cout << m[1][N] << " " << w[1][N] << endl;system("pause"); }

總結

以上是生活随笔為你收集整理的最优二叉搜索树探究【C/C++】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。