B 树删除与调整规则全题型秒杀笔记
【学长导读】 B 树的删除与下溢调整是 408 数据结构查找章节的核心重难点。命题人最喜欢考“删除某个非叶结点关键字后,根结点/叶结点可能或不可能变成什么样”。 做对这类题不需要死背冗长的课本定义,只需掌握 “1 条生死线 + 2 个替身 + 3 种填坑动作”,考场上 20 秒即可稳拿满分!
模块一:B 树核心规则与“生死线”速算(必背前提)
做任何 B 树插入/删除题之前,第一步永远是先看阶数 ,算出每个结点最少和最多能放几个关键字!
1. 阶 B 树的结点容量规则表
| 结点类型 | 最少关键字个数(下限 / 生死线) | 最多关键字个数(上限) | 最少分叉数(子树数) | 最多分叉数(子树数) |
|---|---|---|---|---|
| 根结点(树高 ) | ||||
| 非根结点(含内部结点与终端叶结点) |
n阶B树,最多有n棵子树。
📌 考场秒记口诀:
- “根最少 1 个,非根最少 个,最多全都是 个!”
- “子树数永远等于关键字数 !”
2. 高频阶数速查(考场免计算直接套)
- 阶 B 树(2-3 树):非根结点关键字个数范围 (少于 个即变空时下溢,达到 个时上溢分裂)。
- 阶 B 树(2-3-4 树):非根结点关键字个数范围 (少于 个时下溢,达到 个时上溢分裂)。
- 阶 B 树(真题最爱考):非根结点关键字个数范围 (只剩 个就发生下溢! 达到 个时上溢分裂)。
3. B 树唯一的高度要求(应试考点)
- 结构铁律:所有叶结点(即外部失败结点 / 虚拟的 NULL 结点)必须在同一层!(绝对平衡,概念题高频考点)。
- 💡 极速应试指南:408 从未考过默写那个冗长的对数不等式公式!真题若考“求高度/结点数极值”(如 2012 年第 10 题),考场直接手画树逐层推导(第 1 层根结点 1 个,第 2 层 2 个,往后每层分叉按最少 或最多 算),比背死公式快 10 倍且零失误!
4. 上溢分裂 vs 下溢调整核心规则对齐表(⚠️ 考场防混淆红线)
| 对比维度 | 上溢(插入过多) | 下溢(删除过少) |
|---|---|---|
| 触发条件 | 结点关键字数达到 个(超过容量上限 ) | 非根结点关键字数 (跌破生死线) |
| 是否选偏右中位数? | ✅ 是!(偶数阶必选偏右中位数) | ❌ 绝不选!根本不存在中位数这一步 |
| 核心选取逻辑 | 取第 个关键字(偏右中位数)向上提升 | 全是**“两端极值”或“树指针物理定位”**,绝不取中位 |
| 具体操作动作 | 【中间提位】: • 偏右中位数并入父结点; • 左右两半分别自立为新左、右兄弟结点; • 若一路分裂至根,整棵树高 。 | 【三步决策链】: 1. 删非叶转叶:找直接前驱(左子树最大)或直接后继(右子树最小值)顶替; 2. 向兄弟借位:向左借取左兄最大值,向右借取右兄最小值(父下移,兄上移); 3. 与兄弟合并:将左兄 + 夹在正上方的父关键字 + 残缺结点三合一(拉父下水,父结点关键字数 )。 |
📌 学长一句话秒杀记忆口诀:
- “上溢才要挑中位,偶数偏右往上推;”
- “下溢借位看极值,合并正中把爹拉!”
模块二:B 树动态构建与插入分裂全流程(拿下 2020 年第 10 题)
B 树的构建过程是一个由下自上、向上长高的过程。新关键字永远只能先插入在最底层的终端叶结点中。
1. 核心插入与分裂铁律
【B 树插入与分裂闭环流程】
┌──────────────────┐
│ 找到应插入的叶结点 │
└────────┬─────────┘
▼
┌──────────────────┐
│ 结点内按序放入 K │
└────────┬─────────┘
▼
┌──────────────────┐
│关键字数达到 m 个? │
└────────┬─────────┘
/ \
否(≤ m-1) 是(= m, 上溢!)
/ \
┌──────────────────────┐ ┌──────────────────────────┐
│ ✅ 插入完成,树形稳定 │ │ 【中间分裂提位】 │
│ │ │ 取第 ⌈(m+1)/2⌉ 个关键字上移│
│ │ │ 左右两半分别自立为左右兄弟│
└──────────────────────┘ └─────────────┬────────────┘
▼
┌──────────────────────────┐
│ 提上去的关键字并入父结点 │
│ 父结点也满 m 个继续向上裂 │
│ 若根结点也分裂,树高 +1! │
└──────────────────────────┘- 定位插入点:
- 新关键字 必须落入最底层的终端叶结点(有关键字的最底层,非叶子外部 NULL 结点)。
- 上溢判定:
- 阶 B 树每个结点最多包含 个关键字。
- 若放入 后关键字个数达到 ,立即触发上溢分裂!
- 中位数提升分裂法则:
- 设结点内的 个关键字已升序排列为 ;
- 提取中间位置关键字(当 为偶数如 4 阶时,408 统考统一提取第 个关键字,即偏右中位数):
- 左侧留存: 留在原左结点;
- 中间提升: 向上并入双亲结点;
- 右侧新建: 拆分为新的右兄弟结点;
- 级联反应:父结点由于被插入了一个新关键字,若也达到 个,则递归继续向上分裂;若一路分裂至根结点,整棵 B 树高度增加 1(这是 B 树长高的唯一方式)。
先全放在根,直到溢出(超过最大关键字容量),挑中位数上溢成根(如是偶数个则挑偏右上溢出),后续进来的不放在根,而是与根比较,看放入哪边,具体看下方例题
2. 真题实战演练:2020 年 408 统考第 10 题
【2020年 408 统考第 10 题】 依次将关键字
5, 6, 9, 13, 8, 2, 12, 15插入初始为空的 4 阶 B 树后,根结点中包含的关键字是( )。
A. 8 B. 6, 9 C. 8, 13 D. 9, 12
步骤拆解(手把手复盘每一趟):
- 阶数信息速查:
- 阶 B 树:每个结点最多容纳 个关键字;一旦达到 4 个立即触发分裂。
- 分裂点取第 个关键字(偏右中位数)上升。
- 插入 5, 6, 9:
- 根结点放入 5、6、9,此时为
[5, 6, 9](3 个关键字,未超标,不分裂)。
- 根结点放入 5、6、9,此时为
- 插入 13(第 1 次分裂,树高从 1 变 2):
- 放入 13 后变为
[5, 6, 9, 13],包含 4 个关键字,上溢! - 取第 3 个关键字
9向上提升为新根; - 左孩子为
[5, 6],右孩子为[13]。 - 树形为:根
[9],左右孩子分别为[5, 6]与[13]。
- 放入 13 后变为
- 插入 8:
- ,放入左孩子
[5, 6]变为[5, 6, 8](3 个关键字,未超标)。
- ,放入左孩子
- 插入 2(第 2 次分裂,根结点扩容):
- ,放入左孩子变为
[2, 5, 6, 8],包含 4 个关键字,上溢! - 取第 3 个关键字
6向上提升,并入双亲根结点[9]; - 原左结点分裂为:左孩子
[2, 5],中间孩子[8]; - 此时根结点变为
[6, 9](2 个关键字,合法),树高仍为 2。
- ,放入左孩子变为
- 插入 12:
- ,落入右孩子
[13]变为[12, 13](2 个关键字,合法)。
- ,落入右孩子
- 插入 15:
- ,落入右孩子变为
[12, 13, 15](3 个关键字,达到上限但未超标,无需分裂)。
- ,落入右孩子变为
最终树形结构:
- 根结点:
[6, 9] - 第一棵子树():
[2, 5] - 第二棵子树():
[8] - 第三棵子树():
[12, 13, 15]
👉 秒出答案:根结点中包含的关键字是 6, 9,选 B!
模块三:B 树删除操作全套规则与决策树
B 树的删除操作分为 “删非叶(非终端)结点” 和 “删叶(终端)结点” 两大阶段。所有非叶结点的删除,一律先找替身转化为叶结点的删除!
flowchart TD A["要删除关键字 K"] --> B{"K 在哪一层?"} B -->|"在非叶(非终端)结点"| C["【找替身】<br/>用 K 的直接前驱(左子树最大值)<br/>或直接后继(右子树最小值)顶替 K"] C --> D["转化为:在最底层叶结点中<br/>删除那个被抽走的替身"] B -->|"本来就在最底层叶结点"| D D --> E{"删完后,该叶结点关键字数<br/>是否 ≥ ⌈m/2⌉ - 1 ?"} E -->|"是(够删,未破生死线)"| F["✅ 直接删除成功,调整结束!"] E -->|"否(不够删,发生下溢!)"| G{"看相邻的左/右亲兄弟<br/>谁的关键字数 > ⌈m/2⌉ - 1 ?"} G -->|"亲兄弟富余(够借)"| H["✅ 【向兄弟借:父下移,兄上移】<br/>夹在中间的父关键字下移填补当前结点;<br/>兄弟中紧挨着的极值关键字上移到父结点"] G -->|"左右亲兄弟全都在生死线上(不够借)<br/>(或题目未强制借位而直接合并)"| I["✅ 【与兄弟合并:拉父下水抱团】<br/>将当前结点 + 夹在中间的父关键字 + 相邻兄弟<br/>三者合并成一个新结点(父结点关键字数 -1)"]
核心动作拆解(怎么借?怎么合?)
- 找替身(非叶转叶):
- 直接前驱:当前关键字左下方子树一路往右走到底的最大关键字。
- 直接后继:当前关键字右下方子树一路往左走到底的最小关键字。
- 向富余亲兄弟借(口诀:“父下来,兄上去”):
- 向左兄弟借:夹在它俩中间的父关键字下移到当前结点开头;左兄弟的最大关键字上移到父结点原位置。
- 向右兄弟借:夹在它俩中间的父关键字下移到当前结点末尾;右兄弟的最小关键字上移到父结点原位置。
- 💡 特征:借位操作完成后,父结点的关键字个数保持不变,只是里面某个关键字的值被换成了兄弟的元素!
- 与亲兄弟合并(口诀:“左右抱团,把中间的爹拽下来”):
- 把当前残缺结点、相邻的左(或右)兄弟、以及父结点中夹在它们俩正中间的那个分隔关键字,三者打包合并成一个新结点。
- 💡 特征:合并操作会把父结点的一个关键字拉下来,因此父结点的关键字个数必定 !(若父结点因此也低于下限,则继续向上层递归调整;若根结点唯一的1个关键字被拉下来合并,则树高 )。
模块四:真题母题精讲(2022 年 5 阶 B 树删除 260)
【原题重现】

