7.4.1.4 B 树的删除

教材导航 · 第7章

原书定位

印刷页P313起,对应PDF第325页。下文为目视整理的知识提要;完整内容见原书对照。

内部关键字可用前驱或后继替换,将实际删除转移到终端实际结点。删除后若不少于 t−1t-1 个关键字即可结束,否则处理下溢:

  • 相邻兄弟有富余:经父结点借位,父的分隔关键字下移、兄弟的一端关键字上移;有孩子时也迁移相应指针。
  • 兄弟无富余:将当前结点、父的分隔关键字和相邻兄弟合并,父关键字减少,可能继续向上调整。

根减为空且有一个实际孩子时,由孩子成为新根,树高降低 1。删除不一定都要合并,也不一定改变树高。

删除内部关键字的前驱替换

删除内部关键字的前驱替换,原书P313。

B 树删除的借位与合并

B 树删除的借位与合并,原书P313。

对应练习

7.4 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P313,PDF第325页

原书对照,原书P314,PDF第326页