【算法导论】动态规划之最优二叉查找树

​ 如果我们想写一个单词查询的软件的话，我们的目的就是让查询的总时间最短，我们首先想到用之前的二叉查找树。我们可以用红黑树或者其它的平衡二叉树来保证每个单词的搜索时间。但是每个单词出现的频率一般不同，因此我们希望把频率较大的单词放在离根比较近的地方，频率较小的放在离叶子较近的地方。而且，我们所要查询的单词词库中没有，这也值得考虑。

​ 由上文可知，$k_i$表示单词，$d_i$表示不能查到的情况。由上面的例子可知，一棵最优二叉树不一定是高度最小的树。我们也不一定总把频率最大的放在根部。

​ 和矩阵链乘法一样，穷举所有的可能行肯定不是一个好的算法。由于具有动态规划的特征，毫无疑问，我们将使用动态规划法。

​ 对于原序列，我们假设第k个元素(采用遍历的方法)作为根时可以得到最优解，由于是二叉查询树，则前$k-1$个元素在左子树，剩余元素在右子树。接下来，我们要分别在左、右子树中找到最优二叉树，于是我们可以用相同的方法：假设左、右子树中第$m, n$个为根时，可以得到最优解，依此类推，就可以求得整体最优解。上面的解法中，可能存在左或者右子树为空的情况：

通过推导，可以递推公式：

其中$e$表示搜索的代价，$q[i]$为$d[i]$的出现频率，$w$为子树总的概率。

具体程序实现如下：

#include<stdio.h>
#define N 7
void Optimal_Bst(float *p,float *q,int n,float e[][N],int root[][N]);

void main()
{
	float p[]={0,0.15,0.1,0.05,0.1,0.2};//关键字出现的概率
	float q[]={0.05,0.1,0.05,0.05,0.05,0.1};//搜索不到关键字的几种情况的概率
	int n=6;//关键字个数
	float e[N][N]={0};//存储搜索的代价
	int root[N][N]={0};//子树的根，便于重构最优二叉树
	Optimal_Bst(p,q,n,e,root);
	for(int i=1;i<6;i++)
		for(int j=5;j>=i;j--)
			printf("从第%d个元素到第%d个元素的最优二叉查找树的顶点为：%d\n",i,j,root[i][j]);
}

void Optimal_Bst(float *p,float *q,int n,float e[][N],int root[][N])
{
	float w[N][N]={0};
	float t=0;
	for(int i=1;i<=n;i++)//左右子树为空的情况
	{
		e[i][i-1]=q[i-1];
		w[i][i-1]=q[i-1];
	}
	for(int l=1;l<=n;l++)
		for(int i=1;i<=n-l+1;i++)
		{
			int j=0;
			j=i+l-1;
			e[i][j]=10000;//初始化为很大的值，可以随意设置
			w[i][j]=w[i][j-1]+p[j]+q[j];//
			
			for(int r=i;r<=j;r++)//r代表以下标r为根，r在所有的子树节点中遍历
			{
				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;//得到最优二叉树时的根
					
				}
					
			}
		}
}

上述程序运行后，数组e,w,root的结果如下：

上述程序的运行时间为$O(n^3)$，这和前面的矩阵链乘法是一样的。