一、問題定義

1.1 二叉搜索樹

二叉搜索樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹： 若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值； 若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值； 它的左、右子樹也分別為二叉搜索樹。

規(guī)定樹根為第0層，圓結(jié)點(diǎn)為數(shù)據(jù)，方結(jié)點(diǎn)為數(shù)據(jù)之間的空隙。

1.2 概率分布

實(shí)際上每個數(shù)據(jù)出現(xiàn)的概率是不同的，給定序列$S=<x_1,x_2,...,x_n>$，構(gòu)造二叉搜索樹，形成了$n$個結(jié)點(diǎn)$x_1,x_2,...,x_n$，和$n+1$個空隙$(x_0,x_1),(x_1,x_2),...,(x_{n?1},x_n),(x_n,x_{n+1})$，其中$x_0=?\infty ,x_{n+1}=+\infty$

記$x$在$x_i$出現(xiàn)的概率為$b_i$，在空隙$(x_i,x_{i+1})$的概率為$a_i$，則$S$的存取概率分布為$P=<a_0,b_1,a_1,b_2,a_2,...,b_n,a_n>$

1.3 檢索數(shù)據(jù)的平均時間

對于數(shù)據(jù)集$S=<x_1,x_2,...,x_n>$和存取概率分布$P=<a_0,b_1,a_1,b_2,a_2,...,b_n,a_n>$：

規(guī)定樹根為第0層，結(jié)點(diǎn)$x_i$在$T$中的深度是$d(x_i),i=1,2,\dots ,n$，空隙$L_j$的深度為$d(L_j),j=0,1,\dots ,n$，平均比較次數(shù)為：
$$m(T)=\sum _{i=1}^n{b}_i(1+d(x_i))+\sum _{j=0}^n{a}_{j}d(L_j)$$
例如，給定樹：

$S=<1,2,3,4,5,6>$，$P=<0.04,?0.1?,0.01,?0.2?,0.05,?0.2?,0.02,?0.1?,0.02,?0.1?,0.07,?0.05?,0.04>$（$p_{x_i}$用**包圍）

則平均檢索時間為：

$m(T_1)=[1\times 0.1+2\times (0.2+0.05)+3\times (0.1+0.2+0.1)]+[3\times (0.04+0.01+0.05+0.02+0.02+0.07)+2\times 0.04]=2.51$

1.4 最優(yōu)二叉搜索樹問題

對于數(shù)據(jù)集$S=<x_1,x_2,...,x_n>$和存取概率分布$P=<a_0,b_1,a_1,b_2,a_2,...,b_n,a_n>$，不同的樹的組織形式會產(chǎn)生不同的平均檢索時間，如何求一棵平均比較次數(shù)最少的二叉搜索樹？

二、算法

2.1 分析問題結(jié)構(gòu)

以$(i,j)$為界劃分子問題：

令$S[i,j]=<x_i,x_{i+1},\dots ,x_j>$，存取概率分布：$P=<a_{i?},b_i,a_i,b_{i+1},...,b_j,a_j>$

2.2 建立遞推關(guān)系

假設(shè)以$x_k$作為樹的根，則樹被劃分為三部分：

左子樹：$S[i,k?1],P[i,k?1]$

根：$x_k$

右子樹：$S[k+1,j],P[k+1,j]$

令$w[i,j]={\sum }_{p=i?1}^j{a}_p+{\sum }_{q=i}^j{b}_q$，表示$x_i$到$x_j$之間所有概率（數(shù)據(jù)和空隙）之和；設(shè)$m[i,j]$是相對于輸入$S[i,j]$和$P[i,j]$的最優(yōu)二叉搜索樹的平均比較次數(shù)

則可建立遞推方程：
m [ i , j ] = min ? i ≤ k ≤ j { m [ i , k ? 1 ] + m [ k + 1 , j ] + w [ i , j ] } 1 ≤ i ≤ j ≤ n m [ i , i ? 1 ] = 0 , i = 1 , 2 , . . . , n m[i,j]=\min_{i\leq k\leq j}\left \{ m[i,k-1]+m[k+1,j]+w[i,j] \right \} \quad 1\leq i\leq j\leq n \\ m[i,i-1]=0, \quad i=1,2,...,n m[i,j]=i≤k≤jmin?{m[i,k?1]+m[k+1,j]+w[i,j]}1≤i≤j≤nm[i,i?1]=0,i=1,2,...,n

（1）為了不遺漏最優(yōu)解，所以需要從$x_1$到$x_k$依次選取做根嘗試，選出最小值

（2）$m[i,k?1]$表示以$x_k$做根的最優(yōu)左子樹的比較次數(shù)

（3）$m[k+1,j]$表示以$x_k$做根的最優(yōu)右子樹的比較次數(shù)

（4）對于給定的數(shù)據(jù)$x$，需要先與根$x_k$進(jìn)行比較后才可以進(jìn)入到左子樹或右子樹；而由于使用根$x_k$將左子樹和右子樹連接起來，子樹的每個結(jié)點(diǎn)高度均增加了一層，所以在比較次數(shù)上也要加1，所以$w[i,j]$是由增加的左子樹的比較次數(shù)、增加的右子樹的比較次數(shù)、和根的比較次數(shù)之和

$w[i,j]$的證明：

由根$x_k$引起的比較次數(shù)增加為：

2.3 自底向上計(jì)算

初始化：當(dāng)左子樹或右子樹為空時，其平均查找數(shù)為0
$$m[i,i?1]=0,i=1,2,...,n$$

不妨以$m[1,4]$來觀察：
$$m[1,4]=min?\begin{array}{cc}m[1,0]+m[2,4]+w[1,4]& k=1\\ m[1,1]+m[3,4]+w[1,4]& k=2\\ m[1,2]+m[4,4]+w[1,4]& k=3\\ m[1,3]+m[5,4]+w[1,4]& k=4\end{array}$$

顯然，要計(jì)算一個值，我們需要計(jì)算它一行一列的數(shù)據(jù)，因此確定計(jì)算順序：

2.4 追蹤最優(yōu)方案

構(gòu)造追蹤數(shù)組$Rec[\mathrm{1..}n,\mathrm{1..}n]$，$Rec[i,j]$表示$S[i,j]$的根節(jié)點(diǎn)$x_k$。

在計(jì)算$m[i,j]$的過程中，選出最小的$k$，記錄$Rec[i,j]=k$

追蹤時，從$Rec[1,n]$出發(fā)，假設(shè)$Rec[1,n]=k$，則說明在$x_k$處進(jìn)行了分割，分為子樹$m[1,k]$和$m[k+1,n]$，再分別查看$Rec[1,k]$和$Rec[k+1,n]$…

如此尋找直至對角線部分。

2.5 復(fù)雜度分析

時間復(fù)雜度$O(n^3)$

空間復(fù)雜度$O(n^2)$文章來源地址http://www.zghlxwxcb.cn/news/detail-597272.html

到了這里，關(guān)于【動態(tài)規(guī)劃】最優(yōu)二叉搜索樹——算法設(shè)計(jì)與分析的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！