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

数据结构 -- B树和B+树

B树

B树

5叉查找树

最少1个关键字,2个分叉

最多4个关键字,5个分叉

如何保证查找效率

(1)eg.对于5叉排序树,规定除了根节点外,任意结点都至少有3个分叉,2个关键字

(若每个结点内关键字太少,导致树变高,要查找更多层结点,效率低)

【策略】

m叉查找树中,规定除了根结点外,任何结点至少有[m/2]个分叉,即至少含有[m/2]-1个关键字

为什么要除了根结点之外?

当树中只有一个结点时,没有办法保证

(2)不够“平衡”,树很高,有很多层节点

【策略】

m叉查找树中,规定对于任何一个结点,其所有子树的高度都要相同

满足这两点策略要求的树即为B树

在这里插入图片描述

B树,又称多路平衡查找树,B树中所被允许的孩子个数的最大值称为B树的阶,通常用m表示。一颗m阶的B树或为空树,或为满足以下特性的m叉树:

①树中每个结点至多有m棵子树,至多含有m-1个关键字

②若根结点不是终端结点,则至少有两棵子树

③除根结点外的所有非叶子节点至少有[m/2]个分叉,即至少含有[m/2]-1个关键字

⑤所有的叶子结点都出现在同一层,并且不带信息(可以视为外部结点或者类似于折半查找判定树的查找失败结点,实际上这些结点不存在,指向这些结点的指针为空)

④所有非叶子节点的结构如下:

在这里插入图片描述

大部分学校算B树的高度不包括叶子结点(失败结点)

问题:含n个关键字的m阶B树,最小高度、最大高度是多少?

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

B树的插入

B树的插入

在插入key后,若导致原结点的关键字字数超出上限,则从中间位置([m/2])将其的关键字分为两部分,左部分包含的关键字放在原结点中,右部分包含的关键字放到新结点中,中间位置([m/2])的结点插入原结点的父结点

新元素一定是插入到最底层“终端结点”,通过“查找”来确定插入位置

叶子结点必须在同一层

B树的删除

若被删除关键字在非终端节点,则用直接前驱或后继来替代被删除的关键字

直接前驱:当前关键字左侧指针所指子树“最右下”的元素

直接后继:当前关键字右侧指针所指子树“最左下”的元素

若删除关键字在非终端节点,则用直接前驱或直接后继来替代被删除的关键字

删除后关键字数量不低于下限:直接删除

删除后关键字数量低于下限:兄弟够借,用当前节点的后继(前驱)、后继的后继(前驱的前驱)来填补空缺

在这里插入图片描述

删除后关键字数量低于下限:兄弟不够借,若被删除关键字所在结点删除前的关键字个数低于下限,且此时与该结点相邻的左右兄弟结点的关键字个数均=[m/2]-1,则将关键字删除后与左(或右)兄弟结点以及双亲结点中的关键字进行合并

在这里插入图片描述

B+树

定义

在这里插入图片描述

一棵m阶的B+树需要满足以下条件
①每个分支结点最多有m棵子树

②非叶根结点至少有两棵子树,其他每个分支节点至少有[m/2]棵子树

③结点子树个数与关键字个数相等

④所有的叶结点包含全部关键字及指向对应记录的指针,叶结点中将关键字按大小排序,并且相邻叶结点按大小顺序相互连接起来

⑤所有分支结点中仅包含它的各个子节点中关键字的最大值以及指向其子节点的指针

B+树的查找

多路查找:无论查找成功与否,都要找到最后一层结点

顺序查找:直接通过指针p在叶子层进行查找

B+树 VS B树

m阶B+树:

B+树B树
结点中的n个关键字对应子树个数nn+1
结点内关键字个数最多有m个结点,除根结点外,其他每个分支节点至少有[m/2]棵子树最多有m-1个结点,除根结点外,其他每个分支节点至少有[m/2]棵子树
关键字叶结点包含全部关键字,非叶子结点中出现过的关键字也会在叶结点中出现哥结点包含的关键字是不重复的
查找操作叶结点包含信息,所有非叶结点仅起到索引作用,非叶结点的每个索引项只含有对应子树的最大关键字和指向该子树的指针,不会有该关键字对应记录的存储地址结点都包含了关键字对应记录的存储地址

在这里插入图片描述

http://www.xdnf.cn/news/7984.html

相关文章:

  • 插值算法 - 图像缩放插值QT
  • 容器化与云原生安全
  • 深入剖析 5G 核心网中的 PLMN
  • 青少年编程与数学 02-020 C#程序设计基础 01课题、C#编程概要
  • launch 在Kotlin 中怎么使用
  • [Vue]路径跳转和路由高级设置
  • SC3000智能相机-自动存图
  • java后端-海外登录(谷歌/FaceBook)
  • Appium+python自动化(二)- 环境搭建—下
  • Go 语言中的 Struct Tag 的用法详解
  • mysql可重复读隔离级别下的快照读和当前读
  • leetcode 148. Sort List
  • 力扣-无重复字符的最长子串
  • Golang 内存模型小结
  • Qt 最新版6.9.0使用MQTT连接腾讯云详细教程
  • window 显示驱动开发-视频内存供应和回收(一)
  • jquery.table2excel方法导出
  • 鸿蒙仓颉开发语言实战教程:实现商城应用首页
  • 尼科彻斯定理
  • Vue 3.0中自定义指令
  • 01-jenkins学习之旅-window-下载-安装
  • 【云原生安全】零信任与机密计算
  • Qt C++实现马的遍历问题
  • 【JavaEE】(1) 计算机如何工作
  • 阿里巴巴 MCP 分布式落地实践:快速转换 HSF 到 MCP server
  • 记录:uniapp 上线部署到微信小程序vendorjs包过大的问题
  • 外网如何连接内网中的mysql数据库服务器?简单网络工具方案
  • Cause: org.apache.ibatis.ognl.OgnlException: sqlSegment
  • 【C++】位图+布隆过滤器
  • JAVA EE(进阶)_CSS