2、的路径上节点数目）最小，就需要建立一棵最优二叉查找树。图一显示了给定上面的概率分布pi、qi，生成的两个二叉查找树的例子。图二就是在这种情况下一棵最优二叉查找树。概率分布：i012345pi0.150.100.050.100.20qi0.050.100.050.050.050.10已知每个关键字以及虚拟键被搜索到的概率，可以计算出一个给定二叉查找树内一次搜索的期望代价。假设一次搜索的实际代价为检查的节点的个数，即所发现的节点的深度加1.计算一次搜索的期望代价等式为：建立一棵二叉查找树，如果是的上式最小，那么这棵二叉查找树就是最优二叉查找树。而且有下式成立：二、最优二叉查找树的最优子
3、结构最优子结构：如果一棵最优二叉查找树T有一棵包含关键字ki,..,kj的子树T'，那么这可子树T'对于关键字Ki,...,kj和虚拟键di-1,...dj的子问题也必定是最优的。可以应用剪贴法证明。根据最优子结构，寻找最优解：给定关键字ki,...,kj，假设kr(i<=r<=j)是包含这些键的一棵最优子树的根。其左子树包含关键字ki,...,kr-1和虚拟键di-1,...,dr-1，右子树包含关键字kr+1,...,kj和虚拟键dr,...dj。我们检查所有的候选根kr,就保证可以找到一棵最优二叉查找树。递归解：定义e[i,j]为包含关键字ki,...,kj的最优二叉查找树的
4、期望代价，最终要计算的是e[1,n]。当j=i-1时，此时子树中只有虚拟键，期望搜索代价为e[i,i-1]=qi-1.当j>=i时，需要从ki,...,kj中选择一个根kr，然后分别构造其左子树和右子树。下面需要计算以kr为根的树的期望搜索代价。然后选择导致最小期望搜索代价的kr做根。现在需要考虑的是，当一棵树成为一个节点的子树时，期望搜索代价怎么变化？子树中每个节点深度都增加1.期望搜索代价增加量为子树中所有概率的总和。对一棵关键字ki,...,kj的子树，定义其概率总和为：因此，以kr为根的子树的期望搜索代价为：而因此e[i,j]可以进一步写为：这样推导出最终的递归公式为：三、
5、代码实现（C++）：[cpp] viewplaincopyprint?1.//最优二叉查找树 2. 3.#include 4. 5.using namespace std; 6. 7.const int MaxVal = 9999; 8. 9.const int n = 5; 10.//搜索到根节点和虚拟键的概率 11.double p[n + 1] = {-1,0.15,0.1,0.05,0.1,0.2}; 12.double q[n + 1] = {0.05,0.1,0.05,0.05,0.05,0.1}; 13. 14.int
6、root[n + 1][n + 1];//记录根节点 15.double w[n + 2][n + 2];//子树概率总和 16.double e[n + 2][n + 2];//子树期望代价 17. 18.void optimalBST(double *p,double *q,int n) 19.{ 20. //初始化只包括虚拟键的子树 21. for (int i = 1;i <= n + 1;++i) 22. { 23. w[i][i - 1] = q[i - 1]; 24. e[i][i - 1] = q[i
7、 - 1]; 25. } 26. 27. //由下到上，由左到右逐步计算 28. for (int len = 1;len <= n;++len) 29. { 30. for (int i = 1;i <= n - len + 1;++i) 1. { 2. int j = i + len - 1; 3. e[i][j] = MaxVal; 4.
