7.4.1.4 B 树的删除
原书定位
印刷页P313起,对应PDF第325页。下文为目视整理的知识提要;完整内容见原书对照。
内部关键字可用前驱或后继替换,将实际删除转移到终端实际结点。删除后若不少于 个关键字即可结束,否则处理下溢:
- 相邻兄弟有富余:经父结点借位,父的分隔关键字下移、兄弟的一端关键字上移;有孩子时也迁移相应指针。
- 兄弟无富余:将当前结点、父的分隔关键字和相邻兄弟合并,父关键字减少,可能继续向上调整。
根减为空且有一个实际孩子时,由孩子成为新根,树高降低 1。删除不一定都要合并,也不一定改变树高。

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

B 树删除的借位与合并,原书P313。
对应练习
关联知识
原书对照
展开原书对照截图

