最优二叉搜索树 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 = new List<int> { 10, 20, 30, 40, 50, 60 };
//间隙 数值 间隙 数值 ... 间隙
List<float> fls = new List<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);
文章来源:https://www.toymoban.com/news/detail-835326.html
程序核心代码
dp表项
public struct Item
{
//概率之和[权重]
public float weight;
//最短平均路长[状态转移表]
public float path;
//根节点
public int root;
}
构建搜索树代码
private static float GetPath(int h, int l, Item[,] items)
{
if (h > l)
{
return 0.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>
private static BSTree CreateBSTNode(int h, int l, Item[,] dps, List<int> datas)
{
//开始大于结束
if (h > l)
{
return null;
}
//开始等于结束
if (h == l)
{
return new BSTree(datas[dps[h,l].root - 1]);
}
else//开始小于结束 进入递归
{
BSTree bSTree = new BSTree(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;
}
}
public static BSTree CreateOPSTree(List<int> datas, List<float> probs)
{
Item[,] dp = new Item[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;
}
}
}
}
return CreateBSTNode(1, datas.Count, dp,datas);
}
参考
B站张老师视频
虽然写完了,如果不参考代码,其实只有思路,还是撸不出来的…文章来源地址https://www.toymoban.com/news/detail-835326.html
到了这里,关于最优二叉搜索树 C#实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!