4、问题具有最优子结构性质。证明:设Tij是有序集{xi,…,xj}关于存取概率分布(ai-1，bi，…，bj，aj)的一棵最优二叉搜索树，平均路长为pij。Tij的根结点存储元素xk。其左右子树Tl和Tr的平均路长分别为pl和pr。由于Tl是关于集合{xi，…，xk-1}的一个二叉搜索树，故pl≥pi,k-1。如果pl＞pi,k-1,那么用Ti,k-1替换Tl可得到平均路长比Tij更小的二叉搜索树。这与Tij是最优二叉搜索树相矛盾。所以，左子树Tl是一棵最优二叉搜索树，同理可证右子树Tr也是一棵最优二叉搜索树，即最优二叉搜索树的子树也是最优二叉搜索树。建立递归关系式若
5、最优二叉搜索树Ti,j的根结点为k,最小平均路长为pi,j,m[i,j]表示Ti,j的开销，则有m[i,j]=wi,jpi,j，其中，可建立下列递归关系：M[i,j]=bk+(m[i,k-1]+wi,k-1)+(m[k+1,j]+wk+1,j) 而wi,j=bk+wi,k-1+wk+1,j 则m[i,j]=wi,j+m[i,k-1]+m[k+1,j]（1） 将k=i+1，i+2，…,j分别代入<1>式，选取使m[i,j]达到最小的K，这样
6、递归关系式改为： m[i,j]=wi,j+min{m[i,k-1]+m[k+1,j]}m[i,i-1]=0，1≤i≤n 解递归关系，m[1,n]就是所求的最优值。将对应于m[i,j]的断开位置k记录在s[i,j]中（也称为根表，记录子树的根），以便构造最优解。根据记录的最优断开位置s[i,j],可以容易地构造出最优解。第5页共8页课程设计说明书(论文)用纸3算法设计寻找最优子结构。一个最优二叉树的子树必定包含连续范围的关键字ki~kj，1<=i<=j<=n，同时也必须含有连续的虚叶子节点di-1~dj。如果一棵最优二叉查找树T有一棵含有关键字ki~kj的子树T'
7、，那么，T'也是一棵最优查找树，这通过剪贴思想可以证明。现在开始构造最优子结构：在ki~kj中，选定一个r,i<=r<=j，使以kr为根，ki~k(r-1)和k(r+1)~kj为左右孩子的最优二叉树。注意r=i或者r=j的情况，表示左子树或右子树只有虚叶子节点。定义e[i,j]为一棵包含关键字ki~kj的最优二叉树的期望代价。当j=i-1时没有真实的关键在，只有虚叶子节点d(i-1)。于是：当j=i-1时，e[i,i-1]=q(i-1)。当j>=i时，需要选择合适的kr作为根节点，然后其余节点ki~K(r-1)和k(r+1)~kj构造左右孩子。这时要考虑左右孩子
