您好,欢迎访问欧亿体育!

020-88886892

全国咨询热线

您现在所在位置: 主页 > 通知资讯

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

更新时间:2024-01-14

文章目录


一、问题定义

1.1 二叉搜索树

二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉搜索树。

规定树根为第0层,圆结点为数据,方结点为数据之间的空隙。


1.2 概率分布

实际上每个数据出现的概率是不同的,给定序列 S = < x 1 , x 2 , . . . , x n > S= S=<x1,x2,...,xn>,构造二叉搜索树,形成了 n n n个结点 x 1 , x 2 , . . . , x n x_1,x_2,...,x_n x1,x2,...,xn,和 n + 1 n+1 n+1个空隙 ( x 0 , x 1 ) , ( x 1 , x 2 ) , . . . , ( x n − 1 , x n ) , ( x n , x n + 1 ) (x_0,x_1),(x_1,x_2),...,(x_{n-1},x_n),(x_n,x_{n+1}) (x0,x1),(x1,x2),...,(xn1,xn),(xn,xn+1),其中 x 0 = − ∞ , x n + 1 = + ∞ x_0=-\infin,x_{n+1}=+\infin x0=,xn+1=+

x x x x i x_i xi出现的概率为 b i b_i bi,在空隙 ( x i , x i + 1 ) (x_i,x_{i+1}) (xi,xi+1)的概率为 a i a_i ai,则 S S S的存取概率分布为 P = < a 0 , b 1 , a 1 , b 2 , a 2 , . . . , b n , a n > P= P=<a0,b1,a1,b2,a2,...,bn,an>


1.3 检索数据的平均时间

对于数据集 S = < x 1 , x 2 , . . . , x n > S= S=<x1,x2,...,xn>和存取概率分布 P = < a 0 , b 1 , a 1 , b 2 , a 2 , . . . , b n , a n > P= P=<a0,b1,a1,b2,a2,...,bn,an>

规定树根为第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=1nbi(1+d(xi))+j=0najd(Lj)
例如,给定树:

S = < 1 , 2 , 3 , 4 , 5 , 6 > S = < 1, 2, 3, 4, 5, 6 > 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 = < 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=<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 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 = < x 1 , x 2 , . . . , x n > S= S=<x1,x2,...,xn>和存取概率分布 P = < a 0 , b 1 , a 1 , b 2 , a 2 , . . . , b n , a n > P= P=<a0,b1,a1,b2,a2,...,bn,an>,不同的树的组织形式会产生不同的平均检索时间,如何求一棵平均比较次数最少的二叉搜索树?



二、算法

2.1 分析问题结构

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

S [ i , j ] = < x i , x i + 1 , … , x j > S [i, j] = < x_i , x_{i+1}, … , x_j > S[i,j]=<xi,xi+1,,xj>,存取概率分布: P = < a i − , b i , a i , b i + 1 , . . . , b j , a j > P= P=<ai,bi,ai,bi+1,...,bj,aj>


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,k1],P[i,k1]

根: 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=i1jap+q=ijbq,表示 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]=ikjmin{m[i,k1]+m[k+1,j]+w[i,j]}1ijnm[i,i1]=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,k1]表示以 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,i1]=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

0 1 2 3 4
0 NULL NULL NULL NULL NULL
1 0
2 NULL 0
3 NULL NULL 0
4 NULL NULL NULL 0
5 NULL NULL NULL NULL

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


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)

在线客服

ONLINE SERVICE

联系电话

020-88886892

返回顶部