一、 考场 10 秒秒杀思路(教你怎么一眼看出答案)
- 第一步算下限:题目说是 阶 B 树,非根结点最少要有 个关键字,最多 个关键字。
- 第二步看删除位置:要删的
260在根结点(非叶结点),它的左下方是[100, 110],右下方是[280, 300]:- 直接前驱是
110; - 直接后继是
280。
- 直接前驱是
- 第三步直接抓“半成品”陷阱(秒杀 D 选项):
- 假如用前驱
110顶替260,根结点暂时变成60, 90, 110, 350(即 D 选项)。 - 但是!
110被抽走后,原来的叶结点只剩下[100](只有 个关键字 ,发生下溢!)。 - 既然发生下溢,就必须继续做“借位”或“合并”调整:
- 如果向左兄弟借,根结点里的
90会被85顶替(变成60, 85, 110, 350,即 C 选项); - 如果和兄弟合并,根结点里的
110(或90)会被拉下来(根只剩 3 个关键字,如60, 90, 350,即 B 选项)。
- 如果向左兄弟借,根结点里的
- 无论怎么调整,最终合法的根结点绝对不可能停留在
60, 90, 110, 350这个还没处理下溢的中间状态! 所以直接秒选 D!
- 假如用前驱
二、 全路径完整图解推导(把 A、B、C、D 彻底盘透)
为了把这道题吃透,我们把 “用前驱 110 顶替” 和 “用后继 280 顶替” 两条路线的所有合法调整画出来:
路线 1:用直接前驱 110 顶替 260(推出 C 选项、B 选项,排除 D 选项)
- 中间下溢态:
110上移顶替260后,根为[60, 90, 110, 350],原叶结点只剩[100](仅 1 个关键字,下溢!D 选项停在这里未做后续调整,故 D 不可能)。 - 合法调整分支 ①(向左兄弟借 得到 C 选项):
[100]的左兄弟是[70, 80, 85],有 个关键字(,富余够借!)。- 执行**“父下移、兄上移”**:父结点的
90下移并入[100]变成[90, 100];左兄弟最大的85上移到父结点顶替90。 - 最终根结点为:
60, 85, 110, 350(C 选项可能!)
- 合法调整分支 ②(与右兄弟合并 得到 B 选项):
- 如果不借左兄弟,而是将残缺的
[100]、右兄弟[280, 300]、以及夹在它们中间的父关键字110直接合并,得到新叶结点[100, 110, 280, 300](共 个关键字 ,未超上限,合法!)。 - 最终根结点为:
60, 90, 350(B 选项可能!)
- 如果不借左兄弟,而是将残缺的
路线 2:用直接后继 280 顶替 260(推出 B 选项、A 选项)
- 中间下溢态:
280上移顶替260后,根为[60, 90, 280, 350],原叶结点只剩[300](仅 1 个关键字,下溢!)。 - 观察左右亲兄弟:左兄弟
[100, 110]只有 2 个,右兄弟[400, 500]也只有 2 个。左右兄弟全都在生死线(2 个)上,谁都没法借,只能合并! - 合法调整分支 ①(与左兄弟合并 得到 B 选项):
- 将左兄弟
[100, 110]、夹在中间的父关键字280、以及[300]合并为[100, 110, 280, 300](4 个关键字,合法)。 - 父结点
280被拉下,最终根结点为:60, 90, 350(对应 B 选项!)
- 将左兄弟
- 合法调整分支 ②(与右兄弟合并 得到 A 选项):
- 将
[300]、夹在中间的父关键字350、以及右兄弟[400, 500]合并为[300, 350, 400, 500](4 个关键字,合法)。 - 父结点
350被拉下,最终根结点为:60, 90, 280(对应 A 选项!)
- 将
模块五:命题人设坑套路与避坑总结
- 陷阱一:拿“未处理下溢的半成品”当选项(本题 D 选项)
- 识别方法:只要发现某个选项只是单纯把前驱/后继提到了父结点,而原叶结点抽走元素后关键字个数 ,那这个选项 100% 是错的!因为🔴后续不管是“借”还是“合”,都会立刻改变父结点里夹着的关键字。
- 陷阱二:隔着兄弟“跨房借”(非相邻兄弟不能直接借)
- 规则红线:下溢结点只能向紧挨着的左亲兄弟或右亲兄弟借!比如在路线 2 中,
[300]下溢时,虽然最左边的[70, 80, 85]有 3 个元素,但它是隔了一层的“堂/远房兄弟”(中间隔着[100, 110]),不能直接跨过去借。
- 规则红线:下溢结点只能向紧挨着的左亲兄弟或右亲兄弟借!比如在路线 2 中,
- 陷阱三:合并时忘了把父结点的分隔关键字拉下来
- 规则红线:两个兄弟合并不叫两家直接拼一起,而是**“左兄弟 + 中间的父关键字 + 右兄弟”三合一**!所以合并后新结点的关键字个数等于 ,刚好不会超过上限 ,且父结点关键字个数必然少 个。
- 陷阱四:概念大混淆——“上溢和下溢都是选偏右中位数?”(考场致命误区)
- 上溢(插入分裂)才看中位数:
- 只有在结点塞满 个关键字触发上溢分裂时,才需要寻找中位数向上提升。
- 当 为偶数(如 4 阶满 4 个)时,中间有两个关键字,408 统考与主流教材统一约定取第 个(即偏右中位数)向上分裂。
- 下溢(删除调整)根本不存在“中位数”一说:
- 下溢是因为结点关键字个数低于下限 (元素太少,不够删),其所有补救动作全是极值操作或物理定位,绝不找中位数:
- 删非叶结点找替身:选直接前驱(左子树最大值)或直接后继(右子树最小值),这是极值!
- 向兄弟借位:向左兄弟借就挑左兄弟的最大值;向右兄弟借就挑右兄弟的最小值,这依然是紧邻一侧的极值!
- 与兄弟合并:由指针物理关系唯一定位,固定拉下父结点中夹在两个兄弟正中间的那个分隔关键字合三为一,根本无需任何中位数选取!
- 下溢是因为结点关键字个数低于下限 (元素太少,不够删),其所有补救动作全是极值操作或物理定位,绝不找中位数:
- 上溢(插入分裂)才看中位数: