最优二叉搜索树 C#实现

这篇具有很好参考价值的文章主要介绍了最优二叉搜索树 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 = 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);

最优二叉搜索树 C#实现,c#,开发语言,算法,动态规划最优二叉搜索树

程序核心代码

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】哈夫曼编码(最优二叉树实现

    哈夫曼编码 等长编码:占的位置一样 变长编码(不等长编码):经常使用的编码比较短,不常用的比较短 最优:总长度最短 最优的要求:占用空间尽可能短,不占用多余空间,且不能有二义性 这里给出哈夫曼二叉树的实现: HuffmanTree.h: 测试数据(主函数): 运行结果截图

    2024年02月16日
    浏览(44)
  • 最优二叉搜索树(Optimal Binary Search Tree)_20230401

    前言 如果有序数组或有序表中的各个元素查找概率相等,那么采用二叉搜索树(BST)进行折半查找,性能最优。如果有序表中各个记录的查找概率不相等,情况又如何呢? 先看一个具体例子。已知有序表keys, 同时给出各个元素的查询频率,注意到各个元素的查询频率不相同。

    2024年02月12日
    浏览(51)
  • 【算法设计与分析】(三)动态规划_更新中:斐波那契、二项式系数、树的最大独立集、最长递增、公共子序列、编辑距离、Hischberg、最优二叉搜索树、交替拿硬币、石子合并、背包、乘电梯

    分治 动态规划本篇 还差一堆 贪心 网络流 首先,怕误人子弟必须声明一下 本人很菜 (越复习越觉得完蛋了 作为一个科班研究生算法学成这样非常惭愧(跪 ,可能写的都不是很懂,很多内容打算背过去了。因为我发现好像真的有人看所以多提醒一句。。(大家就只食用目录

    2024年01月19日
    浏览(98)
  • 数据结构-哈夫曼树(最优二叉树)

    目录 一、引言 二、哈夫曼树的概念 三、哈夫曼树的构建 1. 构建步骤 2. 构建示例 四、哈夫曼编码 1. 编码规则 2. 编码示例 五、哈夫曼树的应用 1. 数据压缩 2. 文件加密 六、总结 在计算机科学中,数据结构是指计算机中数据组织、管理和存储的方式。数据结构是计算机科学的

    2024年02月07日
    浏览(42)
  • Python实现GBDT(梯度提升树)分类模型(GradientBoostingClassifier算法)并应用网格搜索算法寻找最优参数项目实战

    说明:这是一个机器学习实战项目(附带 数据+代码+文档+视频讲解 ),如需 数据+代码+文档+视频讲解 可以直接到文章最后获取。 1.项目背景 GBDT是Gradient Boosting Decision Tree(梯度提升树)的缩写。GBDT分类又是建立在回归树的基础上的。 本项目应用GBDT算法实现多分类模型。

    2024年02月13日
    浏览(45)
  • 次优二叉查找树(次优查找树)_递归和非递归实现_20230414

    前言 当有序表中的各记录的查找概率相等的时候,采用折半查找效率可以提升查找性能;如果有序表中的各记录的查找概率不相等,那么折半查找就不再适用。 如果只考虑查找成功的情况,则使查找性能达到最佳性能的判定树就是带权路径长度的之和,也即路径各个记录的查

    2023年04月16日
    浏览(36)
  • 二叉搜索树的实现(C语言)

    目录 前言: 一:准备工作 (1)需要的头文件 (2)树节点结构体描述 (3)初始化 二:指针 三:插入新节点(建树) (1)生成一个新节点 (2)找插入位置 四:查找和遍历 (1)查找 (2)遍历 五:删除节点 六:全部代码 (1)BinarySearchTree.h(声明) (2)BinarySearchTree.c(函数具体实现) (3)test.c(测试) 二叉

    2024年02月06日
    浏览(32)
  • 使用 Go 语言实现二叉搜索树

    原文链接: 使用 Go 语言实现二叉搜索树 二叉树是一种常见并且非常重要的数据结构,在很多项目中都能看到二叉树的身影。 它有很多变种,比如红黑树,常被用作 std::map 和 std::set 的底层实现;B 树和 B+ 树,广泛应用于数据库系统中。 本文要介绍的二叉搜索树用的也很多,

    2024年02月14日
    浏览(39)
  • C语言实现哈希搜索算法

    哈希搜索,也叫散列查找,是一种通过哈希表(散列表)实现快速查找目标元素的算法。哈希搜索算法通常适用于需要快速查找一组数据中是否存在某个元素的场景,其时间复杂度最高为 O(1),而平均情况下的时间复杂度通常相当接近 O(1),因此在实际应用中具有很高的效率和

    2024年02月12日
    浏览(31)
  • 二叉树中序遍历非递归算法C语言实现

    // //  Inordertraverse.c //  二叉树链式存储 // //  Created by 丘** on 2021/7/28. // #include \\\"Inordertraverse.h\\\" #include stdbool.h #includestdlib.h typedef   struct StackNode {     int data;     struct StackNode* next;      }StackNode; typedef struct BiTNode {     int data;     struct BiTNode* lchild,* rchild;           }BiTnode

    2024年02月02日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包