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! │
                               └──────────────────────────┘
  1. 定位插入点:
    • 新关键字 必须落入最底层的终端叶结点(有关键字的最底层,非叶子外部 NULL 结点)。
  2. 上溢判定:
    • 阶 B 树每个结点最多包含 个关键字。
    • 若放入 后关键字个数达到 ,立即触发上溢分裂!
  3. 中位数提升分裂法则:
    • 设结点内的 个关键字已升序排列为 ;
    • 提取中间位置关键字(当 为偶数如 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 个立即触发分裂。
    • 分裂点取第 个关键字(偏右中位数)上升。
  1. 插入 5, 6, 9:
    • 根结点放入 5、6、9,此时为 [5, 6, 9](3 个关键字,未超标,不分裂)。
  2. 插入 13(第 1 次分裂,树高从 1 变 2):
    • 放入 13 后变为 [5, 6, 9, 13],包含 4 个关键字,上溢!
    • 取第 3 个关键字 9 向上提升为新根;
    • 左孩子为 [5, 6],右孩子为 [13]。
    • 树形为:根 [9],左右孩子分别为 [5, 6] 与 [13]。
  3. 插入 8:
    • ,放入左孩子 [5, 6] 变为 [5, 6, 8](3 个关键字,未超标)。
  4. 插入 2(第 2 次分裂,根结点扩容):
    • ,放入左孩子变为 [2, 5, 6, 8],包含 4 个关键字,上溢!
    • 取第 3 个关键字 6 向上提升,并入双亲根结点 [9];
    • 原左结点分裂为:左孩子 [2, 5],中间孩子 [8];
    • 此时根结点变为 [6, 9](2 个关键字,合法),树高仍为 2。
  5. 插入 12:
    • ,落入右孩子 [13] 变为 [12, 13](2 个关键字,合法)。
  6. 插入 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. 找替身(非叶转叶):
    • 直接前驱:当前关键字左下方子树一路往右走到底的最大关键字。
    • 直接后继:当前关键字右下方子树一路往左走到底的最小关键字。
  2. 向富余亲兄弟借(口诀:“父下来,兄上去”):
    • 向左兄弟借:夹在它俩中间的父关键字下移到当前结点开头;左兄弟的最大关键字上移到父结点原位置。
    • 向右兄弟借:夹在它俩中间的父关键字下移到当前结点末尾;右兄弟的最小关键字上移到父结点原位置。
    • 💡 特征:借位操作完成后,父结点的关键字个数保持不变,只是里面某个关键字的值被换成了兄弟的元素!
  3. 与亲兄弟合并(口诀:“左右抱团,把中间的爹拽下来”):
    • 把当前残缺结点、相邻的左(或右)兄弟、以及父结点中夹在它们俩正中间的那个分隔关键字,三者打包合并成一个新结点。
    • 💡 特征:合并操作会把父结点的一个关键字拉下来,因此父结点的关键字个数必定 !(若父结点因此也低于下限,则继续向上层递归调整;若根结点唯一的1个关键字被拉下来合并,则树高 )。

模块四:真题母题精讲(2022 年 5 阶 B 树删除 260)

【原题重现】

5阶B树删除260原题


一、 考场 10 秒秒杀思路(教你怎么一眼看出答案)

  1. 第一步算下限:题目说是 阶 B 树,非根结点最少要有 个关键字,最多 个关键字。
  2. 第二步看删除位置:要删的 260 在根结点(非叶结点),它的左下方是 [100, 110],右下方是 [280, 300]:
    • 直接前驱是 110;
    • 直接后继是 280。
  3. 第三步直接抓“半成品”陷阱(秒杀 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

  • 中间下溢态: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

  • 中间下溢态: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 选项!)

模块五:命题人设坑套路与避坑总结

  1. 陷阱一:拿“未处理下溢的半成品”当选项(本题 D 选项)
    • 识别方法:只要发现某个选项只是单纯把前驱/后继提到了父结点,而原叶结点抽走元素后关键字个数 ,那这个选项 100% 是错的!因为🔴后续不管是“借”还是“合”,都会立刻改变父结点里夹着的关键字。
  2. 陷阱二:隔着兄弟“跨房借”(非相邻兄弟不能直接借)
    • 规则红线:下溢结点只能向紧挨着的左亲兄弟或右亲兄弟借!比如在路线 2 中,[300] 下溢时,虽然最左边的 [70, 80, 85] 有 3 个元素,但它是隔了一层的“堂/远房兄弟”(中间隔着 [100, 110]),不能直接跨过去借。
  3. 陷阱三:合并时忘了把父结点的分隔关键字拉下来
    • 规则红线:两个兄弟合并不叫两家直接拼一起,而是**“左兄弟 + 中间的父关键字 + 右兄弟”三合一**!所以合并后新结点的关键字个数等于 ,刚好不会超过上限 ,且父结点关键字个数必然少 个。
  4. 陷阱四:概念大混淆——“上溢和下溢都是选偏右中位数?”(考场致命误区)
    • 上溢(插入分裂)才看中位数:
      • 只有在结点塞满 个关键字触发上溢分裂时,才需要寻找中位数向上提升。
      • 当 为偶数(如 4 阶满 4 个)时,中间有两个关键字,408 统考与主流教材统一约定取第 个(即偏右中位数)向上分裂。
    • 下溢(删除调整)根本不存在“中位数”一说:
      • 下溢是因为结点关键字个数低于下限 (元素太少,不够删),其所有补救动作全是极值操作或物理定位,绝不找中位数:
        • 删非叶结点找替身:选直接前驱(左子树最大值)或直接后继(右子树最小值),这是极值!
        • 向兄弟借位:向左兄弟借就挑左兄弟的最大值;向右兄弟借就挑右兄弟的最小值,这依然是紧邻一侧的极值!
        • 与兄弟合并:由指针物理关系唯一定位,固定拉下父结点中夹在两个兄弟正中间的那个分隔关键字合三为一,根本无需任何中位数选取!

关联知识卡片