最優(yōu)二叉搜索樹(Optimal Binary Search Tree)
- 前言
如果有序數(shù)組或有序表中的各個元素查找概率相等，那么采用二叉搜索樹(BST)進(jìn)行折半查找，性能最優(yōu)。如果有序表中各個記錄的查找概率不相等，情況又如何呢？
先看一個具體例子。已知有序表keys， 同時給出各個元素的查詢頻率，注意到各個元素的查詢頻率不相同。要求在此條件下，構(gòu)造出最優(yōu)搜索二叉查找樹。
keys[] = {10, 12, 20},
freq[] = {34, 8, 50}
如果各個元素概率相等，在此基礎(chǔ)上，構(gòu)造二叉搜索樹，結(jié)果為一顆平衡搜索樹。
12
/ \
10 20
考慮各個元素的查找概率和二叉樹的不同形式，可以構(gòu)造五顆不同的二叉搜索樹，最優(yōu)二叉搜索樹則是帶權(quán)路徑最小的的和:
P
a
t
h
?
W
e
i
g
h
t
=
Σ
（
w
e
i
g
h
t
[
i
]
?
h
e
i
g
h
t
[
i
]
)
(
0
<
=
i
<
n
)
Path\ Weight=Σ（weight[i]*height[i]) (0<=i<n)
Path?Weight=Σ（weight[i]?height[i])(0<=i<n)
10 12 20 10 20
\ / \ / \ /
12 10 20 12 20 10
\ / / \
20 10 12 12
I II III IV V
分別對5種形式的二叉搜索樹的帶權(quán)路徑和進(jìn)行計算，采用列表的形式儲存計算結(jié)果，則得到下述列表形式，
| 二叉樹編號 | 帶權(quán)路徑和 | 備注 |
|---|---|---|
| I | =>34+8*2+50*3=200 | |
| II | =>8+34*2+50*2=176 | |
| III | =>50+8*2+34*3=168 | |
| IV | =>34+50*2+8*3=158 | |
| V | =>50+34*2+8*3=142 | 最優(yōu)二叉搜索樹 |
可以得到結(jié)論，等概率的二叉搜索樹的帶權(quán)路徑和為176，并不是最優(yōu)二叉搜索樹，本例子中的最優(yōu)二叉搜索樹為第V種形式。還可以看出，最優(yōu)二叉搜索樹并不一定是深度最小的樹，第V種二叉樹的深度為3，第II種的普通的二叉搜索樹的深度為2，即第V種樹的深度比第II中多1，但是其帶權(quán)路徑和保持最小。另外還有一個結(jié)論，從本例中并不能明顯看出，根節(jié)點權(quán)值不一定是最大權(quán)值節(jié)點。
上述兩點聲明和表述主要是說明，構(gòu)造最小最優(yōu)二叉搜索樹不能簡單采用貪心算法，貪心算法通常把最大權(quán)值放在根結(jié)點，并且設(shè)法降低樹的高度，貪心算法并不能保證得到最優(yōu)二叉搜索樹。
- 問題求解
按照慣例，依照《算法導(dǎo)論》中的CRCC方法，采用動態(tài)規(guī)劃方法對最優(yōu)二叉搜索樹問題進(jìn)行求解。首先需要表征最優(yōu)問題解的基本結(jié)構(gòu)。
- 表征最優(yōu)問題解的結(jié)構(gòu)(Characterize the structure of the optimal solution)
考察最優(yōu)二叉搜索樹的任意一顆子樹，子樹包含某個連續(xù)元素:
k
i
.
.
.
.
k
j
,
?
1
≤
i
≤
j
≤
n
k_i....k_j, \ 1≤i≤j≤n
ki?....kj?,?1≤i≤j≤n
根據(jù)遞歸特性，子樹本身一定屬于最優(yōu)二叉搜索樹，結(jié)論可以用反證法進(jìn)行證明，不再贅述。分析對象為這顆子樹，對于這顆子樹我們可以分為左右子樹，(ki…kr-1) 和 (kr+1…kj), 把這兩顆子樹作為kr的左右子樹，相當(dāng)于原來的子樹的每個節(jié)點的深度都增加1，同時考慮根節(jié)點kr的權(quán)值，那么選擇r作為根節(jié)點的代價為w(i,j)。r可以在區(qū)間【i，j】之間進(jìn)行變化，但是選擇的代價都是w(i,j)。
- 遞歸定義最優(yōu)解的值(Recursively define the value of the optimal solution)
遞歸定義可以描述為，在ki…kj元素范圍內(nèi)，嘗試所有的可能情況，尋找最優(yōu)二叉搜索樹，在暫時不考慮重復(fù)子問題的前提下，問題呈現(xiàn)出窮盡/窮舉的特征。
對于任意根節(jié)點r，根節(jié)點位于【i，j】，定義f(i,j)為此節(jié)點r的帶權(quán)路徑和，采用數(shù)學(xué)語言可以描述問題，
f
(
i
,
j
)
=
f
(
i
,
r
?
1
)
+
f
(
r
+
1
,
j
)
+
w
(
i
,
j
)
;
f(i,j)=f(i,r-1)+f(r+1,j)+w(i,j);
f(i,j)=f(i,r?1)+f(r+1,j)+w(i,j);
這就是狀態(tài)轉(zhuǎn)移方程，狀態(tài)轉(zhuǎn)移方程的遞歸過程實際上分支遞減多叉樹，第一層多叉樹的分枝樹為j-i+1, 隨著遞歸的深入，多叉樹的分枝數(shù)不斷減少。最優(yōu)解涉及到在整個區(qū)間上求最小值，得到最后的遞歸形式的最優(yōu)解為，
f
(
i
,
j
)
=
m
i
n
{
f
(
i
,
r
?
1
)
+
f
(
r
+
1
,
j
)
+
w
(
i
,
j
)
}
;
?
i
≤
r
≤
j
f(i,j)=min\{f(i,r-1)+f(r+1,j)+w(i,j)\}; \ i≤r≤j
f(i,j)=min{f(i,r?1)+f(r+1,j)+w(i,j)};?i≤r≤j
- 求解最優(yōu)解的值(Compute the value of the optimal solution)
如果采用遞歸形式，那么求解最優(yōu)解的值的關(guān)鍵步驟就是定義遞歸的終止條件，也可以理解為遞歸的出口。遞歸出口存在兩種形式：
? - i>j，這種情況表明，遍歷完左邊的關(guān)鍵字后，仍然沒有找到關(guān)鍵字的匹配，此情況下，直接返回0
? - i==j，這種情況表明，找到了匹配的關(guān)鍵字，直接返回本關(guān)鍵字的頻率值即可
再看一個具體的例子，鑒定有四個元素，每個元素出現(xiàn)的頻次各不相同，要求構(gòu)造出最優(yōu)二叉搜索樹，從前面得知，如果有四個元素，那么第一次分支就會出現(xiàn)4叉分支，由于分支比較復(fù)雜，我們分幾張圖加以闡述。
分枝1(Branch 1)，分枝1的二叉搜索樹的最小路徑和為233，右邊為二叉搜索樹，橙色框內(nèi)需要代表頻率數(shù)組元素的下標(biāo)。肢體的一提的是，每個分枝實際上由兩部分組成，這兩部分 分別代表二叉搜索樹的左右子孩子。簡單理解，每個分枝由兩個孩子構(gòu)成（可能存在節(jié)點沒有孩子節(jié)點的情況）。
分枝2/分枝3，相同思路，分枝2和分枝3的帶權(quán)路徑和分別為251 和192。左右兩邊的橙色的二叉樹分別對應(yīng)其相應(yīng)不同的二叉搜索樹。
分枝4，分枝4的帶權(quán)路徑和為259，右邊的橙色的樹代表其帶權(quán)路徑的和。
綜上，分枝3為本問題的最優(yōu)二叉搜索樹。
動態(tài)規(guī)劃的特征之二就是，不同分支中會出現(xiàn)重疊子問題(overlapping subproblem)，如果仔細(xì)觀察分枝1和分枝4，就會發(fā)現(xiàn)F(1,2)子問題都包含再兩個分枝當(dāng)中，這是應(yīng)用遞歸記憶的基礎(chǔ)，如果沒有重復(fù)子問題，那么遞歸記就失去其相應(yīng)意義。
- 構(gòu)建具體的解
上述遞歸僅可以求出最優(yōu)二叉搜索樹的最小帶權(quán)路徑和，但是并無法構(gòu)造相應(yīng)的最優(yōu)二叉搜索樹，這就需要追加額外的數(shù)組root[n+2][n+2]來記錄每個【i，j】區(qū)間中的根節(jié)點的選擇root[i][j]=r。
- 代碼實現(xiàn)
3.1 定義頭文件
/**
* @file optimal_binary_search_tree.h
* @author your name (you@domain.com)
* @brief
* @version 0.1
* @date 2023-03-31
*
* @copyright Copyright (c) 2023
*
*/
#ifndef OPTIMAL_BINARY_SEARCH_TREE_H
#define OPTIMAL_BINARY_SEARCH_TREE_H
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
/**
* @brief Create the optimal binary search tree on the sorted array
*
* @param freq Frequency array list
* @param i Search start point
* @param j Search end point
* @return int -Return weight of optinal_binary search tree weight
*/
int optimal_BST(int *freq,int i, int j);
/**
* @brief Calculate the sum of frequency list
*
* @param freq Frequency list
* @param i Search start point
* @param j Search end point
* @return int -Return the sume from index=i to index=j
*/
int weight_sum(int *freq, int i, int j);
#endif
3.2 函數(shù)的實現(xiàn)
/**
* @file optimal_binary_search_tree.c
* @author your name (you@domain.com)
* @brief
* @version 0.1
* @date 2023-03-31
*
* @copyright Copyright (c) 2023
*
*/
#ifndef OPTIMAL_BINARY_SEARCH_TREE_C
#define OPTIMAL_BINARY_SEARCH_TREE_C
#include "optimal_binary_search_tree.h"
int optimal_BST(int *freq, int i, int j)
{
int r;
int min_value;
int left;
int right;
int c;
if(i>j)
{
return 0;
}
if(i==j)
{
return freq[i];
}
min_value=INT_MAX;
for (r = i; r <= j; r++) // int freq[] = {34,8,50,25};
{
left=optimal_BST(freq,i,r-1);
right=optimal_BST(freq,r+1,j);
c=left+right+weight_sum(freq,i,j);
// int freq[] = {34,8,50,25};
if(c<min_value)
{
min_value=c;
}
}
return min_value;
}
int weight_sum(int *freq, int i, int j)
{
int k;
int sum=0;
for(k=i;k<=j;k++)
{
sum+=freq[k];
}
return sum;
}
#endif
3.3 測試函數(shù)
/**
* @file optimal_binary_search_tree_main.c
* @author your name (you@domain.com)
* @brief
* @version 0.1
* @date 2023-03-31
*
* @copyright Copyright (c) 2023
*
*/
#ifndef OPTIMAL_BINARY_SEARCH_TREE_MAIN_C
#define OPTIMAL_BINARY_SEARCH_TREE_MAIN_C
#include "optimal_binary_search_tree.c"
int main(void)
{
int freq[] = {34,8,50,25};
int n=sizeof(freq)/sizeof(int);
int min_value;
min_value=optimal_BST(freq,0,n-1);
printf("The miminum value is %d\n",min_value);
getchar();
return EXIT_SUCCESS;
}
#endif
- 小結(jié)
構(gòu)建二叉搜索樹的過程，采用和矩陣鏈相乘相同的思路，通過直接求解子問題[i,j]，從而最終求解全局問題。這個過程中需要特別注意，由于解的結(jié)果僅為矩陣中的上三角或下三角，所以需要引入長度的概念，對i和j進(jìn)行不同的限制，最終達(dá)到求解的目的。文章來源：http://www.zghlxwxcb.cn/news/detail-522828.html
參考資料：文章來源地址http://www.zghlxwxcb.cn/news/detail-522828.html
- 《Introduction to algorithm, 4ed》
- Optimal Binary Search Tree | DP-24 - GeeksforGeeks
到了這里，關(guān)于最優(yōu)二叉搜索樹(Optimal Binary Search Tree)_20230401的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
