算法与数据结构学习笔记-最优二叉搜索树(optimal binary search tree)的动态规划实现详解

一串字符中可能进行多次查找，每个字符被查找到的频率都不同，如何根据字符被查找到的频率，建立一个二叉搜索树，使得花费时间最少呢？

题目：给定一列按升序排列的键值$K=[k_1,k_2,...,k_n]$K=[k1​,k2​,...,kn​]和它们被搜索到的频率$P=[p_1,p_2,...,p_n]$P=[p1​,p2​,...,pn​]，建立一个二叉搜索树，使得搜索的平均费用最低。要求输入键值和频率数组，返回搜索树及其费用。

二叉树的费用如何计算呢？我们知道节点越低，搜索经过的路程越长。因此定义搜索的花费$cost(k_i)=depth(k_i)+1$cost(ki​)=depth(ki​)+1。因为对根节点进行查找也需要一次操作，而根节点的深度为0,所以定义每个节点的搜索花费为$depth(k_i)+1$depth(ki​)+1。每一个节点$k_i$ki​被搜索到的频率为$p_i$pi​，因此整棵树T的费用定义为：

$E(T)=\sum_{i=1}^{n} cost(k_i) \cdot p_i= \sum_{i=1}^{n} (depth(k_i)+1)\cdot p_i= \sum_{i=1}^{n} depth(k_i) \cdot p_i+\sum_{i=1}^{n} p_i$E(T)=i=1∑n​cost(ki​)⋅pi​=i=1∑n​(depth(ki​)+1)⋅pi​=i=1∑n​depth(ki​)⋅pi​+i=1∑n​pi​
而$\sum_{i=1}^{n} p_i$∑i=1n​pi​的值为1（每个键值的概率相加），因此
$E(T)=\sum_{i=1}^{n} depth(k_i) \cdot p_i+1$E(T)=i=1∑n​depth(ki​)⋅pi​+1

在搜索过程中会出现对给出的键值之外的值的搜索，为了方便，我们给搜索树的每个叶子节点加上两个“假的”节点，并给出搜索到假节点的概率用$q_0, q_1, ...,q_n$q0​,q1​,...,qn​表示。

用该公式尝试计算一棵二叉搜索树的费用：

i	1	2	3	4	5
$k_i$ki​	0.25	0.20	0.05	0.20	0.30

左树$E(T)=\sum_{i=1}^{n} depth(k_i)\cdot p_i+1=0.20×0+0.25×1+0.20×1+0.05×2+0.30×2+1=2.15$E(T)=i=1∑n​depth(ki​)⋅pi​+1=0.20×0+0.25×1+0.20×1+0.05×2+0.30×2+1=2.15
右树$E(T)=\sum_{i=1}^{n} depth(k_i)\cdot p_i+1=0.20×0+0.25×1+0.30×1+0.20×2+0.05×3+1=2.10$E(T)=i=1∑n​depth(ki​)⋅pi​+1=0.20×0+0.25×1+0.30×1+0.20×2+0.05×3+1=2.10

显然右树更理想。

有时会对给出键值之外的值进行搜索，这部分搜索的概率不为0，导致$\sum_{i=0}^np_i<1$∑i=0n​pi​<1，这时要把搜索不到的部分也加到搜索树上，也就是加上一些“假节点”，当搜索到假节点时，表示搜索失败。这部分概率用$q_0,q_1,q_2,...,q_n$q0​,q1​,q2​,...,qn​表示。

i	0	1	2	3	4	5
$p_i$pi​		0.15	0.10	0.05	0.10	0.20
$q_i$qi​	0.05	0.10	0.05	0.05	0.05	0.10

左树$E(T)=\sum_{i=1}^{n} depth(k_i)\cdot p_i+\sum_{i=0}^{n} depth(k_i)\cdot q_i+1\\=0.10×0+0.15×1+0.10×1+0.05×2+0.20×2+0.05×2+0.10×2+0.05×3+0.05×3+0.05×3+0.10×3+1\\=2.80$E(T)=i=1∑n​depth(ki​)⋅pi​+i=0∑n​depth(ki​)⋅qi​+1=0.10×0+0.15×1+0.10×1+0.05×2+0.20×2+0.05×2+0.10×2+0.05×3+0.05×3+0.05×3+0.10×3+1=2.80

右树$E(T)=\sum_{i=1}^{n} depth(k_i)\cdot p_i+\sum_{i=0}^{n} depth(k_i)\cdot q_i+1\\=0.10×0+0.15×1+0.20×1+0.10×2+0.05×3+0.05×2+0.10×2+0.05×3+0.05×3+0.05×3+0.10×3+1\\=2.75$E(T)=i=1∑n​depth(ki​)⋅pi​+i=0∑n​depth(ki​)⋅qi​+1=0.10×0+0.15×1+0.20×1+0.10×2+0.05×3+0.05×2+0.10×2+0.05×3+0.05×3+0.05×3+0.10×3+1=2.75

