二分法,平衡二叉树、B树、B+树

2023-11-14

二分法

二分法查找

首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功

算法要求

必须采用顺序存储结构
必须按关键字大小有序排列

比较次数

计算公式:
当顺序表有n个关键字时:
查找失败时,至少比较a次关键字;查找成功时,最多比较关键字次数是b
a,b,n均为正整数

二分法到二叉树

二分法是我们常用的一种查找算法,可以有效的提升数据找找的效率,其实现思路是:
首先对数据集进行排序
找到数据集中间位置的节点
用查找的条件和中间节点进行比较,等于则直接返回,中间节点数据小于查找条件则说明数据在排序列表的左边,大于则说明数据在排序列表的右边。

平衡二叉树

平衡二叉树概念

平衡二叉树是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

平衡二叉树的构建规则

(1)非叶子节点只能允许最多两个子节点存在
(2)每一个节点的左边子节点值小于当前节点,右边的子节点值大于当前节点;
(3)通过平衡算法(比如Treap、AVL、红黑树),保证树左右节点的高度相差不超过2层

平衡二叉树特点

平衡二叉树是采用二分法思维把数据按规则组装成一个树形结构的数据,用这个树形结构的数据减少无关数据的检索,大大的提升了数据检索的速度;平衡二叉树的数据结构组装过程有以下规则:

总结平衡二叉树特点:
(1)非叶子节点最多拥有两个子节点;
(2)非叶子节值大于左边子节点、小于右边子节点;
(3)树的左右两边的层级数相差不会大于1;
(4)没有值相等重复的节点;

B树(B-tree)

B树和平衡二叉树的不同之处是:B树属于多叉树又名平衡多路查找树(查找路径不止两个),数据库索引技术里大量使用着B树和B+树的数据结构。

B树的构建规则

(1)排序方式:所有节点关键字是按递增次序排列,并遵循左小右大原则;
(2)子节点数:非叶节点(根节点和枝节点)的子节点数 >1、且子节点数量<=M 、且M>=2,空树除外(注:M阶代表一个树节点最多有多少个查找路径,M=M路,当M=2则是2叉树,M=3则是3叉);
(3)关键字数:枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个(注:ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2);
(4)所有叶子节点均在同一层、叶子节点除了包含了关键字 和 关键字记录的指针外,也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子;

B树的查询流程

如果我们需要找到E字母,查找流程如下(26个字母顺序)

(1)获取根节点的关键字进行比较,当前根节点关键字为M,E<M(26个字母顺序),所以往找到指向左边的子节点(二分法规则,左小右大,左边放小于当前节点值的子节点、右边放大于当前节点值的子节点);
(2)拿到关键字D和G,D<E<G 所以直接找到D和G中间的节点;
(3)拿到E和F,因为E=E 所以直接返回关键字和指针信息(如果树结构里面没有包含所要查找的节点则返回null);

B+树

B+树是在B树的基础上又一次的改进,其主要对两个方面进行了提升,一方面是查询的稳定性,另外一方面是在数据排序方面更友好。

B+树构建规则

(1)B+树的非叶子节点不保存具体的数据,而只保存关键字的索引,而所有的数据最终都会保存到叶子节点。因为所有数据必须要到叶子节点才能获取到,所以每次数据查询的次数都一样,这样一来B+树的查询速度也就会比较稳定,而B树的查找过程中,不同的关键字查找的次数很有可能都是不同的(有的数据可能在根节点,有的数据可能在最下层的叶节点),所以在数据库的应用层面,B+树就显得更合适
(2)B+树叶子节点的关键字从小到大有序排列,左边结尾数据都会保存右边节点开始数据的指针。因为叶子节点都是有序排列的,所以B+树对于数据的排序有着更好的支持
(3)非叶子节点的子节点数=关键字数

B+树和B树的对比

1、B+树查询速度更稳定:B+所有关键字数据地址都存在叶子节点上,所以每次查找的次数都相同所以查询速度要比B树更稳定

