本文共 1781 字，大约阅读时间需要 5 分钟。
引言
公众号原文链接： 希望点进去的小伙伴关注一下我的公众号哟，文末有二维码，谢谢！
本文继续介绍B树。上一篇文章 中介绍了B树结点的查找过程，本文将介绍B树结点增删过程。
首先介绍B树的两种特殊形式：
-
2-3树：3阶B树，只能有2结点和3结点（结点的孩子数为2称之为2结点，以此类推）
-
2-3-4树：4阶B树，只能有2结点、3结点和4结点
既然它们是B树，那么它们一定满足B树的所有性质。
下面我通过2-3树，来描述一下B树结点的插入删除过程。
我会频繁用结点n和n结点这样的词，比如结点2和2结点，事先解释一下，结点2表示该结点的元素值为2，2结点表示该结点的孩子数为2。
1、2-3树的结点插入
2-3树结点的插入与二叉查找树类似，都是将新结点当做叶子结点去插入的，但是与二叉查找树不同的是，2-3树插入新结点后会对该树的其余结构产生连锁反应。
2-3树的插入如下几种情况：
情况1：空树：对于空树，插入一个2结点即可(简单)
情况2：新结点插入到一个是2结点的叶子结点上(一般)
情况3：新结点插入到一个是3结点的叶子结点上(复杂)
情况3-1
情况3-2
情况3-3
1.1、情况2
将新结点插入到一个是2结点的叶子上，只需要将2结点升级为3结点即可。
如下图中的左图所示，在B树上插入新结点3，那么新结点3只能当做结点1的右孩子，但是这样会破坏B树性质（所有叶子结点在同一层），因此只能将结点1升级为3结点，如下图中的右图所示。
1.2、情况3
往3结点插入一个新结点，由于3结点不能再升级，复杂就复杂在这里。对于这样的情况，需要对结点做拆分（分裂），下面会介绍。
1.3、情况3-1
插入新结点5，但是结点6 7已经是3结点了，而正好结点6 7的父亲结点4是个2结点，因此将结点6 7做拆分，然后将元素6上移，如下图所示。
1.4、情况3-2
将新结点11插入到3结点上，与情况3-1不同的是，结点9 10的父亲结点12 14同样也是3结点，因此只能继续往上找，发现结点8是2结点，因此需要对结点9 10和结点12 14都做拆分，如下图所示。
1.5、情况3-3
插入新结点2，此时结点1 3、结点4 6、结点8 12都是3结点，这就说明当前树的高度已经不能再新增结点了。此时2-3树插入的传播效应会导致根结点进行拆分，树的高度也会增加，如下图所示。
2、2-3树的结点删除
2-3树的结点删除分如下几种情况：
情况1：删除元素位于是3结点的叶子结点上：将3结点降级为2结点即可
情况2：删除的元素位于是2结点的叶子结点上
情况2-1
情况2-2
情况2-3
情况2-4
情况3：删除的元素位于分支结点上
情况3-1：分支结点是2结点
情况3-2：分支结点是3结点
2.1、情况2
虽然删除的元素位于是2结点的叶子结点上，理论上直接将该2结点删除即可，但该2结点的父亲结点少了一个孩子，此时肯定不满足B树的性质了，因此需要做特殊处理。
2.2、情况2-1
该2结点的父亲是2结点，父亲的右孩子是3结点。
这种情况下，将结点1删除后，子树左旋即可，如下图所示。
2.3、情况2-2
该2结点的父亲是2结点，父亲的右孩子也是2结点。
这种情况下，左旋不行，因为构成一颗子树至少要3个结点，因此办法就是，让结点7升级为3结点，那么结点8就得被拉下来，结点9就得被提上去，如下图所示。
2.4、情况2-3
该2结点的父亲是3结点。
这种情况下，需要将父亲结点做拆分，如下图所示。
2.5、情况2-4
当前树是满二叉树。
这种情况下，如果不降低树的高度，那么删除该树中的任何一个结点，都无法使它满足B树性质，因此需要降低树高度，如下图所示。
2.6、情况3-1
删除的分支结点是2结点，所做的调整如下图所示。
2.7、情况3-2
删除的分支结点是3结点，所做的调整如下图所示。
终于讲完了，看完感觉是不是头大，一个插入或删除操作就有这么多情况都要考虑，而且还要涉及到树结构的调整、结点的分裂等，每一种情况都不太好实现。看完本文，心里有个底即可，结合上一篇文章，能对B树的产生背景、基本概念与性质、插入删除的流程有一个清晰的理解，也算是圆满了，至于代码实现，有浓厚兴趣的小伙伴可以实现一下！
我的二维码
觉得写得不错的小伙伴，扫码关注一下我的公众号吧，谢谢呀！
转载地址：https://blog.csdn.net/xl_1803/article/details/113329882 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
