精华内容
下载资源
问答
  • 折半查找判定树平均查找长度

    万次阅读 2016-12-17 12:49:13
    从折半查找的过程看,以有序表的中间记录作为比较对象,并以中间记录将表分割为两个子表,...长度为n的折半查找判定树的构造方法为:⑴ 当n=0时,折半查找判定树为空;⑵ 当n>0时,折半查找判定树的根结点是有序表中

    从折半查找的过程看,以有序表的中间记录作为比较对象,并以中间记录将表分割为两个子表,对子表继续上述操作。所以,对表中每个记录的查找过程,可用二叉树来描述,二叉树中的每个结点对应有序表中的一个记录,结点中的值为该记录在表中的位置。通常称这个描述折半查找过程的二叉树为折半查找判定树。

    长度为n的折半查找判定树的构造方法为:

    ⑴ 当n=0时,折半查找判定树为空;

    ⑵ 当n>0时,折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录,根结点的左子树是与有序表r[1] ~ r[mid-1]相对应的折半查找判定树,根结点的右子树是与r[mid+1] ~ r[n]相对应的折半查找判定树。

    例如,长度为10的折半查找判定树的具体生成过程为:

    ⑴ 在长度为10的有序表中进行折半查找,不论查找哪个记录,都必须先和中间记录进行比较,而中间记录的序号为(1+10)/2=5(注意是整除即向下取整),即判定树的根结点是5,如图7-2(a)所示;

    ⑵ 考虑判定树的左子树,即将查找区间调整到左半区,此时的查找区间是
    [1,4],也就是说,左分支上为根结点的值减1,代表查找区间的高端high,此时,根结点的左孩子是(1+4)/2=2,如图7-2(b)所示;

    ⑶ 考虑判定树的右子树,即将查找区间调整到右半区,此时的查找区间是
    [6,10],也就是说,右分支上为根结点的值加1,代表查找区间的低端low,此时,根结点的右孩子是(6+10)/2=8,如图7-2(c)所示;

    ⑷ 重复⑵⑶步,依次确定每个结点的左右孩子,如图7-2(d)所示。

    这里写图片描述

    这里写图片描述

    对于折半查找判定树,需要补充以下两点:

    ⑴ 折半查找判定树是一棵二叉排序树,即每个结点的值均大于其左子树上所有结点的值,小于其右子树上所有结点的值;

    ⑵ 折半查找判定树中的结点都是查找成功的情况,将每个结点的空指针指向一个实际上并不存在的结点——称为外结点,所有外结点即是查找不成功的情况,如图7-2(e)所示。如果有序表的长度为n,则外结点一定有n+1个。

    在折半查找判定树中,某结点所在的层数即是查找该结点的比较次数,整个判定树代表的有序表的平均查找长度即为查找每个结点的比较次数之和除以有序表的长度。例如,长度为10的有序表的平均查找长度为:

    ASL=(1×1+2×2+3×4+4×3)/10=29/10

    在折半查找判定树中,查找不成功时的比较次数即是查找相应外结点时与内结点的比较次数。整个判定树代表的有序表在查找失败时的平均查找长度即为查找每个外结点的比较次数之和除以外结点的个数。例如,长度为10的有序表在查找失败时的平均查找长度为:

    ASL=(3×5+4×6)/11=39/11

    展开全文
  • 从折半查找的过程看,以有序表的中间记录作为比较对象,并以中间记录将表分割为两个子表,对子表...长度为n的折半查找判定树的构造方法为: ⑴ 当n=0时,折半查找判定树为空; ⑵ 当n>0时,折半查找判定树的根...

    从折半查找的过程看,以有序表的中间记录作为比较对象,并以中间记录将表分割为两个子表,对子表继续上述操作。所以,对表中每个记录的查找过程,可用二叉树来描述,二叉树中的每个结点对应有序表中的一个记录,结点中的值为该记录在表中的位置。通常称这个描述折半查找过程的二叉树为折半查找判定树。

    长度为n的折半查找判定树的构造方法为:

    ⑴ 当n=0时,折半查找判定树为空;

    ⑵ 当n>0时,折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录,根结点的左子树是与有序表r[1] ~ r[mid-1]相对应的折半查找判定树,根结点的右子树是与r[mid+1] ~ r[n]相对应的折半查找判定树。

    例如,长度为10的折半查找判定树的具体生成过程为:

    ⑴ 在长度为10的有序表中进行折半查找,不论查找哪个记录,都必须先和中间记录进行比较,而中间记录的序号为(1+10)/2=5(注意是整除即向下取整),即判定树的根结点是5,如图7-2(a)所示;

    ⑵ 考虑判定树的左子树,即将查找区间调整到左半区,此时的查找区间是

    [1,4],也就是说,左分支上为根结点的值减1,代表查找区间的高端high,此时,根结点的左孩子是(1+4)/2=2,如图7-2(b)所示;

    ⑶ 考虑判定树的右子树,即将查找区间调整到右半区,此时的查找区间是

    [6,10],也就是说,右分支上为根结点的值加1,代表查找区间的低端low,此时,根结点的右孩子是(6+10)/2=8,如图7-2(c)所示;

    ⑷ 重复⑵⑶步,依次确定每个结点的左右孩子,如图7-2(d)所示。

    对于折半查找判定树,需要补充以下两点: 
    ⑴ 折半查找判定树是一棵二叉排序树,即每个结点的值均大于其左子树上所有结点的值,小于其右子树上所有结点的值; 
    ⑵ 折半查找判定树中的结点都是查找成功的情况,将每个结点的空指针指向一个实际上并不存在的结点——称为外结点,所有外结点即是查找不成功的情况,如图7-2(e)所示。如果有序表的长度为n,则外结点一定有n+1个。 在折半查找判定树中,某结点所在的层数即是查找该结点的比较次数,整个判定树代表的有序表的平均查找长度即为查找每个结点的比较次数之和除以有序表的长度。例如,长度为10的有序表的平均查找长度为: 
    ASL=(1×1+2×2+3×4+4×3)/10=29/10 
    在折半查找判定树中,查找不成功时的比较次数即是查找相应外结点时与内结点的比较次数。整个判定树代表的有序表在查找失败时的平均查找长度即为查找每个外结点的比较次数之和除以外结点的个数。例如,长度为10的有序表在查找失败时的平均查找长度为: 
    ASL=(3×5+4×6)/11=39/11

    展开全文
  • 【哈尔滨工业大学2005 四、1(8分)】画出对长度为18的有序的顺序表进行折半查找时的判定树,并指出在等概率时查找成功的平均查找长度,以及查找失败时所需的最多的关键字比较次数。 判定树如下: 图1-1判定树 ...

    写在前边的话:你的支持是我写作的动力,有帮助到你的话麻烦点赞收藏呦。感激不尽!如有错误也请留言指正。

    考研数据结构练习,欢迎订阅我的专辑《考研数据结构题型分类讲解练习》


    【哈尔滨工业大学2005 四、1(8分)】画出对长度为18的有序的顺序表进行折半查找时的判定树,并指出在等概率时查找成功的平均查找长度,以及查找失败时所需的最多的关键字比较次数。

    判定树如下:

    图1-1判定树

     查找成功时的ASL=(1+4+12+32+15)/18=\frac{64}{18}


    查找失败时ASL=(52+30)/19=\frac{82}{19}

    图1-3

    以4*13=52为例,解释一下数字的含义。

    • 4:图中的□代表查找失败的节点,“4*13=52”这行的□需要查找四次。比如,对于16来说,查找到16需要四次,再往下找的时候判断它的左节点为空,而此时也就找到了□。
    • 13:这行一共有13个□需要查找四次
    • 52:这行查找失败的总次数是4*13次

    写在后边的话:你的支持是我写作的动力,有帮助到你的话麻烦点赞收藏呦。感激不尽!如有错误也请留言指正。

    考研数据结构练习,欢迎订阅我的专辑《考研数据结构题型分类讲解练习》

    展开全文
  • 折半查找判定数及平均查找长度

    万次阅读 多人点赞 2016-07-06 13:28:31
    折半查找判定数及平均查找长度 折半查找的过程看,可用二叉树来描述,二叉树中的每个结点对应有序表中的一个记录,结点中的值为该记录在表中的位置。通常称这个描述折半查找二叉树的过程称为折半查找判定树。 ...

    折半查找判定数及平均查找长度

    折半查找的过程看,可用二叉树来描述,二叉树中的每个结点对应有序表中的一个记录,结点中的值为该记录在表中的位置。通常称这个描述折半查找二叉树的过程称为折半查找判定树。

    例如:长度为10的折半查找判定树的具体生成过程:
    都遵循这个规律,左孩子结点<根结点<右孩子结点
        (1)在长度为10的有序表中进行折半查找,不论查找哪个记录,都必须和中间记录进行比较,而中间记录为
    (1+10)/2 =5  (注意要取整)   即判定数的的根结点为5,如图7-2(a)所示。
         (2)考虑判定树的左子树,即将查找区域调整到左半区,此时的查找区间为[1,4],那么中间值为(1+4)/2 =2 (注意要取整) ,所以做孩子根结点为2,如图7-2(b)所示。
         (3)考虑判定树的右子树,即将查找区域调整到右半区,此时的查找区间为[6,10],那么中间值为(6+10)/2 =8 (注意要取整) ,所以做孩子根结点为8,如图7-2(c)所示。
           (4)重复以上步骤,依次去确定左右孩子、


    1.折半查找是一棵二叉排序树,每个根结点的值都大于左子树的所有结点的值,小于右子树所有结点的值。
    2.折半查找判定数中的结点都是查找成功的情况,将每个结点的空指针指向一个实际上不存在的结点————外结点,所有外界点都是查找不成功的情况,如图7-2(e)所示。如果有序表的长度为n,则外结点一定有n+1个
    折半查找判定数中,某结点所在的层数就是即将要比较的次数,整个判定树代表的有序表的平均查找长度即为查找每个结点的比较次数之和除以有序表的 长度。
      例如:长度为10的有序表的平均查找长度为
            ASL=(1*1+2*2+3*4+4*3)/10=29/10;

    折半查找判定数中,查找不成功的次数即为查找相应外结点与内结点的比较次数。整个判定树代表的有序表的平均查找长度。查找失败时的有序表的平均查找长度即为查找每个外结点的比较次数之和除以外结点的个数。
    如图7-2(e)所示
       例如:查找失败时,。长度为10的有序表的平均查找长度为
     ASL=(3*5+4*6)/11=39/11;

    展开全文
  • 折半查找判定树的高度分析 最近看到一道题,在说有序数据集,长度为n时,其最大查找长度为多少 我们知道折半查找每次分块,左半部分占n/2的长度, 中间的单个元素被剔除, 右半部分占有剩下的元素, 因此找出递推...
  • 折半查找判定数及平均查找长度 折半查找的过程看,可用二叉树来描述,二叉树中的每个结点对应有序表中的一个记录,结点中的值为该记录在表中的位置。通常称这个描述折半查找二叉树的过程称为折半查找判定树。 ...
  • 复习数据结构做的笔记: ...长度为12的有序表画出折半查找判定树 12>2^3,即最大能画出3层的满二叉树,接着将剩余5个结点插入该 先插入h,a的左右子树结点个数都为3,则到c,c的左右子树结
  • 折半查找判定树

    千次阅读 多人点赞 2020-12-09 21:23:22
    例如:长度为10的折半查找判定树的具体生成过程,都遵循左孩子结点<根结点<右孩子结点 在长度为10的有序表中进行折半查找,不论查找哪个记录,都必须和中间记录进行比较,而中间记录为(1+10)/2 =5 (注意要...
  • 由有序序列折半查找构建判定树

    万次阅读 多人点赞 2016-10-25 16:07:13
    需要特别强调的是折半查找判定树是一棵平衡。一般对于一个有序序列折半查找过程,需要从中间结点开始结点比较起,这样就会进入左子树或者右子进行比较,因此,只要明白了的根结点怎么确定的,就能够递归的...
  • 以下给出我在学习中总结的一种比较简便的构造折半二叉判定树的思路以及方法: 思路分析: 在计算mid值时,使用的时mid=(low+high)/2 。这里由于mid为int类型,自动默认为向下取整,因此对于一个长度为n序列进行...
  • 二叉判定树 又称 二叉排序,是具有以下性质的二叉树: 若左子树不为空,则左子树上各个节点的...已知一个顺序存储是有序表为(15,26,34,39,45,56,58,63,74,6),试画出对应的二叉判定树,求其平均查找长度。 ...
  • 【数据结构】折半查找及其二叉判定树画法

    万次阅读 多人点赞 2019-09-25 23:55:40
    折半查找又叫二分查找,是数据结构中一种很重要的查找方式。 其特点有以下几个: 只能对有序的顺序表进行查找。 是一种静态查找。 查找的平均时间复杂度为o(log...折半查找和二叉排序查找的平均查找长度均取决...
  • 折半查找平均查找长度

    千次阅读 2019-12-23 18:15:08
    建完全二叉树 例如长度为12的有序线性表,构建完全二叉树,如下图: 平均查找长度为:3.1
  • 查找在实际应用中也是最为常见的。...动态查找表:在查找过程向查找表中删除或插入一个元素,即若在查找过程中同时插入查找表中不存在的元素,或者从查找表中删除已存在的某个元素。 本小节整理的是静
  • 折半查找成功时的平均查找长度

    千次阅读 2019-02-14 09:30:30
    /** * 实验题目: * 求折半查找成功时的平均查找长度 * 实验目的: * 深入掌握折半查找过程和折半查找算法分析 * 实验内容: ...* 1、输出n=11时的判定树并求成功情况下的平均查找长度ASL。 * 2、通过构...
  • 查找表的概念 查找表是由同一类型的数据元素构成的集合。例如电话号码簿和字典都可以看作是一张查找表。 在查找表中只做查找操作,而不改动表中数据元素,称此类查找表为静态查找表;反之,在查找表中做查找操作的...
  • 折半查找和二叉排序

    千次阅读 多人点赞 2019-10-10 14:19:28
    折半查找的性能分析可以用二叉判定树来衡量,平均查找长度和最大查找长度都是O(logn); 二叉排序的查找性能与数据的输入顺序有关,最好情况下的平均查找长度折半查找相同,但最坏情况时,即形成单支时,其...
  • 做这个题之前,建议你先看一下《折半查找判定树 二叉排序 查找成功平均查找长度 查找失败平均查找长度》 好,假设你已经看过《折半查找判定树 二叉排序 查找成功平均查找长度 查找失败平均查找长度》了。如果,...
  • 这个判定树与霍夫曼的区别在于折半查找判定树的内节点也是待查找元素,而叶子节点是区间。因此折半查找与BST更相似,只不过折半查找判定树是固定的,不是动态结构。另一个区别在于折半查找是以元素的序号来...
  • 折半查找判定树高为log2(n+1)向上取整 下面投放折半查找代码 #include <stdio.h> #include <stdlib.h> #define MaxSize 50 #define keyType int //顺序表结构体 typedef ...
  • 本文主要介绍了顺序查找、折半查找、静态最优查找和索引顺序表查找等几种查找算法。
  • 文章目录查找查找的概念顺序查找顺序查找-算法原理顺序查找-算法实现顺序查找-性能分析折半查找折半查找-算法原理折半查找-算法实现折半查找-性能分析分块查找分块查找-算法原理分块查找-算法实现分块查找-性能分析 ...
  • ASL(Average Search Length),即平均查找长度,在查找运算中,由于所费时间在关键字的比较上,所以把平均需要和待查找值比较的关键字次数称为平均查找长度。 它的定义是这样的: 其中n为查找表中元素个数,Pi为...
  • 一、折半查找
  • 二分查找(折半查找)

    2018-11-12 23:13:22
    二分查找(折半查找) title: 二分查找 tags: 数据结构与算法之美 author: 辰砂 一、简介 二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,...
  • 静态查找:顺序查找和折半查找

    千次阅读 2017-06-09 15:18:18
    一、静态查找:  只是起查询或检索的作用,不涉及插入、删除,反之为动态查找。 二、顺序查找  顺序查找过程中往往设置监视哨,在查找过程中不用... 考虑到查找不成功的情况,顺序查找表的平均查找长度为:3(n+1)
  • 【数据结构】顺序查找和折半查找

    千次阅读 多人点赞 2021-04-03 08:07:36
    数据结构之查找算法 摘要:在本篇文章中,主要讲述了在数据结构中所涉及的几大查找算法,包括:顺序查找、折半查找、分块查找和散列表查找。...在查找算法中,最为重要的便是算法的平均查找长度, ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,392
精华内容 956
关键字:

折半查找判定树平均查找长度