次优二叉查找树(次优查找树)_递归和非递归实现_20230414

这篇具有很好参考价值的文章主要介绍了次优二叉查找树(次优查找树)_递归和非递归实现_20230414。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

次优二叉查找树(次优查找树)-递归和非递归实现

  1. 前言

当有序表中的各记录的查找概率相等的时候,采用折半查找效率可以提升查找性能;如果有序表中的各记录的查找概率不相等,那么折半查找就不再适用。

如果只考虑查找成功的情况,则使查找性能达到最佳性能的判定树就是带权路径长度的之和,也即路径各个记录的查找深度与查找权值的乘积之和,当这个和取得最小值的时候。
P H = Σ c i ∗ w i ,   i ∈ ( 1.... n ) PH=Σc_i*w_i,\ i∈(1....n) PH=Σciwi, i(1....n)
最优二叉查找树需要利用到动态规划的相关知识,之前的文章有所涵盖,有兴趣的读者可查阅之前的文章进行理解。本文所阐述的方法,采用的是贪婪的编程思维,构建出次优二叉查找树(Nearly optimal binary search tree)。

  1. 问题分析

已知一个按照关键有序的记录:

(rl,rl+1…rh)

其中关键字为升序排列,对于每个记录的权值

(wl,wl+1…wh)

现在构造一颗二叉树,是这颗二叉树的带权路径长度PH在同样的二叉树中近似最小,我们称这类二叉树为次优二叉树。

利用贪婪方法,构造次优查找树的方法是:首先在序列l…h构造根节点root(i),使根节点左右两颗子树的差值取最小值,那么这个点就是根节点。采用公式,让理解更为方便。

Δpi=|Σwj(i+1<j<h)-Σwj(l<j<i-1)|

求得i之后,然后分别对子序列(rl,rl+1…ri-1)和(ri+1,rr+2…rh)再分别构造两颗次优二叉树,并设定其根节点为root(i),分别定位root(i)的左子树和右子树。

次优二叉查找树(次优查找树)_递归和非递归实现_20230414

根据上面的分析,引入递归算法和非递归算法构造次优二叉书。

  1. 递归算法分析

由于构造二叉树的过程需要分别对左右子树进行处理,所以整体的需要涉及两次递归调用。二叉树的构造过程和遍历过程非常类似,都是对左右子树访问的过程。针对本问题,我们选择先序遍历模式完成问题的解答。

由于采用递归,那么递归的结束条件是什么呢? 递归的结束条件就是遍历到叶子结点,在本问题当中,可以理解问题根节点的下标等于high或者low的时候,此时递归就满足结束条件(不再进行入栈操作)。

  1. 递归代码C语言实现

递归函数的操作对象为记录的权值和,在递归函数之前需要求解sw[0…n-1],我们使用void find_sw(int *sw, SSTable st)函数完成此项任务。

递归函数中包含子树下标的最小值与最大值,在先序递归之前,通过迭代求出根节点所在位置,然后与high和low进行比较,我们使用void second_optimal(BiTree *bt, SElemType *rec, int *sw, int low, int high)函数完成这项任务。

a.) find_sw函数实现,注意第1个元素的sw值为0

void find_sw(int *sw, SSTable st)
{
    int i;

    *(sw + 0) = 0;

    for (i = 1; i <= st.len; i++)
    {
        sw[i] = sw[i - 1] + st.elem[i].value;
    }
}

b.) second_optimal函数实现

void second_optimal(BiTree *bt, SElemType *rec, int *sw, int low, int high)
{
   int min;
   int i;
   int j;
   int dw;
   int delta;

   min=INT_MAX;
   dw=sw[high]+sw[low-1];
   i=low;

   for(j=i;j<=high;j++)
   {
        delta=abs(dw-(sw[j]+sw[j-1]));
        if(delta<min)
        {
            i=j;
            min=delta;
        }
   }

   *bt=(BiTree)malloc(sizeof(BiTNode));
   (*bt)->data=rec[i];

   if(i==low)
   {
        (*bt)->lchild=NULL;
   }
   else
   {
        second_optimal(&((*bt)->lchild),rec,sw,low,i-1);
   }

   if(i==high)
   {
        (*bt)->rchild=NULL;
   }
   else
   {
        second_optimal(&((*bt)->rchild), rec, sw, i + 1, high);
   }
}
  1. 非递归实现

为了实现非递归建立次优二叉查找树,就需要借助栈(stack)的概念,本质是就是借助自定义栈来实现编译器中的函数栈的管理。栈实际上储存的是记忆的状态,采用“后进先出”模式来模拟编译器中的函数栈。我们在利用栈实现功能之前,首先需要定义过程中需要记忆(保存)哪些参数。很明显,对于本问题,我们至少需要保留三个变量参数的当前状态,下一个待处理二叉树结点的指针(它必定来自于当前结点的左孩子或者右孩子),子树需要处理的范围,也就是low和high的下标位置,有了这些背景分析,定义栈保存的元素:

typedef struct StackNode
{
    BiTree node;
    int    low;
    int    high;
}StackNode;

基于上述定义,非递归次优二叉树实现函数如下:

