B树结点的插入删除操作

骑猪看日落 2023-01-12 11:34 152阅读 0赞

## 引言 ##

公众号原文链接：[2-3树结点的插入删除][2-3] 希望点进去的小伙伴关注一下我的公众号哟，文末有二维码，谢谢！

本文继续介绍B树。上一篇文章 [什么是B-树、B树、B+树、B\*树？][B-_B_B_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结点，如下图中的右图所示。

![图片][45af934f245e5b10f8c9511511978e9f.png]

### **1.2、情况3** ###

往3结点插入一个新结点，由于3结点不能再升级，复杂就复杂在这里。对于这样的情况，需要对结点做拆分（分裂），下面会介绍。

### **1.3、情况3-1** ###

插入新结点5，但是结点6 7已经是3结点了，而正好结点6 7的父亲结点4是个2结点，因此将结点6 7做拆分，然后将元素6上移，如下图所示。

![图片][f98bfd44b83aa04889d81f63a3297582.png]

### **1.4、情况3-2** ###

将新结点11插入到3结点上，与情况3-1不同的是，结点9 10的父亲结点12 14同样也是3结点，因此只能继续往上找，发现结点8是2结点，因此需要对结点9 10和结点12 14都做拆分，如下图所示。

![图片][a4f5324cd63784ef547923e7d6903c0f.png]

### **1.5、情况3-3** ###

插入新结点2，此时结点1 3、结点4 6、结点8 12都是3结点，这就说明当前树的高度已经不能再新增结点了。此时2-3树插入的传播效应会导致根结点进行拆分，树的高度也会增加，如下图所示。

![图片][32df1d14ebf6715c2ee6a156a1cee485.png]

## **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删除后，子树左旋即可，如下图所示。

![图片][919bd4c7cb826ac19eba676bfbf9424e.png]

###    **2.3、情况2-2** ###

该2结点的父亲是2结点，父亲的右孩子也是2结点。

这种情况下，左旋不行，因为构成一颗子树至少要3个结点，因此办法就是，让结点7升级为3结点，那么结点8就得被拉下来，结点9就得被提上去，如下图所示。

![图片][a351691ed1d97635f2ff0f08639314d7.png]

### **2.4、情况2-3** ###

该2结点的父亲是3结点。

这种情况下，需要将父亲结点做拆分，如下图所示。

![图片][63615ff39fd936d53bb02246593b66d1.png]

### **2.5、情况2-4** ###

当前树是满二叉树。

这种情况下，如果不降低树的高度，那么删除该树中的任何一个结点，都无法使它满足B树性质，因此需要降低树高度，如下图所示。

![图片][0052c3421725042683fe2c9ce846219a.png]

### **2.6、情况3-1** ###

删除的分支结点是2结点，所做的调整如下图所示。

![图片][af34936c86e8293e8ded063e4e359039.png]

### **2.7、情况3-2** ###

删除的分支结点是3结点，所做的调整如下图所示。

![图片][f380d1756b1f4eabd38b6fde71184d03.png]

终于讲完了，看完感觉是不是头大，一个插入或删除操作就有这么多情况都要考虑，而且还要涉及到树结构的调整、结点的分裂等，每一种情况都不太好实现。看完本文，心里有个底即可，结合上一篇文章，能对B树的产生背景、基本概念与性质、插入删除的流程有一个清晰的理解，也算是圆满了，至于代码实现，有浓厚兴趣的小伙伴可以实现一下！

## 我的二维码 ##

觉得写得不错的小伙伴，扫码关注一下我的公众号吧，谢谢呀！

![20210121085816775.jpg][]

[2-3]: https://mp.weixin.qq.com/s?__biz=MzI1NTc1MDU3Mw==&mid=2247484822&idx=1&sn=32ec505b44b832aa28963c0c55a986d3&chksm=ea307d54dd47f4421468a19d52ef3cc4b31733f89c0ecb82610c191804a01c2c3e0afb1cb6f7&token=1460364831&lang=zh_CN#rd
[B-_B_B_B]: https://blog.csdn.net/xl_1803/article/details/113327698
[45af934f245e5b10f8c9511511978e9f.png]: /images/20221119/680d0992a7644166b0a1a0661b8efa0c.png
[f98bfd44b83aa04889d81f63a3297582.png]: /images/20221119/49efc167b9224eb99248b97d29bc7ee6.png
[a4f5324cd63784ef547923e7d6903c0f.png]: /images/20221119/b7a87c97240442b899dca698f51a4e3b.png
[32df1d14ebf6715c2ee6a156a1cee485.png]: /images/20221119/e24eab160054480dae361604f69322ee.png
[919bd4c7cb826ac19eba676bfbf9424e.png]: /images/20221119/6e4183b261e84f5080ad85d9e689bb53.png
[a351691ed1d97635f2ff0f08639314d7.png]: /images/20221119/ee2d728d810b4d44844e89a694e4fcca.png
[63615ff39fd936d53bb02246593b66d1.png]: /images/20221119/9d444085415e457193e7e5e609ed505c.png
[0052c3421725042683fe2c9ce846219a.png]: /images/20221119/73c61416fa94443c8a5bda3e168e35c9.png
[af34936c86e8293e8ded063e4e359039.png]: /images/20221119/660e126b04e740658d042237d7fc6ada.png
[f380d1756b1f4eabd38b6fde71184d03.png]: /images/20221119/f411cedc51d74ab3a395bea8a0b99852.png
[20210121085816775.jpg]: /images/20221119/828dadc11001441ba7fa58a9ab2b1851.png