最优二叉搜索树 C#实现

最优二叉搜索树 C#实现

介绍一下

上一篇博文搞半天挺烧脑，没搞清楚继续… 主要是练习动态规划算法。最关键的一个是这个最优二叉搜索树能干啥。我认为如果数据稳定，统计出概率来，用最优二叉树保存，以后搜索应该是效率比较高的。还有一个是通过一通研究这个算法，折磨半天自己，加深理解，动态规划是真的难。
dp表项 一个是概率之和的理解，一个是dp状态转义表的理解。

概率之和递推公式

if (j < i)//看条件判定 没有任何数值的树概率就是间隙的概率
dp[i, j].weight = probs[2 * j];
else//递推 数值之前的概率 + 数值概率 + 数值和之后的间隙概率
dp[i, j].weight = dp[i, j - 1].weight + probs[2 * j - 1] + probs[2 * j];

状态转移递推公式

//赋值一个比较大的数字，可以知道，搜索长度最大不会超过数组长度
dp[h, l].path = datas.Count;
for (int k = h; k <= l; k++)
{
//通过getpath函数兼容索引后面小于前面的情况，节省空间。
float path = GetPath(h, k - 1, dp) + GetPath(k + 1, l, dp) + dp[h, l].weight;
if (dp[h, l].path > path)
{
//冒泡比较 记录最小搜索路长和树的根，以便于创建树
dp[h, l].path = path;
dp[h, l].root = k;
}
}

根据转移表递归创建搜索树

主要是CreateBSTNode函数
开始大于结束直接返回空，没有树结点
开始等于结束返回单一结点
开始小于结束，进入递归

程序数据和结果

List<int> lst =newList<int>{10,20,30,40,50,60};//间隙 数值 间隙 数值 ... 间隙List<float> fls =newList<float>{0.05f,0.05f,0.1f,0.1f,0.05f,0.05f,0.05f,0.1f,0.05f,0.2f,0.1f,0.01f,0.09f};//创建最优二叉搜索树，准备绘制
bTree = BSTree.CreateOPSTree(lst, fls);

程序核心代码

dp表项

publicstructItem{//概率之和[权重]publicfloat weight;//最短平均路长[状态转移表]publicfloat path;//根节点publicint root;}

构建搜索树代码

privatestaticfloatGetPath(int h,int l,Item[,] items){if(h > l){return0.0f;}else{return items[h, l].path;}}/// <summary>/// 根据dp转移表构建树/// </summary>/// <param name="h">开始</param>/// <param name="l">结束</param>/// <param name="dps">转移表</param>/// <param name="datas">树结点数据</param>/// <returns></returns>privatestaticBSTreeCreateBSTNode(int h,int l,Item[,] dps,List<int> datas){//开始大于结束if(h > l){returnnull;}//开始等于结束if(h == l){returnnewBSTree(datas[dps[h,l].root -1]);}else//开始小于结束 进入递归{BSTree bSTree =newBSTree(datas[dps[h, l].root -1]);
        bSTree.lChild =CreateBSTNode(h, dps[h,l].root-1,dps, datas);
        bSTree.rChild =CreateBSTNode(dps[h, l].root +1, l, dps, datas);return bSTree;}}publicstaticBSTreeCreateOPSTree(List<int> datas,List<float> probs){Item[,] dp =newItem[datas.Count +1, datas.Count +1];//赋值概率for(int i =1; i <= datas.Count; i++){for(int j = i -1; j <= datas.Count; j++){if(j < i)
                dp[i, j].weight = probs[2* j];else
                dp[i, j].weight = dp[i, j -1].weight + probs[2* j -1]+ probs[2* j];}}//赋值dp转移表for(int len =1; len <= datas.Count; len++){for(int h =1, l= len; h <= datas.Count && l<= datas.Count; h++, l++){
            dp[h, l].path = datas.Count;for(int k = h; k <= l; k++){float path =GetPath(h, k -1, dp)+GetPath(k +1, l, dp)+ dp[h, l].weight;if(dp[h, l].path > path){
                    dp[h, l].path = path;
                    dp[h, l].root = k;}}}}returnCreateBSTNode(1, datas.Count, dp,datas);}

参考

B站张老师视频
虽然写完了，如果不参考代码，其实只有思路，还是撸不出来的…