B树——插入和删除
B树——插入和删除
B树的插入
5阶B数——结点关键字个数向上取整m/2-1≤n≤m-1
即2≤n≤4
连续插入5个元素后，超出来了。
在插入key后，若导致原结点关键字数超过上限，则从中间位置（m/2向上取整）将其中的关键字分为两个部分，左部分包含的关键字放在原结点中，右部分包含的关键字放在新节点中，中间位置（m/2向上取整）的结点插入原结点的父节点
新元素一定是插入到最底层“终端结点”，用“查找”来确定插入位置
在插入key后，若导致原结点关键字数超过上限，则从中间位置（m/2向上取整）将其中的关键字分为两个部分，左部分包含的关键字放在原结点中，右部分包含的关键字放在新节点中，中间位置（m/2向上取整）的结点插入原结点的父节点，again
若此时导致其父节点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根节点为止，进而导致B树高度增1
核心要求：
①对m阶B树——除根节点外，结点关键字个数m/2向上取整-1≤n≤m-1
②子树0＜关键字1小于子树1＜关键字2＜子树2＜。。
新元素一定是插入到最底层“终端结点”，用“查找”来确定插入位置
在插入key后，若导致原结点关键字数超过上限，则从中间位置（m/2向上取整）将其中的关键字分为两个部分，左部分包含的关键字放在原结点中，右部分包含的关键字放在新节点中，中间位置（m/2向上取整）的结点插入原结点的父节点。若此时导致其父节点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根节点为止，进而导致B树高度增1
B树的删除
删除60
若被删除关键字在终端节点，则直接删除该关键字（要注意节点关键字个数是否低于下限m/2向上取整-1）
删除80
找直接前驱后者直接后继
若被删除关键字在非终端节点，则用直接前驱后直接后继替代被删除的关键字
直接前驱：当前关键字左侧指针 所指子树中“最右下”的元素
直接后继：当前关键字右侧指针 所指子树中“最左下”的元素
对非终端节点关键字的删除，必然可以转化为对终端节点的删除操作
低于关键字数下限
删除38
若被删除关键字所在节点删除前的关键字个数低于下限，且与此节点右（或左）兄弟节点的关键字个数还很宽裕，则需要调整该节点、右（或左）兄弟节点及其双亲结点（父子换位法）
其实就是在左右兄弟还很宽裕的时候，用当前结点的前驱（后继）、前驱的前驱（后继的后继）来填补空缺
删除90
左兄弟富裕，借下来
本质：永远保证子树0＜关键字1小于子树1＜关键字2＜子树2＜。。
删除49
兄弟不够借？
若被删除关键字所在结点删除前的关键字个数低于下限，且此时与该结点相邻的左、右兄弟结点的关键字个数均=m/2向上取整-1，则将关键字删除后与左（或右）兄弟节点及双亲结点中的关键字进行合并
但是73这个位置又不够关键字了。。。
把父节点的扒下来
知识回顾
5阶
最新文章
- GJM ：Unity 使用SqlServer数据库 [原创]
- php中的curl使用入门教程和常见用法实例
- 来自苹果的编程语言——Swift简介转载】
- archlinux 安装mysql-workbench
- adb uninstall
- nopcommerce3.3简洁版
- python (10) 文件夹的创建与文件夹的删除
- C# DataGridView的列对象属性探讨 (未完待续)
- 侯捷C++ Type traits（类型萃取
- Yii2 灵活加载js、css
- beta版本复审
- SQL Server 实现递归查询
- log4j2.yml配置文件
- wap2app（五）-- 微信授权登录以及踩过的坑
- shell脚本介绍 shell脚本结构和执行 date命令用法 shell脚本中的变量
- Redis 实现问题
- Net Core 使用外部登陆提供程序登陆的流程，以及身份认证的流程
- 控制台console对象常用的一些方法
- 每天一个linux命令(5)：in命令
- sqlite的一个Unable to Open database file的坑爹错误