331-B_树的删除过程

以你之姓@ 2022-10-05 04:49 131阅读 0赞

## B\_树的删除过程 ##

**根据上一节画的B树**  
**构造如下**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
**那么我们该如何删除呢？**  
可以分为如下情况：  
**一种是分枝结点一种是叶子结点。**

**1、如果删除o结点**，我们得寻找o（o在1下标位置）的直接前驱或者直接后继来替代它，直接前驱就是o的位置（1下标）,1-1=0号下标，0下标的s的最右边结点（也就是0的左孩子的最右边结点）n，直接后继就是o的右孩子的最左边的结点q，我们应该拿n去替代，好处是l,m,n分别在1,2，3号位置，拿n替换之后，数据不需要移动！！！  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]  
我们把删除统一到叶节点的删除  
我们把n替换o  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]  
我们变相地是对n删除，把个数3减为2。  
如果我们现在要删除n了，找到它的直接前驱m，但是个数是2，我们找直接后继，如果后继的数据是3，就可以把q覆盖n，然后进行数据的移动，个数减1，为什么是先左后右，就是左边不用移动数据！  
**对分枝结点的删除，都是去找它的直接前驱或者直接后继，变成对叶子的删除！**

**2、如果我们要删除j，结点的元素个数变为1个，我们的5阶B-树的要求是  
最小元素个数是2，最大不超过4个，如果把j删除，这个结点就不符合要求了！如果我们要删除j，下一个动作是什么？**  
先借后并！  
借，先左，找到这个结点的左兄弟，然后找这个结点的右兄弟，  
如果这个结点的左兄弟元素个数大于2，就把h放下来和i作伴，g放上去，但是这个结点的元素个数不大于2。但是这个结点的右兄弟的元素个数是3，大于2，把k放下来和i作伴，把l放上去。然后把m,n向左移动。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]  
**借的时候有2种旋转，一种是和左边借，一种是和右边借  
跟左兄弟借后，左兄弟的元素个数要大于MINITEM！！！**  
**左边借不了，从右边借，但是元素个数都是要大于MINITEM！！！**

**3、如果我们把k删除，先左后右借，但是左右边都是2个元素，都不够了。只能合并！**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]  
现在是左右边借不了，只能先左后右进行合并，如果有左兄弟，就和左兄弟合并，如果没有就和右兄弟合并。  
和左兄弟怎么合并？  
我们把h放到g后面的3号位置，把i移动到4号位置，中间结点的元素个数为0，进行free掉，把l移动1号位置，把s3指针移动到s2指针，2数据3分枝。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]  
如果我们现在删除i,h,，都不用做什么，因为个数大于2。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 7]  
如果我们还要删除g，那么先向左兄弟借，左边有4个元素，把f后移，把e放下来和f作伴，把d移动上去。右旋转。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 8]

我们接着把f删除，向左兄弟借，e后移，把d放下来和e作伴，把c放上去。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 9]  
我们要删除e，先左后右，兄弟们的元素个数都不够啊！借不了，和左边合并。  
把c合并进去，把d合并进去，free这个结点，l放到1号位置，指针也前移，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 10]  
但是当前只有1个元素，也小于2了。它没有左兄弟，有右兄弟，3个元素，可以去借，把o放下来和l作伴，把r放上去。把p,q移动过来，拿o的右边指向，u,x左移，其三个孩子也左移。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 11]  
我们再接着删除d,c,不用做什么。  
我们要删除b了，对于这个结点，个数小于2了，但是没有左兄弟，有右兄弟，和右兄弟借了。但是右兄弟只有2个元素，不能借，只能和右兄弟合并，把l放下来和a作伴，把m,n放到a这个结点里面，然后free这个空节点了。o左移，指针左移，1数据2分枝，但是 不是根节点，这个分枝结点只有1个元素。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 12]  
这个分枝结点没有左兄弟，有右兄弟，但是其元素个数是2，没有得借，只能和右兄弟合并，把r放下来和o作伴，把u,x移动到o这个结点里面，把3个指针也弄进来，free掉这个空节点和空头结点，新根出现了  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 13]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 14]  
此时我们删除n,m，不用做什么  
然后我们删除l，和右孩子合并。  
把p,q移过来，删除空节点，r,u,x和3个孩子指针依次左移。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 15]  
我们接着删除q,p，不用做什么  
然后我们删除t，要借数据，两边都借不了，先左后右合并，把r放下来和a,o作伴，把s也左移和a,o作伴，free这个空节点，u,x左移，孩子也左移。2数据3分枝。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 16]  
我们删除s,r,  
我们删除z，没有右兄弟，有左兄弟，借不了，和左兄弟合并，把x放下来和v,w作伴，把y左移和v,w作伴，free这个空节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 17]  
我们删除y,x,w，没有办法借了，把u合并到a,o这个结点，把v放过去，free这个空节点和空头结点  
![在这里插入图片描述][20210606195840868.png_pic_center]  
现在这个结点既是根节点又是叶子节点。删除v,u,o都没问题，对于根节点，可以有1个元素，当我们删除a，这个根节点也空了，释放这个根节点，为空了。

## B树浪费空间 ##

**对于叶子结点，sub指针用不到。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 18]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221005/ab0669f0b1f441e29c2d9b71b1d451f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221005/5347e2dc68074dbbaa3740cda5950171.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221005/34e15c211eb54cfcb549a75fabba05bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221005/80f76c08fe43424eb6e6e4b5a3726eaa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221005/178b2bcac4794a48a6836a68e15777f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221005/30ea7835180949cf8bc3227b918c4243.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221005/c70b33d719984947ad954d18fe1222e4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221005/8e07b56d97364b19a282acf1b9cf5318.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221005/5539fd3075a14f21a337065f8c66d3b1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221005/5a0b2cda9fc044138668ba1351113c26.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221005/f047c5b8dab44637af0d91a49b0bcbed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221005/de0dff73dbed4c45b0437a8058242a08.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 12]: /images/20221005/ad06c62241984120982d97d1ef53e186.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 13]: /images/20221005/70fef9762c0e49dfafc5c22c6384c7d0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 14]: /images/20221005/4fdc8db417fc4103a663e8eb4a61d7f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 15]: /images/20221005/a755f4aad5154e868b15cedd7d755f54.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 16]: /images/20221005/299a44a925224859961d9fc9f9f80218.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 17]: /images/20221005/bab50f387a7e4107a67a62b3cbf155c4.png
[20210606195840868.png_pic_center]: /images/20221005/ae2f1c52008448ceab8e0b9edfd198eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 18]: /images/20221005/09cbe3fb848442eeb61605bf89727336.png