《算法导论》读书笔记与习题解答 — 15.5 最优二叉搜索树

笔记

　　二叉搜索树满足如下性质：假设x$x$是二叉搜索树中的一个结点。如果l$l$是x$x$的左子树的一个结点，那么l.key≤x.key$l.key\le x.key$。如果r$r$是x$x$的右子树的一个结点，那么r.key≥x.key$r.key\ge x.key$。
　　
　　也就是说，二叉搜索树中的任意一个结点，它的左子树中的所有结点都不大于它，它的右子树中的所有结点都不小于它。下图给出了一个二叉搜索树的例子。
　　
　　最优二叉搜索树(Optimal Binary Search Tree)问题描述如下。给定一个n$n$个不同关键字的已排序的序列K[1..n]=<k1,k2,…,kn>$K[\mathrm{1..}n]=<k_1,k_2,\dots ,k_n>$（因此k1<k2<…<kn$k_1<k_2<\dots <k_n$），我们希望用这些关键字构造一个二叉搜索树。对每个关键字ki$k_i$，都有一个概率pi$p_i$表示其搜索概率。搜索过程中有可能遇到不在K[1..n]$K[\mathrm{1..}n]$中的元素，因此我们还有n+1$n+1$个元素的“伪关键字”序列D[0..n]=<d0,d1,d2,…,dn>$D[\mathrm{0..}n]=<d_0,d_1,d_2,\dots ,d_n>$，表示搜索过程中可能遇到的所有不在K[1..n]$K[\mathrm{1..}n]$中的元素。d0$d_0$表示所有小于k1$k_1$的元素；dn$d_n$表示所有大于kn$k_n$的元素；对i=1,2,…,n−1$i=1,2,\dots ,n-1$，di$d_i$表示所有在ki$k_i$到ki+1$k_{i+1}$之间的元素。对每个伪关键字di$d_i$，也有一个概率qi$q_i$表示对应的搜索概率。在二叉搜索树中，伪关键字di$d_i$必然出现在叶结点上，关键字ki$k_i$必然出现在非叶结点上。每次搜索要么成功（找到某个关键字ki$k_i$），要么失败（找到某个伪关键字di$d_i$）。关键字和伪关键字的概率满足：
　　　　　　　　　　　　　　
　　假定一次搜索的代价等于访问的结点数，也就是此次搜索找到的结点在二叉搜索树中的深度再加1$1$。给定一棵二叉搜索树T$T$，我们可以确定进行一次搜索的期望代价。
　　　　　　　　
　　其中depthT$dept{h}_T$表示一个结点在二叉搜索树T$T$中的深度。
　　
　　对于一组给定的关键字和伪关键字，以及它们对应的概率，我们希望构造一棵期望搜索代价最小的二叉搜索树，这称之为最优二叉搜索树。现在我们用动态规划方法来求解最优二叉搜索树问题。

　　首先我们描述最优二叉搜索树问题的最优子结构：假设由关键字子序列K[i..j]=<ki,…,kj>$K[i..j]=<k_i,\dots ,k_j>$和伪关键字子序列D[i−1..j]=<di−1,…,dj>$D[i-\mathrm{1..}j]=<d_{i-1},\dots ,d_j>$构成的一棵最优二叉搜索树以kr(i≤r≤j)$k_r(i\le r\le j)$为根结点。那么它的左子树由子序列K[i..r−1]$K[i..r-1]$和D[i−1..r−1]$D[i-\mathrm{1..}r-1]$构成，这颗左子树显然也是一棵最优二叉搜索树。同样，它的右子树由子序列K[r+1..j]$K[r+\mathrm{1..}j]$和D[r..j]$D[r..j]$构成，这颗右子树显然也是一棵最优二叉搜索树。
　　
　　这里有一个值得注意的细节—空子树。如果包含子序列K[i..j]$K[i..j]$的最优二叉搜索树以ki$k_i$为根结点。根据最优子结构性质，它的左子树包含子序列K[i..i−1]$K[i..i-1]$，这个子序列不包含任何关键字。但请注意，左子树仍然包含一个伪关键字di−1$d_{i-1}$。同理，如果选择kj$k_j$为根结点，那么右子树也不包含任何关键字，而只包含一个伪关键字dj$d_j$。
　　
　　用e[i,j]$e[i,j]$表示包含关键字子序列K[i..j]=<ki,…,kj>$K[i..j]=<k_i,\dots ,k_j>$的最优二叉搜索树的期望搜索代价。我们最终希望计算出e[1,n]$e[1,n]$。
　　
　　对于j=i−1$j=i-1$的情况，由于子树只包含伪关键字di−1$d_{i-1}$，所以期望搜索代价为e[i,i−1]=qi−1$e[i,i-1]=q_{i-1}$。
　　
　　当j≥i$j\ge i$时，我们要遍历以ki,ki+1,…,kj$k_i,k_{i+1},\dots ,k_j$作为根结点的情况，然后从中选择期望搜索代价最小的情况作为子问题的最优解。假设选择kr(i≤r≤j)$k_r(i\le r\le j)$作为根结点，那么子序列K[i..r−1]$K[i..r-1]$构成的最优二叉搜索树作为左子树，左子树的期望搜索代价为e[i,r−1]$e[i,r-1]$；子序列K[r+1..j]$K[r+\mathrm{1..}j]$构成的最优二叉搜索树作为右子树，右子树的期望搜索代价为e[r+1,j]$e[r+1,j]$。
　　
　　当一棵子树链接到一个根结点上时，子树中所有结点的深度都增加了1$1$，那么这棵子树的期望搜索代价的增加值为它的所有结点的概率之和。对于一棵包含子序列K[i..j]$K[i..j]$的子树，所有结点的概率之和为
　　　　　　　　　　　　
　　接上文，若kr(i≤r≤j)$k_r(i\le r\le j)$作为包含关键字子序列K[i..j]$K[i..j]$的最优二叉搜索树的根结点，可以得到如下公式
　　　　　　　　e[i,j]=pr+(e[i,r−1]+w[i,r−1])+(e[r+1,j]+w[r+1,j])$e[i,j]=p_r+(e[i,r-1]+w[i,r-1])+(e[r+1,j]+w[r+1,j])$

