【动态规划】最优二叉搜索树——算法设计与分析

P=

P=

1.3 检索数据的平均时间

对于数据集

S

=

S=

S=和存取概率分布

P

=

P=

P=：

规定树根为第0层，结点

x

i

x_i

xi​在

T

T

T中的深度是

d

(

x

i

)

,

i

=

1

,

2

,

…

,

n

d(x_i), i=1,2,…,n

d(xi​),i=1,2,…,n，空隙

L

j

L_j

Lj​的深度为

d

(

L

j

)

,

j

=

0

,

1

,

…

,

n

d(L_j),j=0,1,…,n

d(Lj​),j=0,1,…,n，平均比较次数为：

m

(

T

)

=

∑

i

=

1

n

b

i

(

1

+

d

(

x

i

)

)

+

∑

j

=

0

n

a

j

d

(

L

j

)

m(T)=\sum_{i=1}^{n}b_i(1+d(x_i))+ \sum_{j=0}^{n}a_jd(L_j)

m(T)=i=1∑n​bi​(1+d(xi​))+j=0∑n​aj​d(Lj​)

例如，给定树：

S

=

S =

S=，

P

=

P =

P=（

p

x

i

p_{x_i}

pxi​​用**包围）

则平均检索时间为：

m

(

T

1

)

=

[

1

×

0.1

+

2

×

(

0.2

+

0.05

)

+

3

×

(

0.1

+

0.2

+

0.1

)

]

+

[

3

×

(

0.04

+

0.01

+

0.05

+

0.02

+

0.02

+

0.07

)

+

2

×

0.04

]

=

2.51

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

m(T1​)=[1×0.1+2×(0.2+0.05)+3×(0.1+0.2+0.1)]+[3×(0.04+0.01+0.05+0.02+0.02+0.07)+2×0.04]=2.51

1.4 最优二叉搜索树问题

对于数据集

S

=

S=

S=和存取概率分布

P

=

P=

P=，不同的树的组织形式会产生不同的平均检索时间，如何求一棵平均比较次数最少的二叉搜索树？

二、算法

2.1 分析问题结构

以

(

i

,

j

)

(i,j)

(i,j)为界划分子问题：

令

S

[

i

,

j

]

=

S [i, j] =

S[i,j]=，存取概率分布：

P

=

P=

P=

2.2 建立递推关系

假设以

x

k

x_k

xk​作为树的根，则树被划分为三部分：

左子树：

S

[

i

,

k

−

1

]

,

P

[

i

,

k

−

1

]

S[ i, k−1], P[ i, k−1]

S[i,k−1],P[i,k−1]

根：

x

k

x_k

xk​

右子树：

S

[

k

+

1

,

j

]

,

P

[

k

+

1

,

j

]

S[ k+1, j ], P[ k+1, j ]

S[k+1,j],P[k+1,j]

令

w

[

i

,

j

]

=

∑

p

=

i

−

1

j

a

p

+

∑

q

=

i

j

b

q

{w[i,j]=\sum_{p=i-1}^{j}a_p+ \sum_{q=i}^{j}b_q }

w[i,j]=∑p=i−1j​ap​+∑q=ij​bq​，表示

x

i

x_i

xi​到

x

j

x_j

xj​之间所有概率（数据和空隙）之和；设

m

[

i

,

j

]

m[i,j]

m[i,j]是相对于输入

S

[

i

,

j

]

S[i,j]

S[i,j]和

P

[

i

,

j

]

P[i,j]

P[i,j]的最优二叉搜索树的平均比较次数

则可建立递推方程：

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）为了不遗漏最优解，所以需要从

x

1

x_1

x1​到

x

k

x_k

xk​依次选取做根尝试，选出最小值

（2）

m

[

i

,

k

−

1

]

m[i,k-1]

m[i,k−1]表示以

x

k

x_k

xk​做根的最优左子树的比较次数

（3）

m

[

k

+

1

,

j

]

m[k+1,j]

m[k+1,j]表示以

x

k

x_k

xk​做根的最优右子树的比较次数

（4）对于给定的数据

x

x

x，需要先与根

x

k

x_k

xk​进行比较后才可以进入到左子树或右子树；而由于使用根

x

k

x_k

xk​将左子树和右子树连接起来，子树的每个结点高度均增加了一层，所以在比较次数上也要加1，所以

w

[

i

,

j

]

w[i,j]

w[i,j]是由增加的左子树的比较次数、增加的右子树的比较次数、和根的比较次数之和

w

[

i

,

j

]

w[i,j]

w[i,j]的证明：

由根

x

k

x_k

xk​引起的比较次数增加为：

2.3 自底向上计算

初始化：当左子树或右子树为空时，其平均查找数为0

m

[

i

,

i

−

1

]

=

0

,

i

=

1

,

2

,

.

.

.

,

n

m[i,i-1]=0, \quad i=1,2,…,n

m[i,i−1]=0,i=1,2,…,n

不妨以

m

[

1

,

4

]

m[1,4]

m[1,4]来观察：

m

[

1

,

4

]

=

m

i

n

{

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

m[1,4]=min\left\{\begin{matrix} 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{matrix}\right.

m[1,4]=min⎩
⎨
⎧​m[1,0]+m[2,4]+w[1,4]m[1,1]+m[3,4]+w[1,4]m[1,2]+m[4,4]+w[1,4]m[1,3]+m[5,4]+w[1,4]​k=1k=2k=3k=4​

显然，要计算一个值，我们需要计算它一行一列的数据，因此确定计算顺序：

2.4 追踪最优方案

构造追踪数组

R

e

c

[

1..

n

,

1..

n

]

Rec[1..n,1..n]

Rec[1..n,1..n]，

R

e

c

[

i

,

j

]

Rec[i,j]

Rec[i,j]表示

S

[

i

,

j

]

S[i,j]

S[i,j]的根节点

x

k

x_k

xk​。

在计算

m

[

i

,

j

]

m[i,j]

m[i,j]的过程中，选出最小的

k

k

k，记录

R

e

c

[

i

,

j

]

=

k

Rec[i,j]=k

Rec[i,j]=k

追踪时，从

R

e

c

[

1

,

n

]

Rec[1,n]

Rec[1,n]出发，假设

R

e

c

[

1

,

n

]

=

k

Rec[1,n]=k

Rec[1,n]=k，则说明在

x

k

x_k

xk​处进行了分割，分为子树

m

[

1

,

k

]

m[1,k]

m[1,k]和

m

[

k

+

1

,

n

]

m[k+1,n]

m[k+1,n]，再分别查看

R

e

c

[

1

,

k

]

Rec[1,k]

Rec[1,k]和

R

e

c

[

k

+

1

,

n

]

Rec[k+1,n]

Rec[k+1,n]…

如此寻找直至对角线部分。

2.5 复杂度分析

时间复杂度

O

(

n

3

)

O(n^3)

O(n3)

空间复杂度

O

(

n

2

)

O(n^2)

O(n2)