右树更优。

这道题是否满足动态规划解题的条件呢？

可以把每一个节点看成一棵二叉树的根节点，如果整棵二叉树是最优的（搜索费用最低），那么每一棵子树里面节点的排列也是最优的。否则可以通过重新排列子树的节点使整棵树的费用降低。因此该问题满足”最优子结构“。

寻找递归公式使用如下方式：对所有$i\geq 1, j\leq n, j\geq i-1$i≥1,j≤n,j≥i−1，对于从$k_i到k_j$ki​到kj​的一系列节点，每一个节点都有可能是使$k_i到k_j$ki​到kj​成为最优搜索树的根节点，因此让$k_i到k_j$ki​到kj​的每一个节点都当一次根节点$k_r$kr​，并让$k_i到k_{r-1}$ki​到kr−1​成为最优二叉搜索树，且让$k_{i+1}到k_j$ki+1​到kj​成为最优二叉搜索树，并计算相应的$E(k_r)$E(kr​)。在所有的$E(k_r)$E(kr​)里找到最小值并记录$E(k_r)$E(kr​)和$r$r值。

定义$k_i...k_j$ki​...kj​组成的最优二叉搜索树的费用为$e[i,j]$e[i,j]（与上文的$E(T)$E(T)类似），那么当$k_r(i\leq r \leq j)$kr​(i≤r≤j)作为根节点时，左树最低费用为$e[i,r-1]$e[i,r−1]，右树最低费用为$e[r+1,i]$e[r+1,i]，根节点费用为$p_r$pr​。然而，整棵树的费用不能简单地将左树费用，根节点费用，右树费用相加，因为$e[i,r-1]$e[i,r−1]和$e[r+1,i]$e[r+1,i]分别为左右树单独成树的费用。当它们成为$k_r$kr​的左子树和右子树，所有节点的深度加1，根据公式$E(T)=\sum_{i=1}^{n} depth(k_i)\cdot p_i+\sum_{i=0}^{n} depth(k_i)\cdot q_i+1$E(T)=∑i=1n​depth(ki​)⋅pi​+∑i=0n​depth(ki​)⋅qi​+1，成为子树后$E(T)=\sum_{i=1}^{n} (depth(k_i)+1)\cdot p_i+\sum_{i=0}^{n} (depth(k_i)+1)\cdot q_i+1$E(T)=∑i=1n​(depth(ki​)+1)⋅pi​+∑i=0n​(depth(ki​)+1)⋅qi​+1，即$E'(T)=E(T)+\sum_{i=1}^{n} p_i+\sum_{i=0}^{n} q_i$E′(T)=E(T)+∑i=1n​pi​+∑i=0n​qi​。

定义一个新变量$w(i,j)=\sum_{l=i}^{j} p_l+\sum_{l=i}^{j} q_l$w(i,j)=∑l=ij​pl​+∑l=ij​ql​，那么
$e[i,j]=p_r+(e[i,r-1]+w(i,r-1))+(e[r+1,j]+w(r+1,j))$e[i,j]=pr​+(e[i,r−1]+w(i,r−1))+(e[r+1,j]+w(r+1,j))
可得
$e[i,j]=e[i,r-1]+e[r+1,j]+w(i,j)$e[i,j]=e[i,r−1]+e[r+1,j]+w(i,j)
这是递归公式的基础。当$j=i-1$j=i−1时是什么情况呢？，当把$k_r$kr​作为根节点时，$k_r$kr​的左子树应该是有$k_r...k_{r-1}$kr​...kr−1​这些节点。当$r=i$r=i时，$k_i$ki​的左子树有$k_i...k_{i-1}$ki​...ki−1​这些节点。但因为树的所有节点是从$k_i$ki​开始的，$k_{i-1}$ki−1​并不存在这棵树中。根节点$k_i$ki​也被排除在外。由之前对假节点的定义我们知道，这是一个假节点，表明搜索失败，且这是一棵只有假节点的单节点树，其费用为$q_{i-1}$qi−1​。由此可得：
$e[i,j]= \begin{cases} q_{i-1} & & {j=i-1}\\ \min_{i\leq r \leq j} (e[i,r-1]+e[r+1,j]+w(i,j)) & & {S_L \leq 0 < S_M} \end{cases}$e[i,j]={qi−1​mini≤r≤j​(e[i,r−1]+e[r+1,j]+w(i,j))​​j=i−1SL​≤0<SM​​

如果直接用递归实现，会对很多$e[i,j]$e[i,j]重复计算，比如寻找$k_1...k_5$k1​...k5​的最优树，当$r=2$r=2时，需要计算$k_3...k_5$k3​...k5​的最优解。寻找$k_3...k_7$k3​...k7​的最优树，当$r=6$r=6时，需要再次计算$k_3...k_5$k3​...k5​的最优解。因此有很多重叠的子问题，用动态规划解决能够提高效率。