1、构建最优二叉 搜索树问题一些键的查询次数要比其它键的查询次数要频繁，还是如同平常一样来构造二叉搜索树吗？假设，键 K1 ， K2 ， ， Kn被查询的概率为 p1 , p2, ， pn （ 根据实际情况而定 ）ci 是 算法寻找 到 Ki ， 所作比较的次数。则二叉树 T中平均查找次数为：例 P466-468 ， 计算平均查找次数在 K1 ， K2 ， ， Kn 中，假设 Ki ，为根 结点，则 K1， ， Ki-1 必须在左子树中，而 Ki+1 ， ， Kn 在右子树中 但是我们不能确定选择哪一个作为根结点，才是最优的，所以必须在所有的选择中间求一个开销 A(T)最小的。像求矩阵相乘的最优序
2、一样，子问题可以用一个整数对 (low,high)来唯一描述。子问题 (low,high)表示一个检索开销最小的二叉搜索树。其存放的键值为： Klow ， ， Khigh ，相应的权重为 plow , ， phigh 改概率为权重，是由于 plow , ， phigh 的和 不一定为 1。定义 10.31、 A(low,high,r)是根为 Kr的子问题(low,high) 的最小带权开销。2、 A(low,high)是子问题 (low,high)， 在所有可供选择作为根的键值范围内，的最小带权开销。3、 p(low,high)= plow + + phigh为 搜索键值介于 Klow , Khigh之间的键时的概率，也称为该子问题的权重。结合图（ P469）， 不难理解1 、 A(low,high,r)= pr + p(low,r-1)+ A(low,r-1)+ p(r+1,high)+ A(r+1,high)= p(low,high)+ A(low,r-1) + A(r+1,high)2、 A(low,high)=minA(low,high,r)|lowrhigh不要重复递归调用的递归，其实现参见 P471。(n3)文本分行文本分行，分行时应尽量避免文本行占有不必要的额余空间。TEX ， 是由斯坦福大学的 Don Knuth和他的学生发明开发的。
