当前位置: 首页 > news >正文

软设每日打卡——折半查找二叉判定树、平衡二叉树

对长度为n的有序顺序进行折半查找(即二分查找)的过程可用一颗判定树表该判定树的形态符合( )的特点。

A、最优二叉树(哈夫曼树)        B、平衡二叉树

C、完全二叉树                              D、最小生成树                                答案:B

解:        折半查找又称二分查找,要求表有序,即表中元素an关键字有序,而且必须顺序存储

        折半查找可用一个称为判定树的二叉树描述(如题所述),判定树中的每一个结点对应表中的一个元素,但结点的值不是关键字的值,而是元素在表中的位置。

        题目只是在问折半查找的判定树的形态,那么这里我们主要需要记住的点是,折半查找判定树必为平衡树(平衡二叉树)。即由折半查找过程中所产生的树,首尾以二取整。

        那么为什么折半查找判定树一定是平衡二叉树?因为折半查找的过程是每次将查找区间折半,然后根据中间元素与查找值的大小关系确定下一步的查找区间,这个过程可以看作是在一颗二叉树上进行的。折半查找树是一种二叉搜索树它的每个节点都满足左子树的所有节点的值都小于节点的值,右子树的所有节点的值都大于节点的值。(这句没太懂,我再研究一下)在折半查找树中,每个节点的左子树和右子树的高度差不超过1,因此它是一棵平衡二叉树。判定树是一种用于分析算法的数据结构,它用来表示算法在处理输入时所做的决策。对于折半查找算法,其判定树的每个节点表示一个比较操作,它的左子树和右子树分别比当前节点小和比当前节点大的元素。由于折半查找树是一颗平衡二叉树,因此它的判定树也一定是一颗平衡二叉树。

移到上方

        平衡二叉树是一种特殊的二叉树,它的左右子树高度差(简称平衡因子)的绝对值不超过1(即-1,0,1),这样可以保证树的高度不会太高,从而保证了树的查找效率

平衡二叉树的两个条件:

        1、是二叉排序树

        2、任何一个节点的左子树或右子树都是平衡二叉树(左右高度差小于1

横线复制

这里拓展一下这个判定树的画法,我看的这个博主的文:(这个电脑粘贴坏了,后续我补充)

满二叉树(Full Binary Tree):

所有节点的度要么为0,要么为2,且所有的叶子节点都在最后一层。

不全的内容我后续补充


http://www.mrgr.cn/news/62635.html

相关文章:

  • 二、k8s快速入门之docker+Kubernetes平台搭建
  • html简易流程图
  • 使用wordcloud与jieba库制作词云图
  • Dockerfile制作Oracle19c镜像
  • IDEA修改生成jar包名字的两种方法实现
  • Docker-安装
  • 多线程案例---单例模式
  • 2024年NSSCTF秋季招新赛-WEB
  • Convolution 卷积
  • 前端笔面试查漏补缺
  • 鸿蒙系统:核心特性、发展历程与面临的机遇与挑战
  • JSP水果商城管理系统WEB项目
  • Vue中path和component属性
  • 宠物空气净化器是否有用?五大高性价比宠物空气净化器种草推荐
  • 前端如何安全存储密钥,防止信息泄露
  • 高级SQL技巧:优化查询与提升性能(附11个示例代码)
  • #HarmonyOS:名词
  • Leetcode 198. 打家劫舍 动态规划
  • 拆分PPOCRLabel标注的数据集并生成识别数据集
  • 动态规划-回文串问题——647.回文子串
  • Python使用 try-except 捕获与处理异常
  • 从安装到实战:Spring Boot与RabbitMQ的终极整合指南
  • Go 语言解析 yaml 文件的方法
  • ES聚合(仅供自己参考)
  • 【安全性分析】BAN逻辑 (BAN Logic)之详细介绍
  • 天润融通邀您参加AI破局·聚力增长行业论坛