从零开始学数据结构系列之第五章《B树的删除》-EW帮帮网

删除操作是指，根据key删除记录，如果B树中的记录中不存对应key的记录，则删除失败。

1）如果当前需要删除的key位于非叶子结点上，则用后继key（这里的后继key均指后继记录的意思）覆盖要删除的key，然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上，这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步

2）该结点key个数大于等于Math.ceil(m/2)-1，结束删除操作，否则执行第3步。

3）如果兄弟结点key个数大于Math.ceil(m/2)-1，则父结点中的key下移到该结点，兄弟结点中的一个key上移，删除操作结束。

否则，将父结点中的key下移与当前结点及它的兄弟结点中的key合并，形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针，指向这个新结点。然后当前结点的指针指向父结点，重复上第2步。

有些结点它可能即有左兄弟，又有右兄弟，那么我们任意选择一个兄弟结点进行操作即可。

相比于插入，我们B树的删除就比较难理解了，总的来说我们分成3种情况

情况1

叶子结点的个数正好>最小值，直接删

这种就是最简单的删除方式了，因为待删除的节点中有足够的范围让自己去删除，所以就不用顾及那么多

我们直接看案例，注意案例都是五阶B树，区间是2-4

在这里插入图片描述
上面的B树中删除21，删除后结点中的关键字个数仍然大于等2，所以直接删除就行了。

原始状态
在这里插入图片描述

上面的B树中删除18，删除后结点中的关键字个数仍然大于等2，所以直接删除就行了。
在这里插入图片描述

叶子结点的个数正好=最小值，先去借，借不到就合并

原图：
在这里插入图片描述
上面的B树中删除14，删除后结点中的关键字个数小于2，所以此时我们应该去找兄弟去借（如果兄弟有的话）

那问题是，我们要怎么借？
在这里插入图片描述

我们先看左边能不能借，发现如果向左边去借的话，那么左边兄弟子树也是不满足区间的（借了的话左边兄弟还剩一个，也不满足定义），那我们看看右边子树能不能借，发现右边子树是能去借的（右边子树借了之后还是满足再区间内的【2-4】个）

那重点来了，我们要借的方式是什么？

1. 将他的父亲节点先借给他，将15移下来

在这里插入图片描述
2.之后再把它旁边的兄弟移上去
那这样的话就是我们借的方式了

样例2：

在这里插入图片描述
这是一个三阶子树，他的区间范围是【1-2】

所以如果我们要删除60.则要先把它父亲先借下来，之后再将它兄弟移上去就行了

也就是先删除 60 这个节点，然后再把父亲 80 这个节点再移动到原本被删除的位置，然后再将它兄弟节点 90 这个节点移回它付清这个节点

☁️ 以上就是所有内容，对大家有用的话点个关注！感谢大家！