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

    千次阅读 2019-12-02 20:04:22
    通常称这个描述折半查找过程的二叉树为折半查找判定树,简称判定树。 判定树的构造方法 ⑴ 当n=0时,折半查找判定树为空; ⑵ 当n>0时, 折半查找判定树的根结点为mid=(n+1)/2, 根结点的左子树是与有序表r...

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

     

    判定树的构造方法

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

     

    判定树的特点

    • 任意两棵折半查找判定树,若它们的结点个数相同,则它们的结构完全相同

    • 具有n个结点的折半查找树的高度为

     

    判定树的性质

    • 任意结点的左右子树中结点个数最多相差1

    • 任意结点的左右子树的高度最多相差1

    • 任意两个叶子所处的层次最多相差1

     

     

    展开全文
  • 折半查找定义 折半查找算法实现及查找过程 ...折半查找判定树 查找成功 查找失败 总结 补充 链接 查找成功 查找失败 算法思路 算法实现 折半查找判定树 折半查找ASL 折半查找性能 总结 ...

    折半查找定义

    在这里插入图片描述

    折半查找算法实现及查找过程

    public int Binary_Search(int[] a,int n,int key){
    		int low=1,high=n,mid;
    		while(low<=high){
    			mid=(int)((low+high)/2);
    			if(key<a[mid])
    				high=mid-1;
    			else if(key>a[mid])
    				low=mid+1;
    			else return mid;
    		}
    		return 0;
    }
    

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    折半查找判定树

    查找成功
    在这里插入图片描述
    查找失败
    在这里插入图片描述

    总结

    在这里插入图片描述
    在这里插入图片描述

    补充

    链接
    查找成功
    在这里插入图片描述
    查找失败
    在这里插入图片描述
    在这里插入图片描述
    算法思路
    在这里插入图片描述
    算法实现
    在这里插入图片描述
    在这里插入图片描述
    折半查找判定树
    在这里插入图片描述
    折半查找ASL
    在这里插入图片描述
    在这里插入图片描述
    折半查找性能
    在这里插入图片描述
    总结
    在这里插入图片描述
    在这里插入图片描述

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

    万次阅读 多人点赞 2016-01-08 18:16:27
    折半查找判定树及平均查找长度 从折半查找的过程看,以有序表的中间记录作为比较对象,并以中间记录将表分割为两个子表,对子表继续上述操作。所以,对表中每个记录的查找过程,可用二叉树来描述,二叉树中的每个...

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

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

    长度为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判定树 ...
  • 折半查找判定树的画法思路: 1.先画出满足有序表长度的最大满二叉树,然后将剩下的结点个数一个个插入该树 2.从上往下看,比较每个结点的左右子树结点个数,如果左右子树结点个数相同优先放右边,左边比右边少就放...
  • 折半查找判定树实际上是一棵二叉排序树,它的中序序列是一个有序序列。可以在树结点上依次填上相应的元素,符合折半查找规则的树即是所求。 B选项4、5相加除二向上取整,7、8相加除二向下取整,矛盾。C选项,3、4...
  • 答案解析: 折半查找判定树实际上是一棵二叉排序树,它的中序序列是一个有序序列。可以在树结点上依次填上相应的元素,符合折半查找规则的树即是所求。 B选项4、5相加除二向上取整,7、8相加除二向下取整,矛盾。C...
  • 折半查找判定树的构建

    千次阅读 2018-10-30 18:21:26
    选择一种方式,即可以向上取整也可以向下取整,但是整个构造过程中必须选择且只选择一种,如果两种方式同时进行就是错的。
  • 二叉排序树(vs折半查找判定树

    千次阅读 2020-06-21 11:40:35
    二叉排序
  • 这道题考察的是折半查找时中间点的选择,当剩余序列为偶数个时,我们应该向上取整还是向下取整。例如对1,2,3,4四个数进行排序时,应该选2做中间点还是选3做中间点。实际上并没有要求,选哪个都能完成折半查找,...
  • ![图片说明](https://img-ask.csdn.net/upload/202010/27/1603811385_177013.jpg)这道题目考的是折半查找判定树
  • 折半查找判定树

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

    万次阅读 多人点赞 2016-07-06 13:28:31
    通常称这个描述折半查找二叉树的过程称为折半查找判定树。 例如:长度为10的折半查找判定树的具体生成过程: 都遵循这个规律,左孩子结点  (1)在长度为10的有序表中进行折半查找,不论查找哪个记录,都...
  • 由有序序列折半查找构建判定树

    万次阅读 多人点赞 2016-10-25 16:07:13
    需要特别强调的是折半查找判定树是一棵平衡树。一般对于一个有序序列折半查找过程,需要从中间结点开始结点比较起,这样就会进入左子树或者右子树进行比较,因此,只要明白了树的根结点怎么确定的,就能够递归的...
  • 通常称这个描述折半查找二叉树的过程称为折半查找判定树。 例如:长度为10的折半查找判定树的具体生成过程: 都遵循这个规律,左孩子结点<根结点<右孩子结点     (1)在长度为10...
  • 以下给出我在学习中总结的一种比较简便的构造折半二叉判定树的思路以及方法: 思路分析: 在计算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...折半查找和二叉排序查找的平均查找长度均取决...
  • 查找在实际应用中也是最为常见的。...动态查找表:在查找过程向查找表中删除或插入一个元素,即若在查找过程中同时插入查找表中不存在的元素,或者从查找表中删除已存在的某个元素。 本小节整理的是静
  • 任意两棵折半查找判定树,若它们的结点个数相同,则它们的结构完全相同 任意结点的左右子树中结点个数最多相差1 任意结点的左右子树的高度最多相差1 任意两个叶子所处的层次最多相差1 完全二叉树:如果二叉树的深度...
  • 在这里,我们不妨设折半查找是向下取整的,所以存在: 情况一:当剩余查找个数为偶数的时候,在中表现为对应节点左边的子节点总数比右边子节点总数少一个。例如,在结点1,2,3,4中查找 low=1,high=4 min=2(下...

空空如也

空空如也

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

折半查找判定树