上一讲我们介绍了最优二叉检索树的概念，这棵树是怎么构成的？ 这是我们这一讲需要解决的问题。那就是说，你用什么样的算法 来构造一棵最优的二叉检索树。这里边的关键问题是下面一些问题。一个是 动态规划的算法，你必须先要界定子问题，我们用什么样的参数来界定子问题。 第二个要考虑的就是 它利用的是子问题之间的依赖关系， 你怎么把当前要解的问题归结成更小的子问题， 这个归结的方法是什么。 当有了这个归结方法以后，要写出它关于优化函数的递推 方程和初值，这个递推方程就是比较大的问题的优化函数值，它是 怎么样依赖于那个更小的子问题的优化函数值。 初值呢意味着是最小的子问题它的优化函数值是什么， 然后你要考虑计算顺序，就是子问题是按照什么样的顺序从小到大 迭代地来计算。为了求得问题的解，是不是需要做标记， 那标记函数是怎么设计的，最后就是时间复杂度的分析。 下面我们就针对这样的一些要点来考虑一下 最优二叉检索树对这些问题到底是怎么考虑的。 首先看这个子问题的划分， 子问题的划分呢，需要有两个参数来界定它的边界，i和j， 也就是说，我们现在考虑的是数据集里边的xi到 xj这一段数据它所构造的一棵最优二叉 检索树，当然这棵树它是整个问题解的 这个二叉检索树里边的一个子树，这是它的子问题的边界。 那么原始问题呢，相当于i等于1，j等于n，就是那n个x的所构成的输入。 这是数据集，我们用xi xj来表示。那么针对这个子的数据集， 它有一个子的概率分布，是从原来原始的概率分布中截取了中间的一段， 是哪一段呢？正好是从i到j这一段数据集 相关的概率。那么这里边包含着Xi个 就是数据节点的概率，i+1的，Xi+1的数据节点的 概率，一直到Xj的数据节点的概率。还有 每个数据节点两边的空隙节点的，空隙的这些个概率，所以这是 针对这个子问题的概率分布。那么子问题的 划分呢就由这两个量来决定了，一个是它的数据 是哪些个，它针对的概率分布是哪一部分，这是子问题的 它的输入。下边我们看一个实例， 假定这是一个输入实例，有5个字符A，B ，C ，D， E， 下面是它的概率分布，那么这个红颜色的5个量 代表的是A，B ，C ，D， E的概率，然后这些个黑的这些个数据代表的是一共 有6个空隙，这6个空隙的概率，这个是输入的实例。下边我们截取它的一个子问题， 比如说我选取的是B， C ，D，选取这段数据，考虑它构成的 一棵二叉检索树，最优的这样的树的结构，那么它所对应的这个输入 也要做改变，就是我们输入的数据集就变成B， C ，D 这三个的子数据集了。然后针对这些个子数据集 它的概率分布，这是0.3，0.1，0.2，是B ，C， D的概率， 然后加上它们周边的这个空隙的概率，也就是这一段 概率分布是针对这个子数据的概率分布。因此呢， 我们可以看到子问题S[2，4]，就是第2到第4 它的数组是B， C ，D，然后它所针对的概率分布 P[2，4]，从2到4的概率分布就是这个标蓝的 这一段的概率分布。这就是我们怎么做子问题的划分，当划分了子问题以后所得到 子问题的输入是什么，就可以这样表示出来。下面我们考虑怎么样做归约， 就怎么把原始问题来归约成子问题。这归约的方法就是选定一个节点作为 根，比如说我们选定第k个x，Xk作为树根，它作为树根以后，那么 在Xk比它小的那些个排在它前边的那些个 数据就作为子问题的它的树的那些个数据， 而比Xk大的，就是从Xk+1到Xj的那部分数据，就作为 右边这个子问题的数据，所以我们出现两个子问题，一个是从i到k-1, 就是在Xk左部的那些个数据和它相应的概率分布。 另外还有一个右边的子问题，从k+1到j的这一部分 数据和它对应的概率分布。那么我们看到刚才这个例子， 这是 A， B， C ，D， E，假定我们拿B这个元素作为树根， 那么它左边的数据实际上是A，右边的数据是C，B，D的数据，这样就 形成了两个子问题，这是原始的输入，它是从1到5，这个 数据集是1到5，它的概率分布也是1到5这个范围。 那下边就会产生这两个子问题，是什么样的输入呢？左边 这只有一个数据元素就是[1，1]，它只有一个A，而左边的概率分布实际上 就是，就是这一段，就是A的概率加上它两边空隙的概率，就是这一段。 那么右边这个子问题呢，就是在B右边的这个数组，它是C ，D， E，所以这个是它的 数据，然后下边这个是它对应的这个数据的概率分布。这样我们 就由原始问题通过选定了一个根的元素，比如说我们选定了B， 就会产生两个子问题的它的描述，包括它的数据和概率 分布，这是右边这个子问题的数据和概率分布。 下边我们就来介绍一个概念，叫子问题的 概率之和，那么有了这个概念以后， 我们就可以列有关刚才那个归约方法， 把原始问题归约成子问题以后它的优化函数值的递推方程了。 那么这个概率之和是什么意思呢？我们假定这个子问题是从i到j 这样标记的子问题，这是它对应的概率分布，我们把在这个子问题 相关的所有的概率都把它加起来，那这一项呢是从 它的a i-1到a j， 这个是它的空隙的所有概率之和。而这一项呢，代表的 是它的所有数据节点的概率之和，刚好从bi一直加到bj。 因此这一项w[i，j]反映的是 和这个子问题相关的这个概率项里边的 所有的这些概率都加起来的总和，就是w[i，j]。 下边我们看一个例子，比如说刚才那个实例， 我们现在取的这个问题是2到4这一段，就是B， C， D，这个是它对应的 概率分布，2到4这一段的概率分布，那么这个公式它是所有的概率之和， 我们先把这些数据节点0.3， 0.1， 0.2全部加起来，就是上面这个项。 然后下边呢是所有的它的空隙节点的和，这些个 项都加起来，就是下边这个和。那么这两个加到一起呢，是0.75。 这个反映的是所有的 在这个子问题中的它的包括它的数据节点和空隙节点在整个 问题所占有的成分大概占到0.75的这样的概率。这是关于这个子问题 概率之和的概念。下面我们看一下 优化函数的递推方程，m[i，j]呢是相对于 这样的输入，S[i，j]和概率分布P[i ，j]的 一个最优的二叉搜索树的平均的比较次数，我们列的就是它的 递推方程。下面我们看到假定以第k个 元素作为根，比如说Xk作为根，这样的话就可以把原问题归结成两个子问题， 左边是从i到k-1的这一部分数据 和它相应的概率分布构成的子问题。右边呢是 从Xk+1到Xj这一部分数据跟它相应的 概率分布构成的子问题。假定是我们选了Xk作为根以后， 那这个递推方程应该怎么写呢？它是这样的形式，左边这个子问题的一个 比较次数最优的比较次数，右边这个子问题的一个最优的比较次数就是它的 平均比较次数的最优值，然后加上 从i到j的这所有的概率的综合，就是这个递推方程 的含义。那么为什么要加上这一项呢，因为大家知道 我们计算的平均比较次数相当于是把这个地方作为 根结点向下检索的它这棵子树的平均的比较次数。 那么这一项呢是把右边这个，这是一棵树的结构，把这个地方作为根结点， 向下检索的平均的比较次数，当用xk把这两棵子树 合并成一个更大的树，那这个时候，这里边数据的结点，每个的深度都会增加1。 它的空隙结点的深度也增加1，而这里边的原有的数据结点和空隙结点 它的深度也会增加1，因为我们的检索要从这个结点开始向下检索， 这块多了一次比较。那么当它的深度增加1以后，大家的平均工作量 都会增加1，那对整个的，就是整个这棵树，因为从xk，它还可能以 它为根，作为更大的树的子结构，因此我们对整个最终的那棵树构成以后， 它从，由于这两个层数增加了，对整个这棵树的平均比较次数的影响 就体现在它的概率上，就是这棵树 它在整棵树中的概率是多少，因为每个都增加一次 再乘以它的概率值就是它的工作量的影响。 这是我们这个公式，下面我们看一下这个公式的证明。 这个公式的证明它是这样子，以这个xk作为根， 它的计算的它平均比较次数的最小值。 我们是在xk为根的情况下来计算的，那这就是它的 左边的这一项的它的工作量，这个是左边这棵子树的工作量 加上它的概率，因为每一个 结点都增加了1的深度，所以大家都增加一次乘以这棵树的 出现的这个概率，就是对整个的影响。然后这一项是右边这棵子树的 它的平均，原来的平均比较次数，然后 由于它作为右儿子附上去以后，每个结点增加一次比较。 所以要乘以它的概率，一一乘以这个概率就是它对整个平均次数的影响。 然后这一项代表这是根结点，原来没有这个xk这个元素，现在有了以后， 那如果正好第一次要跟它比较， 那这个结点出现的概率是bk再乘以一次的比较次数，就是x恰好 检索的就是这个根结点，它需要的工作量体现在这一项上。 所以这个就是作为子树所增加的次数呢 是体现在这两项的影响另外加上根结点的影响。 好，下边把这个东西进行整理，我们把含有m的这些个项 都写在前面，这是第一个项，这是有关m的第二个项， 写在这儿，把跟概率有关的这个项、这个项、这个项 写在右边，这样整理，整理完了以后把右边的这一部分 按照定义把它写出来。 那就是说这一项它应该是 所有的概率的和，就是左边这棵子树的概率的和。 包括它的空隙结点和它的数据结点的，两项的 概率和就是这一项。那么bk 写在这儿，然后把右边这个，就是右边这棵子树的 所有的概率之和，我们也把它写在这儿，那么这项是 空隙结点的，这项是数据结点的，所以这个就是代入我们的概率公式得到的这个结果。 然后把这两项我们继续来化简，就是把所有a的项都写到一起，写到这儿。 这个ap刚好p从i减1，就是a i减1一直加到a k减1，而这一项呢刚好从ak 加到aj，所以把这两个合到一起呢，正好是 从a i减1加到aj，就是这个公式。 它正好是把这两项合到一起，把这个b的一项、两项、三项，把这三项 含有b的合到一起，化简就成这个样子，所以这个就是化简的最终结果。那就是所有的 空隙结点的加上所有数据结点的概率之和，那这两个概率之和正好就是w [i, j]，这就得到了最终这个公式。那这个公式呢正好就是我们刚才 递推方程里的那个公式，就是这样证明出来了。下面我们看一下 刚才得到的就是，你把第k个结点作为根的话，它所得到的，m[i,j] 按照这个公式来计算，那你整个的数最好的是哪一个呢？你可能以x1为根， 也可能以x2为根，也可能以 后面的别的x为根，那当我们考虑子问题的时候，i到j这个子问题的时候， 它的为根的范围就从xi一直到xj，在这个范围里头，那就是k的取值 可能取这里边的任何一个数，我们要对所有的k都要尝试一下，看看以哪个为根更好， 找出其中比较次数最少的那个，那才是这个子问题 的最优二叉检索树的结构，所以这是它的结果。 那么写成递推方程的话，那就是说，这个k在这个地方取最小， 要考虑到所有可能为根的情况，找到它的最小的值。 另外我们看一下这个初值，刚才那个递推方程 的初值，初值是m[i,i减1]等于0。 那么这个反映的是什么呢，反映的是正好是 取边上的这个结点为根，比如说我取A为根， 或者取E为根的情况。假定我们取A为根， 这个时候k等于1，k等于的时候，考虑刚才这个方程， k等于1，这个i是1，k也等于1，那就是1和0。 所以刚好就满足我们这个[i, i减1]，i等于1嘛，[1,0]， 正好是这个情况，也就是S[1,0]的情况，那么这个时候m[1,0]呢？ 因为我以这个A要为根的话，它左边根本没有数据结点。 所以左子树是个空子树，这个时候它的比较次数当然是零。所以 初值呢对应的就是这样的情况，另外一个初值的情况呢，就是如果我以E为根， 以最右边这个结点为根，所有的数据结点都落入到 左子树，这个时候右子树是空的，这个时候它得到的 也是一个这样的表示，就是m[i,i减1]的表示，正好是 最右边的这一项的情况，那就是说 刚才我们讲到的它是属于这种极端情况，就是或者左子树为空，或者 右子树为空，这个图就表示的是左子树为空的这种结构。 下面我们看一个具体的计算实例，这个实例呢，它的 概率分布我们都列到这个树上了，这是数据结点， A、B、C、D、E这五个结点的，数据结点的概率分布，那么这些个黑的 这些个数字都是它的空隙结点的概率分布。 那现在我们就来看一看，如果要以B为根 来考虑的时候，那这个时候它左边的数据结点只有A，右边的是C、 D、E，在这个情况下，那左边是m[1,1]，这个时候是0.16， 0.16怎么算的呢？就是因为它的左子树也是空的，它的右子树也是空的，相当于这一项- 、这一项 都是零，只有概率之和加起来就是值了，那概率之和是0.1加0.04加0.02， 所以这个值计算出来是0.16。那么右边这个怎么计算呢？我们也要从 小到大，一层层计算，我们需要计算的是m [3,5]，m[3,5]怎么算呢？先算这个， 这个算出来跟这个计算方法一样，0.1 加0.02加0.05，这是0.17，而右边这棵树这个结构跟左边 这个结构一样，同样的计算方法，0.1加0.06加0.01，也是0.17。 那就是说，我们当以D为根的时候，左边这棵子树就是第一项的值， 是0.17，右边这棵子树是第二项的值，也是0.17， 那么0.17加0.17再加上所有概率的和，所有概率的和就是这个0.2、 0.1、0.1加上这四项，这个概率的和 再加起来，加上刚才那两个0.17，最后算出来就是0.88。 所以右边这棵子树的值是0.88。 那当我们以B为根的时候，意味着左边这棵子树的值已经算出来了，0.16。 而右边这棵这棵子树的值它也算出来了，这个优化函数值是0.88。 在这个情况下我们如果以B为根，这个值应该怎么计算呢？ 我们就可以带入公式，那就是m[1,1]带到前一项，然后m[3,5]带到后一项。 这样带进来。带进来以后呢，那它就是0.16, 这个是0.88，然后加上所有的概率的和，就是把这些个 概率和全部加起来，这样得到的就是这个公式。那就是说， 这个是m[1,1]加上m[3,5]就是这两个值带入， 然后再加上它的所有的概率的和。因为这就是原始问题了， 所有的概率加起来恰好等于1；所以加上这个1就是所有的概率的和。这个计算出来是2- .04。 大家可以对照一下我们一开始的计算方法是按照定律来计算的。 就是把每个结点的深度，如果是空隙结点的话就是深度值， 要是数据结点像这种原结点的话，深度加1。深度加1代表它的工作量。 工作量乘以它的概率，每个结点的对应的工作量，和每个空隙的工作量乘以它的概率 然后按照那个定义计算出的平均的比较次数也是2.04。和我们按照这棵树， 按照这个递推方程计算的平均比较次数是完全一样的。下面我们看一下复杂性的估计。 这个是刚才讲的这个递推方程， 那么根据这个递推方程我们可以估计出来，计算 每个项的工作量。这个组合的可能就是子问题的个数有 多少种呢？就是看i和j，那么i和j在1和n之中来选择的。 按照它的组合的可能性应该是n平方的量计。所以，我们第二个子问题有n平方个子问题。 那么对一个子问题的计算，比如说，i、j固定了以后 它要考虑我在i和j之间选哪个 元素作为根？这个根的，这个K 的位置代表根的位置。 它的取值是在i和j之间变取所有的可能性，所以当i和j 比较大的时候这个k的选择是O(n)的可能性。 那就意味着我为了计算一个m[i,j]，这边要进行O(n)的工作量。 那么一共多少个子问题呢？n平方个子问题，所以算法的工作量是n的立方。 这个空间复杂度正好是备忘录的大小。那就是说， 我有多少个不同的m[i,j]？是n平方个，这是它的空间复杂度。 下面把这个问题小结一下。 划分子问题它是根据什么来划分呢？是考虑以哪个数据结点做树根？ 按照它为根划分成左和右两个子问题。 那么子问题的边界就由前后i和j来界定这个边界。 下面就是定义优化函数，列出有关 优化函数的递推方程和它的边界条件，也就是初值。 它的计算是自底向上的计算，也就是说我们根据初始问题是只有一个数据 结点的最小的子问题，然后是两个数据结点的，就是连续两个挨着的数据结点的； 然后是三个挨着的数据结点的，把所有的这样的子问题 从小到大的自底向上的计算。它的备忘录是 存取这个优化函数的值，然后我们 我们看看要设立标记函数，标记函数就是说我在i到j这个子问题 它取得最少的比较次数的时候是以那个结点为根？就是那个xk的位置到底k等于几， 这个通过标记函数把这个k记下来，将来可以追踪这棵树的结构。 最后时间复杂度的估计，这个估计我们看到是n的立方的时间。好， 好，这是一个多项式时间的算法，关于这个二叉检索树问题呢我们就介绍到这里。