2、B+树天然具备排序功能:B+树所有的叶子节点数据构成了一个有序链表,在查询大小区间的数据时候更方便,数据紧密性很高,缓存的命中率也会比B树高

3、B+树全节点遍历更快:B+树遍历整棵树只需要遍历所有的叶子节点即可,而不需要像B树一样需要对每一层进行遍历,这有利于数据库做全表扫描

4、B树相对于B+树的优点是,如果经常访问的数据离根节点很近,而B树的非叶子节点本身存有关键字和数据,所以在查询这种数据检索的时候会要比B+树快

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

二分法,平衡二叉树、B树、B+树 的相关文章

  • 汽车零配件行业MES规划与落地

    汽车零部件行业作为汽车整车行业的上游 是汽车工业发展的基础 汽车制造业的竞争很大程度上也是其零部件产业水平的竞争 近年来 国内汽车零部件企业通过技术引进 合资合作 自主发展 多元化投资等相关措施 在装备水平 制造技术 产品质量 管理水平等方
  • nextcloud 安装教程 windows 中nextcloud 安装方法

    一 准备工作 1 windows server 中可以用WM 虚拟机 再安装docker 虚拟机磁盘只要20G就够了 云盘数据可以映射到其它盘中 2 在虚拟机中设置好共享文件夹名称为nextcloud 用来存放云盘数据 所以请选一个大一点的

