数据结构和算法-B树的插入和删除

2023-12-31 14:47:46

文章目录

B树的插入

首先将根节点的关键字个数填满，填满后再分开成树
在这里插入图片描述
分开的规则
在这里插入图片描述
此时插入90，从根节点依次查找，然后插入到终端节点的关键字中
在这里插入图片描述
插入同上，注意此时在终端节点插入要符合终端节点的大小顺序
在这里插入图片描述

此时插入88，插入到终端节点后，发现99溢出，再次按规则分开成树
在这里插入图片描述
分开结果
在这里插入图片描述
再插入83和87
在这里插入图片描述
再插入80，此时溢出，再次分开成树
在这里插入图片描述
分开成的父节点作为原父节点的关键字
在这里插入图片描述
再次插入92，93，94，此时终端节点关键字个数溢出
在这里插入图片描述
分开成树
在这里插入图片描述
再次插入73，74，75，插入后溢出
在这里插入图片描述
再次分开成树，此时又发现原父节点满的
在这里插入图片描述
对原父节点进行分开成树

在这里插入图片描述

小结

在这里插入图片描述

B树的删除

此时删除60
在这里插入图片描述
直接删除关键字即可，然后注意终端节点的关键字个数是否合法
在这里插入图片描述
此时删除80，可以用直接前驱或者直接后继替代。这里找到直接前驱77
在这里插入图片描述
将77替代为删除的节点
在这里插入图片描述
此时删除77，找到直接后继82
在这里插入图片描述
将82替代
在这里插入图片描述
此时删除38，发现该节点的关键字个数低于下限
在这里插入图片描述
将49移下去，70移动上去 在这里插入图片描述
此时删除90
在这里插入图片描述
此时将88移下去，87移上去
在这里插入图片描述
此时删除49，发现节点关键子个数小于下限
在这里插入图片描述
此时将右兄弟（71 72）的和原父节点的对于关键字（70）合并
在这里插入图片描述
此时73所在的节点的关键字个数少于小限，将其与双亲结点和兄弟节点合并，此时根节点为零个关键字，那么可以删除
在这里插入图片描述

小结

在这里插入图片描述

文章来源:https://blog.csdn.net/llovewuzhengzi/article/details/135308416
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。