　　由于w[i,j]=w[i,r−1]+pr+w[r+1,j]$w[i,j]=w[i,r-1]+p_r+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]$

　　我们要遍历以ki,ki+1,…,kj$k_i,k_{i+1},\dots ,k_j$作为根结点的情况，并选择期望搜索代价最小的情况作为子问题的最优解。于是我们可以得到下面的递归式。
　　　　　　　　
　　e[i,j]$e[i,j]$给出了最优二叉搜索树子问题的期望搜索代价。我们还需要记录最优二叉搜索树子问题的根结点，用root[i,j]$root[i,j]$来记录。
　　
　　根据上文给出的递归式，我们可以采用自下而上的动态规划方法来求解最优二叉搜索树问题。下面给出了伪代码。
　　
　　我们可以看到，该问题的求解过程与15.2节矩阵链乘法问题是很相似的。该算法的时间复杂度也与矩阵链乘法问题一样，都为Θ(n3)$\Theta (n^3)$。

习题

15.5-1 设计伪代码CONSTRUCT-OPTIMAL-BST(root)$\text{CONSTRUCT-OPTIMAL-BST(root)}$，输入为表root$root$，输出是最优二叉搜索树的结构。例如，对图15-10中的root$root$表，应输出
　　k2$k_2$为根
　　k1$k_1$为k2$k_2$的左孩子
　　d0$d_0$为k1$k_1$的左孩子
　　d1$d_1$为k1$k_1$的右孩子
　　k5$k_5$为k2$k_2$的右孩子
　　k4$k_4$为k5$k_5$的左孩子
　　k3$k_3$为k4$k_4$的左孩子
　　d2$d_2$为k3$k_3$的左孩子
　　d3$d_3$为k3$k_3$的右孩子
　　d4$d_4$为k4$k_4$的右孩子
　　d5$d_5$为k5$k_5$的右孩子
　　与图15-9(b)中的最优二叉搜索树对应。
　　解
　　
15.5-2 若7$7$个关键字的概率如下所示，求其最优二叉搜索树的结构和代价。

　　解
　　最优二叉搜索树如下所示。期望搜索代价为3.12。
　　
　　
　　
　　
15.5-3 假设OPTIMAL-BST$\text{OPTIMAL-BST}$不维护表w[i,j]$w[i,j]$，而是在第9行利用公式(15.12)直接计算w[i,j]$w[i,j]$，然后在第11行使用此值。如此改动会对渐近时间复杂性有何影响？
　　解
　　在每次迭代中，直接利用公式(15.12)计算w[i,j]$w[i,j]$需要的时间为O(n)$O(n)$。然而，w[i,j]$w[i,j]$的计算并不是在最后一层迭代中，并且计算w[i,j]$w[i,j]$的渐近时间与最后一层迭代的渐近时间是相同的。所以此改动并不改变OPTIMAL-BST$\text{OPTIMAL-BST}$的渐近时间。
　　
15.5-4 Knuth[212]已经证明，对所有1≤i<j≤n$1\le i<j\le n$，存在最优二叉搜索树，其根满足root[i,j−1]≤root[i,j]≤root[i+1,j]$root[i,j-1]\le root[i,j]\le root[i+1,j]$。利用这一特性修改算法OPTIMAL-BST$\text{OPTIMAL-BST}$，使得运行时间减少为Θ(n2)$\Theta (n^2)$。
　　解
　　在代码一中，在处理每个子问题[i,j]$[i,j]$时，从i$i$到j$j$进行迭代（代码一第9行）。根据题目所给的结论，在处理每个子问题[i,j]$[i,j]$时，可以改为从root[i,j−1]$root[i,j-1]$到root[i+1,j]$root[i+1,j]$进行迭代。下面给出了伪代码。
　　
　　现在分析OPTIMAL-BST-KNUTH$\text{OPTIMAL-BST-KNUTH}$的运行时间。
　　先考虑子问题规模l>1$l>1$的情况。规模为l$l$的子问题一共有n−l+1$n-l+1$个（参见代码三第6行）。每个规模为l$l$的子问题包含(root[i+1,j]−root[i,j−1]+1)$(root[i+1,j]-root[i,j-1]+1)$次迭代（其中j=i+l−1$j=i+l-1$），故求解所有规模为l$l$的子问题所需的迭代次数为
　　　　　　　　
　　故求解所有规模为l(l>1)$l(l>1)$的问题的迭代次数为Θ(n)$\Theta (n)$。而每次迭代时间为Θ(1)$\Theta (1)$，故求解所有规模为l$l$的子问题的时间为Θ(n)$\Theta (n)$。
　　而规模为l=1$l=1$的子问题一共有n$n$个，每个子问题需要Θ(1)$\Theta (1)$。故求解所有规模为l=1$l=1$的子问题需要Θ(n)$\Theta (n)$时间。
　　子问题的规模l$l$的取值有n$n$种情况，故OPTIMAL-BST-KNUTH$\text{OPTIMAL-BST-KNUTH}$的运行时间为Θ(n2)$\Theta (n^2)$。

　　本节相关的code链接。
　　https://github.com/yangtzhou2012/Introduction_to_Algorithms_3rd/tree/master/Chapter15/Section_15.5