void second_optimal(BiTree *bt, SElemType *rec, int *sw, int len)
{
   int min;
   int i;
   int j;
   int delta;
   int dw;
   int low;
   int high;

   SqStack S;
   StackNode st_node;
   StackNode temp;

   low=1;
   high=len;
   InitStack_Sq(&S);

   st_node.low=low;
   st_node.high=high;
   st_node.node=(BiTree)malloc(sizeof(BiTNode));
   *bt = st_node.node;

   Push_Sq(&S,st_node);

   
   while(!StackEmpty_Sq(S))
   {
        Pop_Sq(&S,&temp);

        low=temp.low;
        high=temp.high;
        i=low;
        min=INT_MAX;
        dw=sw[high]+sw[low-1];

        for(j=i;j<=high;j++)
        {
            delta=abs(dw-sw[j]-sw[j-1]);

            if(delta<min)
            {
                i=j;
                min=delta;
            }
        }

        temp.node->data=rec[i];


        //it should start with from pushing the right child into the stack
        if(i==high)
        {
            temp.node->rchild=NULL;
        }
        else
        {
            st_node.low=i+1;
            st_node.high=high;
            temp.node->rchild=(BiTree)malloc(sizeof(BiTNode));
            st_node.node=temp.node->rchild;

            // here it is st_node.node instead of st_node.node->rchild
            Push_Sq(&S, st_node);
        }

        if (i == low)
        {
            temp.node->lchild = NULL;
        }
        else
        {
            st_node.low = low;
            st_node.high = i - 1;
            temp.node->lchild = (BiTree)malloc(sizeof(BiTNode));
            st_node.node= temp.node->lchild;
            // here it is st_node.node instead of st_node.node->lchild

            Push_Sq(&S, st_node);
        }
   }

}

上述函数的实现涉及到栈操作,有兴趣的读者可以参考《数据结构》严蔚敏版自行实现,在此不再赘述。对于上述非递归代码,请读者自行理解。

  1. 总结

次优二叉查找树是一种基于贪心算法实现的二叉树,它摒弃了动态规划建立最优二叉树的繁琐流程,同时又保留了查询的效率。本文针对次优二叉树,采用递归和迭代两种不同的方式加以实现,加深了对递归的理解,同时也复习了栈(stack)的相关知识。

参考资料:文章来源地址https://www.toymoban.com/news/detail-415370.html

  1. 《数据结构》-清华大学,严蔚敏

到了这里,关于次优二叉查找树(次优查找树)_递归和非递归实现_20230414的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

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

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

    2024年02月16日
    浏览(44)
  • C语言实现八大排序算法(详解插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序(递归和非递归)、归并排序(递归和非递归)和计数排序)

    本篇文章使用C语言实现了数据结构中常见的八大排序算法,它们分别是 插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序和计数排序 。在排序算法的实现过程中,每种算法都有其独特的特点和适用场景。插入排序通过逐步构建有序序列来排序,希尔

    2024年01月24日
    浏览(51)
  • 二叉排序树的定义及基本操作(构造、查找、插入、删除)递归及非递归算法

    二叉排序树(Binary Sort Tree, BST),也称二叉查找树。 二叉排序树或者是一棵空树,或者是一棵具有下列特性的非空二叉树: 1) 若左子树非空,则左子树上所有结点均小于根结点的值; 2) 若右子树非空,则右子树上所有结点均大于根结点的值;

    2024年02月08日
    浏览(58)
  • 快速排序的非递归实现、归并排序的递归和非递归实现、基数排序、排序算法的时间复杂度

    我们使用一个栈来模拟函数的递归过程,这里就是在利用栈分区间。把一个区间分为 [left,keyi-1][key][keyi+1,right]递归下去,直至区间不存在或left right。 如图所示: 先把整体的区间压进去,然后出栈,处理完毕后找到keyi再分为左右两个区间。然后往栈里压有区间,压左区间,就

    2024年02月17日
    浏览(49)
  • 十大排序算法(中):冒泡排序,快速排序(递归和非递归)、归并排序(递归和非递归)

    这篇文章,我们接着来讲剩下的排序算法:冒泡排序,快速排序(递归和非递归)、归并排序(递归和非递归) 中心思想: 交换就是指根据序列中的两个元素的比较结果来对换这两个元素在序列中的位置,特点就是:将值较大的元素向序列尾部移动,将值较小的元素向序列

    2024年02月05日
    浏览(55)
  • 动态规划:最优二叉搜索树

    给定一个序列 有n个有序且各不相同的键, 集合 表示在K中成功的搜索的概率; 为n+1 个不同的哑键,表示所有在和 之间的值, 表示不成功的搜索的概率. 创建二叉搜索树, 使得其期望搜索花费最小。 如果一棵最优二叉搜索树T的子树T’含有键那么这个子树T’肯定是子问题键

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

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

    2024年02月07日
    浏览(42)
  • 快速排序算法的递归和非递归

    基本思路 选择一个基准值,将数组划分三个区域,小于基准值的区域位于左侧,等于基准值的区域位于中间,大于基准值的区域位于右侧。将大于和小于区域继续进行分区,周而复始,不断进行分区和交换,直到排序完成 递归 思路: 步骤1: 在当前分区范围[l,r]中随机选中一

    2024年02月09日
    浏览(47)
  • 排序算法:归并排序(递归和非递归)

    朋友们、伙计们,我们又见面了,本期来给大家解读一下有关排序算法的相关知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏: C语言:从入门到精通 数据结构专栏: 数据结构 个  人  主  页 : stackY、 ​ 目录 1.归并排序

    2024年02月07日
    浏览(37)
  • 【动态规划】最优二叉搜索树——算法设计与分析

    二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉搜索树。 规定树根为第0层,圆结点为数

    2024年02月16日
    浏览(38)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包