B树的删除操作,五种情况图解

2018年9月11日10:35:30数据结构与算法评论18,064 views31字数 1859阅读模式

删除操作

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

情况一

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

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

此时找到“I”,

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

情况二

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

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

找到“G”,

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

完成删除操作。

B树的删除操作,五种情况图解

情况三

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

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

找到“L”,

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

完成删除操作。

B树的删除操作,五种情况图解

情况四

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

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

找到“G”,

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

找到“C”,

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

情况五

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

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

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

B树的删除操作,五种情况图解

作者:超人汪小建
链接:https://juejin.im/post/5b95ba52f265da0af87952a9
来源:掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/4547.html
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定