相关概念
二叉树：
二叉树是每个节点最多有两个子树的树结构。每个节点有一个左子节点(Left children)和右子节点(Right children)。左子节点是左子树的根节点，右子节点是右子树的根节点。如图（a）所示。
二叉搜索树：
二叉搜索树 （Binary Search Tree)：每个节点都不比它左子树的任意元素小，而且不比它的右子树的任意元素大。如图（b）所示。
（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）它的左、右子树也分别为二叉搜索树 。
建立最优二叉搜索树
问题引入：
1、设S={x1, x2, ..., xn}是一个有序集，且x1<x2<...<xn。例如S={3，12，24，37，45，53，61，78，90，100}。表示有序集S的二叉搜索树利用二叉树的结点来存储有序集中的元素。
2、二叉搜索树的叶结点是形如(xi，xi+1)的开区间。
3、在表示S的二叉搜索树中搜索一个元素x，返回的结果有两种情形：
（1）在二叉搜索树的内结点中找到x=xi。
（2）在二叉搜索树的叶结点中确定x∈(xi，xi+1)，约定x0=-∞，xn+1=+∞。
4、在表示S的二叉搜索树T中，设存储元素xi的结点层次为ci；存储叶结点(xi，xi+1)的结点层次为dj，则P表示在二叉搜索树T中作一次搜索所需要的平均比较次数。P又称为二叉搜索树T的平均路长。
问题解决
一、最优子结构性质：
1.二叉搜索树T的一棵含有结点xi, ..., xj和叶结点(xi-1, xi),...,(xj, xj+1)的子树可以看作是有序集{xi ,..., xj}关于全集合{xi-1 ,..., xj+1}的一棵二叉搜索树。
2.设Tij是有序集合{xi, ..., xj}关于存取概率的一棵最优二叉搜索树，其路长为pij。Tij的根结点存储元素xm，其左右子树Tl和Tr的路长分别为pl和pr。由于Tl和Tr中结点深度是他们在Tij中的结点深度减1，故我们有:
3.证明：由于Tl是关于集合{xi,...xm-1}的一棵二叉搜索树，故pl ≥ pi,m-1。若pl>pi,m-1，则用Ti,m-1替换Tl可得到平均路长比Tij更小的二叉搜索树。这与Tij是最优二叉搜索树矛盾。故Tl是一个最优二叉搜索树。同理可证Tr也是一棵最优二叉搜索树。因此最优二叉搜索树具有最优子结构性质。
二、递归计算最优值
1.最优二叉搜索树Tij的路长为Pij，由最优二叉搜索树问题的最优子结构性质可建立计算Pij的递归式如下：
记wi,jpi,j为m(i,j)，计算m(i,j)的递归式为:
代码块
京公网安备 11010502036488号