时间:2021-05-25
上文我们介绍了B-树的插入过程,本文我们来介绍B-树的删除过程。
在B-树中删除节点时,可能会发生向兄弟节点借元素,和孩子节点交换元素,甚至节点合并的过程。
我们以下面的树为基础,进行删除操作。
首先明确一下这个树的定义。它是一个5阶树。所以,每个节点内元素个数为2~4个。
我们依次删除8、16、15、4这4个元素。
首先删除8,因为删除8后,不破坏树的性质,所以直接删除即可。得到如下
然后删除16,这导致该节点只剩下一个13节点,不满足节点内元素个数为2~4个的要求了。所以需要调整。这里可以向孩子借节点,把17提升上来即可,得到下图。这里不能和兄弟节点借节点,因为从3,6节点中把6借走后,剩下的3也不满要求了。另外,也不能把孩子中的15提升上来,那样会导致剩下的14不满足要求。
然后删除15,删除15后同样需要调整。调整的方式是,18上升,17下降到原来15的位置,得到下图。
然后删除元素4,删除4后该节点只剩下5,需要调整。可是它的兄弟节点也都没有多余的节点可借,所以需要进行节点合并。节点合并时,方式会有多种,我们选择其中的一种即可。这里,我们选择父节点中的3下沉,和1,2,以及5进行合并,如下图。
但这次调整,导致6不符合要求了。另外,6非根节点,但只有2个孩子,也不符合要求。需要继续调整。调整的方式是,将10下沉,和6,以及13,18合并为根节点,如下图。
结束。
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对的支持。如果你想了解更多相关内容请查看下面相关链接
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
上文我们介绍了B-树的性质,本文我们来介绍一下B-树的插入过程。插入过程和树的构建过程本质是一致的,即都是进行插入操作,并对插入后的B-树进行调整。我们设定B-
B-树是一种常见的数据结构。和他一起的还有B+树。在这里,需要澄清一下概念。B树,B-树,B+树有什么区别?他们有什么关系呢?其实,从数据结构来讲只有2种,也就
本文内容B-树(B-tree)散列(Hash)k-d树(k-dtree)点四叉树(PointQuadtree)本文介绍关于Oracle索引的结构。大概了解Ora
本文实例讲述了jQuery删除一个元素后淡出效果展示删除过程的方法。分享给大家供大家参考。具体分析如下:当我们删除一个元素时希望能看到删除的过程,这个效果通过对
本文实例讲述了C#实现安全删除文件目录的方法。分享给大家供大家参考。具体分析如下:1.创建文件夹(简单,没多考虑)2.删除所建文件夹:为防止删除过程中有其他进程