算法导论之动态规划：最优二叉搜索树

àì夳堔傛蜴生んèń 2022-07-24 06:21 168阅读 0赞

**最优二叉搜索树**：给定一个n个不同关键字的已排序的序列K=<k1,k2……,kn>(k1<k2<k3……<kn)，用这些关键字构建一颗二叉搜索树。对于每个关键字ki，都有一个概率pi表示其搜索频率。

有些要搜索的值可能不在K中，因此我们还有n+1个“伪关键字”d0,d1……dn表示不在K中的值。d0表示所有小于k1的值，dn表示所有大于kn的值，对已i=1,2……,n-1，伪关键字di表示所有在ki和k(i+1)之间的值。同样对于每个伪关键字di也有一个概率qi表示对应的搜索频率。

关键字和伪关键字的概率和为1，即∑pi+∑qj=1     (1<=i<=n,0<=j<=n)

最优二叉搜索树的期望搜索代价是：

E\[T中搜索代价\]=∑(depth(ki)+1)\*pi + ∑(depth(dj)+1)\*qj=1+∑depth(ki)\*pi + ∑depth(dj)\*qj                          (1<=i<=n,0<=j<=n)

我们也可推算得到一颗期望搜索代价最小的二叉搜索树的**递归公式**为：

e\[i\]\[j\]=q(i-1)                                                     若j=i-1

e\[i\]\[j\]=min\{e\[i\]\[r-1\]+e\[r+1\]\[j\]+w\[i\]\[j\]\}              若i<=j

其中w\[i\]\[j\]=∑pl+∑qk=1     (i<=l<=j,i-1<=k<=j)

**实现代码**如下：

#include <stdio.h>
    #include <limits.h>
    
    float OPTIMAL_BST(float *p,float *q,int n,float e[][n+1],float w[][n+1],int root[][n+1]){
    	int i=1;
    	for(;i<=n+1;i++){
    		e[i][i-1]=q[i-1];
    		w[i][i-1]=q[i-1];
    	}
    	int l=1;
    	for(;l<=n;l++){
    		for(i=1;i<=n-l+1;i++){
    			int j =i+l-1;
    			e[i][j]=INT_MAX;
    			w[i][j]=w[i][j-1]+p[j]+q[j];
    			int r=i;
    			for(;r<=j;r++){
    				float t = e[i][r-1]+e[r+1][j]+w[i][j];
    				if(t<e[i][j]){
    					e[i][j]=t;
    					root[i][j]=r;
    				}
    			}
    		}
    	}
    	return e[1][n];
    }
    
    int main(int argc, char *argv[])
    {
    	float p[]={
    		0,0.15,0.10,0.05,0.10,0.20
    	};
    	float q[]={
    		0.05,0.10,0.05,0.05,0.05,0.10
    	};
    	int n = sizeof(q)/sizeof(int)-1;
    	float e[n+2][n+1],w[n+2][n+1];
    	int root[n+1][n+1];
    	float expect = OPTIMAL_BST(p,q,n,e,w,root);
    	printf("%0.2f\n",expect);
    	printf("the follow is e[][]:\n");
    	int i = 1;
    	for(;i<n+2;i++){
    		int j=i-1;
    		int k=0;
    		for(;k<j;k++)
    			printf("\t");
    		for(;j<n+1;j++)
    			printf("%0.2f\t",e[i][j]);
    		printf("\n");
    	}
    	
    	printf("the follow is w[][]:\n");
    	for(i=1;i<n+2;i++){
    		int j=i-1;
    		int k=0;
    		for(;k<j;k++)
    			printf("\t");
    		for(;j<n+1;j++)
    			printf("%0.2f\t",w[i][j]);
    		printf("\n");
    	}
    	
    	printf("the follow is root[][]:\n");
    	for(i=1;i<n+2;i++){
    		int j=i;
    		int k=0;
    		for(;k<j;k++)
    			printf("\t");
    		for(;j<n+1;j++)
    			printf("%d\t",root[i][j]);
    		printf("\n");
    	}
    	return 0;
    }

上面算法的时间复杂度是Ω(n^3)。

为什么最优二叉搜索树不一定是高度最矮的，而且概率高的关键字也不一定出现在二叉搜索树的根节点那？

因为在二叉搜索树中存在一些伪关键字，而这些伪关键字只能排列在叶子节点处，所以对关键字的分布就造成了影响。

如果没有伪关键字，那么肯定是概率高的关键字在根节点，这时候就是哈夫曼树又称最优二叉树。

**参考资料**：  
算法导论  
  
**备注**：  
转载请注明出处：http://blog.csdn.net/wsyw126/article/details/51422644  
作者：WSYW126