看图轻松理解数据结构与算法系列(B树的删除)

作者:超人汪小建(seaboat)

出处:https://blog.csdn.net/wangyangzhizhou/column/info/25184/2


删除操作

删除操作比较复杂,主要是因为删除的项可能在叶子节点上也可能在非叶子节点上,而且删除后可能导致不符合B树的规定,这里暂且称之为导致B树不平衡,于是要进行一些合并、左旋、右旋等操作,使之符合B树的规定(即让B树平衡)。另外,如果是删除非叶子节点项需要先找到中序前驱来替换。

情况一

要删除的项在叶子节点上且不影响B树的平衡结构,比如删除“I”,从根节点开始查找,“I”大于“D”,往第二个分支,

image

逐一与节点内项的值进行比较,“I”大于“F”,继续比较,“I”大于“H”继续比较,“I”小于“K”,所以往第三个分支继续往下查找,

image

此时找到“I”,

image

直接删除“I”,完成删除操作。

image

情况二

要删除的项在叶子节点上,删除后打破平衡需要从右兄弟节点中借项,而且右兄弟节点有足够的项借给它。比如删除“G”,从根节点开始查找,“G”大于“D”,往右子树,

image

逐一比较节点内项的值,发现应该往第二个分支,

image

找到“G”,

image

此时发现“G”节点的右兄弟节点有项可以借给它,于是删除“G”,然后进行左旋操作,左旋即原来的父节点“H”下移到左子节点填补原来的“G”节点,右子节点中最小值的项“I”提升到父节点,最终如下,

image

完成删除操作。

image

情况三

要删除的项在叶子节点上,删除后打破平衡需要从左兄弟节点中借项,而且左兄弟节点有足够的项借给它。比如删除“L”,从根节点开始查找,“L”大于“D”,往右子树,

image

逐一比较节点内项的值,发现应该往第四个分支,

image

找到“L”,

image

此时发现“L”节点的左兄弟节点有项可以借给它,于是删除“L”,然后进行右旋,右旋即原来的父节点“K”下移到右子节点填补原来的“L”节点,左子节点中最大值的项“J”提升到父节点,最终如下,

image

完成删除操作。

image

情况四

要删除的项在叶子节点上,删除后打破平衡,而且左右兄弟节点都没有项可以借给它。比如删除“G”,从根节点开始查找,“G”大于“D”,往右子树,

image

逐一比较节点内项的值,发现应该往第二个分支,

image

找到“G”,

image

此时发现“G”节点删除掉后,左右兄弟节点都无法借项给它,执行合并操作,

image

合并操作主要是将父节点对应的项“F”下移到左子节点中,同时也将右子节点中剩余的项全部也移到左子节点中(注意这里右子节点删除“G”项后已无其他项),最终结果如下,完成删除操作。

image

需要注意的是如果执行合并操作后使父节点不平衡,则需要继续对父节点继续进行平衡处理。比如下面的例子,需要删除“C”项,从根节点开始于“D”比较,小于“D”则往往第一个分支,

image

逐一与子节点内的项比较,“C”大于“B”则往第二个分支,

image

找到“C”,

image

此时发现“C”项删除掉后,左右兄弟节点都无法借项给它,

image

执行合并操作,将父节点对应的项“B”下移到左子节点中,同时也将右子节点中剩余的项全部也移到左子节点中,合并后结果如下,父节点已经变成空了,树不平衡,

image

此时父节点的右兄弟节点可以借项给它,即执行左旋操作,父节点的父节点“D”下移到父节点,父节点的兄弟节点的最左边项“F”上升,

image

另外,左旋操作还包括要将移动项“F”对应节点的第一个分支(即“E”)移到父节点“D”的最右分支,最终结果如下,

image

情况五

要删除的项在非叶子节点上。比如删除“M”,从根节点开始查找,“M”大于“H”,往第二个分支,

image

逐一比较子节点内的项,找到“M”,

image

非叶子节点项的删除的第一步就是要先找到对应的中序前驱,即第一个分支子节点中最大值的项,

image

然后一直往最后一个分支找,最终找到“L”为前驱,将其提升到待删除项“M”的位置,导致了树不平衡,但它发现兄弟节点可以借项给它,

image

于是进行右旋操作,父节点“K”下移到原来前驱的位置,左兄弟节点最右边的项“J”提升到父节点,另外如果左兄弟节点“J”项有右子节点的话,也需要挂到“K”节点的左边。最终完成删除操作。

image

除此之外,再看看删除根节点的情况,删除只有一个项的根节点,比如删除“D”,

image

先找中序前驱,即第一个分支子节点中最大值的项,

image

一直往最后一个分支找,最终找到“C”为前驱,将其提升到根节点中,

image

此时引起不平衡,而且原来“C”节点的左右兄弟节点都无法借项给它,

image

此时只能做合并处理,将父节点的项“B”下移到左子节点,合并后原来的父节点变为空,产生了不平衡,此时它的兄弟节点可以借项给它,所以需要执行左旋操作,

image

左旋即将“C”下移,“F”提升,

image

而且还要将“E”项挂到“C”节点上,最终如下。

image

赞(0) 打赏

如未加特殊说明,此网站文章均为原创,转载必须注明出处。Java 技术驿站 » 看图轻松理解数据结构与算法系列(B树的删除)
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注【Java 技术驿站】公众号,每天早上 8:10 为你推送一篇技术文章

扫描二维码关注我!


关注【Java 技术驿站】公众号 回复 “VIP”,获取 VIP 地址永久关闭弹出窗口

免费获取资源

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