随机推荐

  • 【C++】3、排序算法 C++ 实现

    文章目录 排序算法程序 1 冒泡排序 2 直接插入排序 3 希尔排序 4 快速排序 5 总结 排序算法程序 1 冒泡排序 通过对相邻数据的元素进行交换 逐步将待排序序列排成有序序列的过程 如升序排列 扫描整个待排序序列 非整个序列 不扫描已
  • 关系数据库中表示层级结构

    Managing Hierarchical Data in MySQL What are the options for storing hierarchical data in a relational database Trees in
  • 微信小程序地图导航源码、地图导航小程序源码

    最近研究了微信小程序地图功能 编写了地图导航功能的Demo 文章尾部附有下载地址 1 用户定位功能 用户同意小程序获取位置权限 并定位用户当前位置 2 选择目的地 并开始自动导航功能 2 选择交通工具 显示里程数 及显示相似目的地功能 地图
  • JSP页面分页显示数据

    效果如上图所示 最多显示10条 完整jsp和后台代码如下
  • Meetup回顾

    近期 社区组织了专场线上Meetup 分享了v3 0在2022年的研发路线及开发部署方式 直播间讨论十分热烈 我们把一些开发者们比较关心的问题进行了梳理 整理成这一篇关于v3 0的常见问题和解答 供大家学习参考 Q 目前v3 0性能是多少
  • 动态规划之详解01背包和完全背包

    一 总述 在动态规划中 01背包和完全背包可以说是动态规划最典型的应用了 先介绍一下定义 动态规划 英 Dynamic Programming 简称DP 动态规划是一种多阶段决策最优解模型的思想 如果某 问题有很多重叠 问题 使 动态规划
  • Unity调试真机VS中找不到手机设备

    这个问题困扰了我好几天 网上各种百度没有解决 在VS中 调试 gt 附加 Unity 调试程序 一直找不到AndroidPlayer 最后检查了一下手机的系统版本是10 0 而我电脑中下载的版本缺少10 0的一些配置 Android SDK
  • Eclipse安装FindBugs插件

    上菜 一 FindBugs说明 Findbugs 是一个静态分析工具 它检查类或者 JAR 文件 将字节码与一组缺陷模式进行对比以发现可能的问题 利用这个工具 就可以在不实际运行程序的情况对软件进行分析 它可以帮助改进代码的质量 二 Fin
  • COLA之架构演变(一)

    一 常用架构 1 分层架构 2 CQRS架构 3 六边形架构 4 洋葱圈架构 二 COLA介绍 COLA 是 Clean Object Oriented and Layered Architecture的缩写 代表 整洁面向对象分层架构 目
  • Eclipse中配置Tomcat热部署

    在Eclipse中配置VM参数使Tomcat自动加载部署修改后的项目 如果在第二张图中选择了通过xml文件发布项目则还需要配置在xml中配置文件的信息
  • 什么是七牛云?七牛云的使用

    一 什么是七牛云 七牛云是国内知名的云计算及数据服务提供商 主要提供了现在网络上占据百分之就是打非结构化数据 也就是图片 音频 视频的云存储服务 二 七牛云的使用 1 注册账号 2 绑定邮箱 3 实名认证 必须进行 4 创建一个存储空间 5
  • 高效的学习方法(几个小技巧)

    几个学习小技巧 1 价值导向性学习法 发现 赋予学习内容意义或者使命感 价值导向性学习法是一种高效的思维方式 可以传递出这样的一种观点 学习上有意义 有价值的行为 而不是消极的 被动式的学习 首先 最重要的是赋予学习内容以意义 其次 定制清
  • RK3399 ,64位,Ubuntu16.04系统安装ROS-kinetic方法总结

    1 第一步是修改hosts vi etc hosts 在127 0 0 1 localhost 后边添加 rpdzkj 自己的ubuntu用户名 127 0 0 1 localhost rpdzkj 设置sources list 我选择的是
  • LaTeX公式符号总结(Markdown适用)

    文章目录 1 希腊字母 小写字母 大写字母 2 符号 箭头符号 二元运算符 逻辑符号 集合符号 特殊符号 3 运算和函数 4 矩阵和多行列式 5 括号与空格 6 颜色 字体颜色 背景颜色 RGB颜色和自定义 默认支持颜色 本文从 Typor
  • 开发日记(4)如何将Bitmap转换成Uri?

    1 bitmap to uri Uri uri Uri parse MediaStore Images Media insertImage getContentResolver bitmap null null 2 uri to bitma
  • 阿里:MySQL 单表数据最大不要超过多少行?为什么?

    点击上方 芋道源码 选择 设为星标 管她前浪 还是后浪 能浪的浪 才是好浪 每天 10 33 更新文章 每天掉亿点点头发 源码精品专栏 原创 Java 2021 超神之路 很肝 中文详细注释的开源项目 RPC 框架 Dubbo 源码解析 网
  • 2023AIGC人才趋势洞察报告

    导读 自ChatGPT于2022年11月发布至今 其大大超出预期的 涌现 能力使得AIGC赛道被彻底点燃 从人力资源角度观察 AIGC相关的岗位明显增加的同时 人才对于此类岗位的投递也愈发积极 值得注意的是 AIGC并不单单是属于ICT行业
  • iOS APP 如何做才安全

    本来 写了一篇 iOS 如何做才安全 逆向工程 Reveal IDA Hopper https抓包 等 发现文章有点杂 并且 iOS 如何做才安全 这部分写的越来越多 觉得 分出来更清晰一点 所以拆成两部分 同时也是为了大家能 共同讨论 毕
  • osgEarth加载SXEarth下载的mbtiles地图文件(win10)

    使用晟兴地球 SXEarth 通过互联网下载mbtiles格式的地图文件 然后使用osgEarth加载 晟兴地球 SXEarth 下载地图文件 晟兴地球SXEarth是一款永久免费的3DGIS平台软件 由北京晟兴科技有限公司开发 支持在线G
  • 二分法,平衡二叉树、B树、B+树

    二分法 平衡二叉树 B树 B 树 二分法 二分法查找 算法要求 比较次数 二分法到二叉树 平衡二叉树 平衡二叉树概念 平衡二叉树的构建规则 平衡二叉树特点 B树 B tree B树的构建规则 B树的查询流程 B 树 B 树构建规则 B 树和