佳査找树的算法及实现方法一般原理（动态规划）一棵树如果是最优二叉搜索树，那么要么它是空树，要么它的左、右子树也是最优二叉搜索树，但分治法计算了很多重复的子树情况，一些子树的查找代价被计算了很多遍，因此只需要将子树的查找代价记录卞来，采用自底向上的动态规划的方法，虽然需要消耗一定的空间，但可以把时间复杂度从指数级降到多项式级1. 描述问题最优二叉查找树（OptimalBST,OptimalBinarySearchTree）最优二叉查找树是使查找各节点平均代价最低的二叉查找树具体来说就是:给定键值序列K=,kx,概率序列P=输出：两个二维数组，Pnce[i]『]表示圧到匕构成的最优子树的查找代价，Rootfi][j]^示表示k,到lq构成的最优子树的根节点位置（用于重构最优二叉查找树）For（子树大小size=1ton）{For（子树的起点start=1to（n-size+1））//这样子树的终点即为end=start+size-1,长度为size{For（该子树的所冇节点作为根节点root=Root[stait][end-1]toRoot[start+1][end]）{对于每个root,根据之前计算过的Price数组得到左右最优子树的代价，可直接得到该子树的代价price为：左右子树的最优子树代价之和+所有节点的访问概率之和（因为所有节点都下降了一层）在内层循坏中找到代价最小的pnce和root分别记录在Price[stait][end]和Root[stait][end]中}}}考察的子树是与考察的内层循环中root数量一一对应的，而当start递进时，前一个root的终点正好等于后一个root的起点（算法中的红色部分），也就是说对于固定的size来说，考察的root的范闱加起来应当首尾相接而且至多刚好覆盖所有节点，因此对于每个size,最多只考察2n个root（这里缩放了一下），因此总共最多考察了2n・n=2n2个子树；另一方面，Root数组中每一个值对应得到的一个最优二叉查找树，也即至少需要考察n2个子树。
因此根据定义得到T(n)=O(n2)3・算法实现〃完整改进版#include#include#include#defineN4///〃/////////////////////〃////////////////////voidOBST(mtP[],mtQ[],mtR[][N+1],intn){〃采用动态规划法构造最佳二分树//P[]查找成功概率：Q[]查找失败概率；R[][N+1]保存各个根结点，11内点个数intW[N+1][N+1];/AV[i,j]=sum(i,j,q)+sum(i+1,j,p);mtC[N+1][N+1];//最优路径值fbr(inti=0;i<=N;i++){//将初值全部置为for(intj=0;j<=N;j++){w[i]U]=c[i]Ul=R[ilU]=o；}}fbr(i=O;i<=n-l;i++){//初始化过程W[i][i]=Q[i];〃空的R[i][i]=0;//C[i][i]=0;//W[i][i+1]=Q[i]+Q[i+1]+P[i+1]；//含一个节点的最优树R[i][i+l]=i+l;C[i][i+l]=Q[i]+Q[i+l]+F[i+l];}W[n][n]=Q[n]；R[n][n]=0;C[n][n]=0;fbr(intm=2;m<=n;m++){//找有in个结点的最优树，m从个开始，直到n个(也就是说最佳二分树构造成了)for(inti=0;i<=n-m;i++)〃i是本次需要计算的含m个内节点的树个数{intj=i+m;//j是含m个内节点的树的最后一个叶子节点下标W[i][j]=W[i][j-l]+P[j]+Q|j]y/i是含m个内节点的树的第一个叶子节点的卞标mtk=i+l;//k是本次计算的第一个内点的下标值，以下标是k的内节点为根的最佳二分树的权值和最小，找使得C[i][k-1]+C[k][j]最小的人且i
动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要人于其它的算法选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间所以，能够用动态规划解决的问题还有一个显著特征：子问题的重叠性这个性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就不具备优势。
