一个节点存储多个分隔键
二叉搜索树每个节点只存储一个键。B 树则在一个节点中放多个已排序键,相邻键之间及两端各有一个子树区间,因此一次读取节点就能在多棵子树之间选择。当读取整个键块,比多次独立存储访问便宜时,这种安排尤其有用。
分支多本身不保证树矮。B 树同时要求最低填充量,并使全部叶节点深度相同。插入新键时,既要腾出空间,也要保留全部条件。本节使用自顶向下插入:进入已满子节点之前先分裂它,使每次递归开始时都有可用空间。
抽象对象是具全序的互异键集合。contains(x) 测试成员关系,insert(x) 在 未存在时加入它。本节的重复插入不只保持集合不变,也保持树结构不变。如果键要附带值,或允许多重集合,就要另外规定规则。
相等判定及 LOWER_BOUND 的比较,必须与同一全序一致。下方 CPU 模型把一次键比较或键/指针移动计为常数工作。
固定最小度的约定
定义 8.1.1
(最小度为 t 的 B 树)
固定整数 。每棵完成操作后的树符合以下不变量:
- 含 个键的节点,键严格递增。它要么没有子节点,称为叶;要么恰有 个子节点。
- 每个非根节点有 至 个键。非空根有 1 至 个键。空树只有一个不含键的叶根节点。
- 每棵子树全部键,都落在节点相邻键所指定的区间。如果键为 ,子节点 0 只含小于 的键; 的子节点 只含严格介于 的键;子节点 只含大于 的键。
- 全部叶深度相同,深度计从根到叶的边数。
含 个键的节点称为已满。非根内部节点至少有 个子节点,至多 个。 时,节点可含一、二或三个键,常称为 2–3–4 树。
不同教材对 B 树“阶”的用法未必相同,本节一律明定最小度 。2–3 树只允许每个节点一或两个键,与这里 的容量约定不同。
分隔键本身也是已存储集合成员,包括内部节点的键,不是必须另外在叶保留一份的副本。B+ 树的记录放置约定不同,不能把它的叶副本规则直接搬入本节算法。
每步只搜索一个区间
LOWER_BOUND(keys,x) 返回第一个不小于 x 的键索引;如果全部键较小,则返回数组长度。键与子节点都用从零开始的索引。
CONTAINS(node, x):
i = LOWER_BOUND(node.keys, x)
if i < number of node.keys and node.keys[i] == x:
return true
if node is a leaf:
return false
return CONTAINS(node.children[i], x)
证明透视
为什么不用搜索其他子树
如果节点内有键等于 ,就已找到集合成员,即使此节点是内部节点也一样。否则 lower bound 找出 唯一可能所在的区间。由范围不变量,其他每棵子树只含严格位于该区间以外的键。
只进入该子节点,就保留“如果 已存储且尚未找到,它就在此子树”的陈述。到叶仍不相等,即证明不存在。每次递归在有限树中下降一层,所以搜索终止。
父节点有空间时,分裂已满子节点
假设父 少于 个键,其索引 子节点 已满,键为 。把中位键 升至父的索引 。 保留 ,新右兄弟 接收 。两个子节点现在各有 个键。
如果 是内部节点,旧的 个子节点也要分开: 保留索引 , 接收 。移动的是整棵子树,其内部结构不变。如果 原本是叶,分裂后两者仍是叶。
SPLIT_CHILD(P, i): // P has room; child i is full
Y = P.children[i]
median = Y.keys[t-1]
Z = a new node with the same leaf status as Y
Z.keys = a copy of Y.keys[t .. 2t-2]
if Y is not a leaf:
Z.children = Y.children[t .. 2t-1]
Y.children = Y.children[0 .. t-1]
Y.keys = Y.keys[0 .. t-2]
insert median into P.keys at index i
insert Z into P.children at index i+1
数组切片表示建立所列的新数组;改左节点时,不能意外擦掉右节点仍需要的数据。P.children[i] 仍指左节点 。中位键从被分裂的 移除,只在 存储一次,左右两个结果子节点都不保留它。
引理 8.1.2
(分裂已满子节点)
设在最小度为 的 B 树中,节点 至多有 个键,其子节点 已满。执行 SPLIT_CHILD(P, i) 后:存储的键集合不变; 与新兄弟 各有 个键; 多一个键、多一个子节点;次序与区间条件全部成立; 之下每个叶的深度不变。
证明
(分裂保留集合、区间与平衡深度)
的键分成左键、中位键及右键,因此每个旧键仍恰好出现一次。两个子节点各有 个键,符合范围。父键数增加一,但原本有空间,所以不超过 。父子节点数也增加一,保留“子节点数等于键数加一”。
每个左键小于中位键,每个右键大于中位键。内部节点的首 个旧子区间属左,余下 个属右。原子树整体已位于 的适当相邻键之间,插入其中位键后,父的其他区间仍有效。
两个替代节点位于旧子节点的同一层,其后代子树移动时高度不变,因此每个叶保留原深度。分裂改变分支及键的位置,却保持所表示集合与平衡叶层。
概念视角结构
分裂重新分组,但不改变键的顺序
把一棵子树依次列出:子树 、键 、子树 、键 ,依此类推,每个子树以同样方式展开。由区间不变量可知,这样读出的恰是全部键的递增序列。分裂不改变这个序列:原本在 两半之间的中位键,现在位于父节点中 与 之间。改变的只是序列如何分组成节点。
常见错误
(把中位键留在被分裂的节点)
把中位键写入父节点,却没有从 移除,该键就被存了两次。取 、,若 仍留在 ,左节点为 ,右节点为 ,父节点键为 。子节点 0 只应含严格小于其分隔键的键,现在却含有 ;而且 有 个键,并非 个。中位键是升上去:离开 ,在 中只存储一次。把分隔键复制进叶是 B+ 树的约定,不适用于这里。
包括根在内,都先分裂再下降
先搜索新键;此成员搜索不修改任何树节点,确保重复插入在任何结构修改之前就结束并保持树不变。因此下方辅助程序有两个前提:新键不在整棵树中;接受调用的节点未满。
INSERT(x):
if CONTAINS(root, x):
return false
if root is full:
oldRoot = root
root = a new internal node with no keys and child [oldRoot]
SPLIT_CHILD(root, 0)
INSERT_NONFULL(root, x)
return true
INSERT_NONFULL(node, x):
i = LOWER_BOUND(node.keys, x)
if node is a leaf:
insert x into node.keys at index i
return
if node.children[i] is full:
SPLIT_CHILD(node, i)
if x > node.keys[i]:
i = i + 1
INSERT_NONFULL(node.children[i], x)
分裂后,与刚升起的中位键比较,决定去左还是右。相等不可能发生,因为插入前 不存在,而分裂不产生新键。
常见错误
(沿用分裂前选定的子节点下降)
取 ,父节点 ,已满的中间子节点 ,插入 。分裂前 LOWER_BOUND 给出 。分裂把 升起,父节点变为 ,索引 1、2 的子节点为 与 。若代码仍用 ,就会把 放入 ,得到 ,位于分隔键 之下。之后搜索 时,与 比较会走向子节点 2,即 ,结果错误地报告不存在。分裂后要拿 与升起的中位键比较, 较大就把 加一。
暂时没有键的新根,是紧接分裂之前的工作记录。分裂后它有一键两子,符合完成树不变量。只有根分裂会增加高度:全部旧叶同时加深一层。
反例模式
分裂已满父节点的子节点
有人会以为,不论父节点如何,已满的子节点都可以分裂。取 ,已满的父节点 及其已满的子节点 。分裂会提升 ,父节点便成为 ,有四个键,但 。引理要求父节点有空位。下降时先分裂已满的子节点再进入,保证所进入的每个节点都未满;没有父节点的根,则在一个新根之下分裂。
定理 8.1.3
(自顶向下插入是正确的)
设最小度为 的 B 树表示有限集合 , 为一个键。若 ,INSERT(x) 返回 false 且不改变任何东西;否则返回 true,所得之树是表示 的最小度 B 树。
证明
(沿下降路径归纳)
若 ,成员测试在修改任何节点之前就返回。否则,根分裂是上述分裂引理在“父节点没有键”时的一个实例,所以之后树仍然是 的有效表示,且根未满。其后每次分裂同样是引理的实例,保留集合及全部不变量,而递归总是进入未满节点。每次分裂后都拿 与新的分隔键比较,因此所选子区间含有 。最后在叶中按 LOWER_BOUND 位置放入 ,键仍严格递增,该叶至多有 个键。所以树表示 ,并符合所有不变量。
证明透视
为什么自顶向下插入不会使节点溢出
辅助程序开始时,根未满:要么原本未满,要么刚换成一键新根。每个内部调用所选子节点,要么本来未满,要么先分裂再下降。父在进入时未满,所以能接收该次升键;之后父可能已满,但此次插入只从它下降一次,不需要再向它升第二个键。
递归再次进入未满节点,最终到达至多有 个键的叶;加入一键后至多 。范围比较把键放入正确区间;全部分裂保留旧集合及平衡深度。所以结果恰表示旧集合加上 ,并符合全部不变量,不需要把溢出沿递归向上传。
最小度二的完整插入跟踪
例题 8.1.4
(在 t = 2 时依次插入 1 至 10)
从空叶根开始,每个节点至多放三键。
| 插入键 | 之后的根 | 叶插入前的结构事件 |
|---|---|---|
| 1 | [1] | 无 |
| 2 | [1,2] | 无 |
| 3 | [1,2,3] | 无 |
| 4 | [2] | 分裂已满根,升起 2 |
| 5 | [2] | 无 |
| 6 | [2,4] | 分裂右子节点,升起 4 |
| 7 | [2,4] | 无 |
| 8 | [2,4,6] | 分裂最右子节点,升起 6 |
| 9 | [4] | 分裂已满根,升起 4,再把 9 插成 [7,8,9] |
| 10 | [4] | 分裂孙节点 [7,8,9],升起 8,再把 10 插成 [9,10] |
插入 4 后:
[2]
/ \
[1] [3,4]
插入 8 后:
[2,4,6]
/ | | \
[1] [3] [5] [7,8]
插入 10 后:
[4]
/ \
[2] [6,8]
/ \ / | \
[1] [3] [5] [7] [9,10]
第九次插入时,旧根已满,尽管目标叶仍有空间,所选算法仍先分裂根。它保持 B 树不变量,却不保证在同一集合的所有表示中高度最小。
下面的互动图逐次原子分裂地重放这段插入记录及其他记录,并以 B 树的不变量检查每个显示的快照。
下降前先分裂,中位键只移动一次
重放最小度数 B 树的插入记录,检查每次原子分裂,并搜索当前快照。内部的分隔键就是集合成员,不是叶节点的副本。
改变度数会重放同一完整请求记录。即使正检查较早事件,插入仍加到完整记录末尾,并显示其最后快照。撤销移除记录的最后请求后重放,并不是 B 树删除。独立搜索探针只作用于当前显示的快照。
已在最后事件。
当前插入请求: [1,2,3,4,5,6,7,8,9,10].
结构事件 34/34: 把不存在的键插入非满叶节点; 请求次序: 10; x=10.
方框显示节点 ID 及排序键。E 表示当前插入事件路径;Q 表示独立搜索路径。P/L/R 表示此事件的分裂父节点及左右节点。节点表提供键、子引用、区间及深度,不必依赖图形。
插入事件路径: N5 → N6 → N7.
| 节点 | 排序键 | 键数 | 允许键数 | 子树严格区间 | 子节点 ID | 深度 | 节点种类 |
|---|---|---|---|---|---|---|---|
| N5 E Q | [4] | 1 | 1..3 | (−∞,+∞) | [1,6] | 0 | 根 · 内部 |
| N1 | [2] | 1 | 1..3 | (−∞,4) | [0,2] | 1 | 内部 |
| N0 | [1] | 1 | 1..3 | (−∞,2) | 无 | 2 | 叶 |
| N2 | [3] | 1 | 1..3 | (2,4) | 无 | 2 | 叶 |
| N6 E Q | [6,8] | 2 | 1..3 | (4,+∞) | [3,4,7] | 1 | 内部 |
| N3 | [5] | 1 | 1..3 | (4,6) | 无 | 2 | 叶 |
| N4 | [7] | 1 | 1..3 | (6,8) | 无 | 2 | 叶 |
| N7 E | [9,10] | 2 | 1..3 | (8,+∞) | 无 | 2 | 叶 |
检查实际快照
- 每个节点的键严格递增
- 是
- 根/非根占用界限成立
- 是
- 内部节点子数为键数加一
- 是
- 全部子键符合严格区间
- 是
- 每个存储键恰好出现一次
- 是
- 全部叶深度相同
- 是
- 存储键等于已完成请求的集合
- 是
此高度的非空树键数界限: 7 ≤ 10 ≤ 63.
搜索当前快照: x=8; 成员查询结果: 是.
探针搜索此快照,不是最后的记录结果。即使是内部节点,相等时也立即找到;否则 lower_bound 选出唯一可能的子区间。叶节点中找不到相等便证明不存在。
| 节点 | 排序键 | 子树严格区间 | lower_bound 索引 | 找到相等键 | 下一子节点 |
|---|---|---|---|---|---|
| N5 | [4] | (−∞,+∞) | 1 | 否 | N6 |
| N6 | [6,8] | (4,+∞) | 1 | 是 | 无 |
每个完成插入请求之后的状态
| 请求次序 | 排序键 | 动作 | 根 | 根到叶高度(边数) | 此请求中的分裂数 |
|---|---|---|---|---|---|
| 1 | 把不存在的键插入非满叶节点 | [1] | 0 | 0 | |
| 2 | 把不存在的键插入非满叶节点 | [1,2] | 0 | 0 | |
| 3 | 把不存在的键插入非满叶节点 | [1,2,3] | 0 | 0 | |
| 4 | 把不存在的键插入非满叶节点 | [2] | 1 | 1 | |
| 5 | 把不存在的键插入非满叶节点 | [2] | 1 | 0 | |
| 6 | 把不存在的键插入非满叶节点 | [2,4] | 1 | 1 | |
| 7 | 把不存在的键插入非满叶节点 | [2,4] | 1 | 0 | |
| 8 | 把不存在的键插入非满叶节点 | [2,4,6] | 1 | 1 | |
| 9 | 把不存在的键插入非满叶节点 | [4] | 2 | 1 | |
| 10 | 把不存在的键插入非满叶节点 | [4] | 2 | 1 |
完整结构事件记录
| 结构事件 | 请求次序 | 排序键 | 动作 | 已完成请求 | 事件焦点节点 |
|---|---|---|---|---|---|
| 不适用 | 不适用 | 空的叶根 | 0 | 无 | |
| 1 | 1 | 改变树前先搜索重复键 | 0 | N0 | |
| 1 | 1 | 把不存在的键插入非满叶节点 | 1 | N0 | |
| 2 | 2 | 改变树前先搜索重复键 | 1 | N0 | |
| 2 | 2 | 把不存在的键插入非满叶节点 | 2 | N0 | |
| 3 | 3 | 改变树前先搜索重复键 | 2 | N0 | |
| 3 | 3 | 把不存在的键插入非满叶节点 | 3 | N0 | |
| 4 | 4 | 改变树前先搜索重复键 | 3 | N0 | |
| 4 | 4 | 原子地替换并分裂满根 | 3 | N1 | |
| 4 | 4 | 下降至选定的非满子节点 | 3 | N2 | |
| 4 | 4 | 把不存在的键插入非满叶节点 | 4 | N2 | |
| 5 | 5 | 改变树前先搜索重复键 | 4 | N2 | |
| 5 | 5 | 下降至选定的非满子节点 | 4 | N2 | |
| 5 | 5 | 把不存在的键插入非满叶节点 | 5 | N2 | |
| 6 | 6 | 改变树前先搜索重复键 | 5 | N2 | |
| 6 | 6 | 父节点有空位时分裂满子节点 | 5 | N1 | |
| 6 | 6 | 下降至选定的非满子节点 | 5 | N3 | |
| 6 | 6 | 把不存在的键插入非满叶节点 | 6 | N3 | |
| 7 | 7 | 改变树前先搜索重复键 | 6 | N3 | |
| 7 | 7 | 下降至选定的非满子节点 | 6 | N3 | |
| 7 | 7 | 把不存在的键插入非满叶节点 | 7 | N3 | |
| 8 | 8 | 改变树前先搜索重复键 | 7 | N3 | |
| 8 | 8 | 父节点有空位时分裂满子节点 | 7 | N1 | |
| 8 | 8 | 下降至选定的非满子节点 | 7 | N4 | |
| 8 | 8 | 把不存在的键插入非满叶节点 | 8 | N4 | |
| 9 | 9 | 改变树前先搜索重复键 | 8 | N4 | |
| 9 | 9 | 原子地替换并分裂满根 | 8 | N5 | |
| 9 | 9 | 下降至选定的非满子节点 | 8 | N6 | |
| 9 | 9 | 下降至选定的非满子节点 | 8 | N4 | |
| 9 | 9 | 把不存在的键插入非满叶节点 | 9 | N4 | |
| 10 | 10 | 改变树前先搜索重复键 | 9 | N4 | |
| 10 | 10 | 下降至选定的非满子节点 | 9 | N6 | |
| 10 | 10 | 父节点有空位时分裂满子节点 | 9 | N6 | |
| 10 | 10 | 下降至选定的非满子节点 | 9 | N7 | |
| 10 | 10 | 把不存在的键插入非满叶节点 | 10 | N7 |
- 存储的不同键
- 10
- 已完成请求
- 10/10
- 根到叶高度(边数)
- 2
- 节点数
- 8
- 搜索找到 x
- 是
- 此搜索访问节点数
- 2
- 快照检查及表示集合一致
- 是
- 待完成请求的键
- 不适用
t=2; 结构事件 34/34: 把不存在的键插入非满叶节点; 已完成请求: 10/10; 存储的不同键: [1,2,3,4,5,6,7,8,9,10]. 搜索当前快照: x=8, 是, 此搜索访问节点数: 2; 快照检查及表示集合一致: 是.
为何表示仍是一棵 B 树
最小度数 t≥2 表示非根节点有 t−1 至 2t−1 个键。非空根有 1 至 2t−1 键,空树则是一个空的叶根。键严格排序,内部节点的子数比键数多一,子区间严格,而且全部叶深度相同。t=2 的约定是 2–3–4 树,不是 2–3 树。
以第 t−1 键分裂有 2t−1 键的满子节点。前 t−1 键留左方,后 t−1 键移右方,中位键移至非满父节点。若子节点为内部节点,前 t 个子引用移左,后 t 个移右,不改变各子树结构。每个旧键保留一次,区间及叶层也保留。
自顶向下插入始终进入非满节点。下降前先分裂满的目标子节点;父节点进入时有空位,所以能接收中位键。父节点之后可变满,但本请求只从它下降一次。最后最多有 2t−2 键的叶加入新键,仍不超额。暂时没有键的内部新根是工作记录,因此图把替换及分裂合为原子事件。
t=2、请求依序 1 至 10 时,每次完成后根键为 [1]、[1,2]、[1,2,3]、[2]、[2]、[2,4]、[2,4]、[2,4,6]、[4]、[4]。插入 9 前,即使目标叶还有空位,满根仍先分裂。只有根分裂增加高度,全部叶同时加深。算法保留不变式,不保证在同一集合的全部合法表示中高度最小。
任何分裂前先做只读成员检查。因此在满根 [1,2,3] 中插入 2,既不改变键,也不改变树形。搜索时,与 x 相等的内部分隔键已是集合成员,不必再到叶找。此 B 树移动被提升键;B+ 树采用不同的存储约定。
非空高度 h 的树由占用界限得 2t^h−1≤n≤(2t)^(h+1)−1,因此 h≤log_t((n+1)/2)。t 可变时,访问节点不是常数 CPU 工作:扫描或移动键需 O(t);块模型则可能一次读取整个节点。本图报告访问节点及实际树形,不测量磁盘时间。快照及不变式检查是插入算法以外的教学成本。
为何撤销并不示范 B 树删除?
撤销会从空根重新建立较早的插入记录。真正删除必须通过借键、合并,有时缩减根,修复最低占用。重放较短记录没有实现这些删除规则,本图也不作此声称。
键是 0 至 30 中互异的集合成员。本图支持最小度数 2 或 3,及最多十二个插入请求。搜索针对中途快照;表示集合只包含已完成请求。每个分裂画面都是原子合法树状态,叶插入之前保留旧集合。删除、B+ 树、存储缓存及实体页分配不在范围。
例题 8.1.5
(重复键与已满的根(t = 2))
设根是已满的叶 。调用 INSERT(2) 时,先执行 CONTAINS,在索引 1 找到 并返回 true,所以 INSERT 返回 false,已满的根原封不动,完全没有分裂。
调用 INSERT(4) 时, 不存在。根已满,于是建立带有子节点 的新空根并分裂:中位键 升起,留下子节点 与 。在根 上执行 INSERT_NONFULL,LOWER_BOUND 给出 ;子节点 未满,不需再分裂, 直接插入该叶。结果是根 ,叶为 与 ,与上面跟踪中的树相同。两次调用的差别只在成员测试:只有键不存在时才发生结构改变。
最低填充量给出对数高度界
定理 8.1.6
(高度与键数的关系)
设非空且最小度为 的 B 树高度为 (计边数),键数为 。则
证明
(逐层计算节点数)
时,根至少一键两子,每个非根内部节点至少有 个子节点。因此第 层至少有 个节点,各至少有 个键。逐层相加,
时,同一下界只是 。由 取对数,得 。
另一极端,第 层至多有 个节点,各至多 个键,所以 。这些界计的是键数,不只是节点数;空叶根另行处理。
反例模式
不能放弃叶深度相同这一条
有人声称,只要每个非根节点有 至 个键,即使各叶深度不同,也已经有 。取 ,根 有子节点 与 ,而 有子节点 与 。每个节点都只有一个键,每个内部节点的子节点数都比键数多一,区间条件也成立。可是最长路径有 条边而 ,而该界要求 。把此模式向右延续,可得 个键、高度为 ,高度与 成线性。不变量 4 正是迫使每条从根到叶的路径都有完整层数的条件。
例题 8.1.7
(t = 3、40 个键时,高度可以是多少?)
定理要求 。 时下界是 ,所以高度不可能是 3 或以上。 时上界是 ,所以高度不可能至多为 1。 时两界为 。因此每棵最小度为 3、有 40 个键的 B 树,高度恰好是 2。
边界情况是 : 的上界 ,只有根有五个键、六个叶各有五个键才能取到。再多一个键,即 ,就已迫使 。
每节点线性扫描时,搜索比较次数为 。二分查找可降至 ,但数组插入及分裂仍可能移动 个键或指针。直接插入算法连同成员预查,最坏 CPU 工作量为 ,所以是 。固定 时为 。成员预查与插入是两次下降,常数倍不改变上述界。
选 时,要使满节点的 个键及 个子引用可装入一个存储块。此模型下,从根到叶下降会读 个块。一次分裂在该层只触及常数个节点块,因此插入连写入及预查也需 块访问。分裂可能写父及左右结果子节点,共常数个块;即使不重用预查读过的块,两次下降仍保持相同渐近界。这不表示在一块内搜索或重排全部键是常数 CPU 工作;表示与成本模型要一并说明。
删除另需借键、合并及可能缩根,恢复最低填充量,不能把上述叶插入直接反转当作完成。本节证明与跟踪只涵盖搜索及插入。
有解练习
快速检查
(1. 分裂内部节点时也要分配子节点)
设 。父键为 [5,60],索引 1 的中间子节点已满,键为 [10,20,30,40,50],依次有子节点 。分裂后,求父键、左右键数组及它们各自的子节点清单。
解答 · 解答 1
升起中位键 30,父变为 [5,30,60]。左节点 [10,20] 配 ;新右节点 [40,50] 配 。两者各有 键及 子。父原本另外两个外侧子节点不变。30 只在父存储一次,不复制入左右子。
快速检查
(2. 搜索内部键、叶键与不存在的键)
用最终十键树跟踪 2、7、11 的成员查询,列出检查的节点键数组及各搜索停止的理由。
解答 · 解答 2
搜索 2:走 [4] 再走 [2],相等即证存在,不必继续下降。搜索 7:走 [4]、[6,8]、[7] 并找到。搜索 11:走 [4]、[6,8]、[9,10];叶键全较小,没有子节点可再搜,所以返回假。
快速检查
(3. 高度界不保证最低高度)
时,高度二的树可只含六键吗?虽然跟踪结果高二,集合 能否也有合法的高度一表示?
解答 · 解答 3
高度二至少需要 键,所以六键不可能。十键集合可用根 [3,6,9],叶子节点 [1,2]、[4,5]、[7,8]、[10],在高度一符合全部填充量及范围条件。自顶向下分裂保证正确平衡,不保证该集合的最矮配置。
快速检查
(4. 父可在下降之前变满)
设 ,父键为 [10,30],中间已满叶为 [12,18,25]。父未满,其余树结构合法。用辅助程序插入未存在的 20,求新父及中间区域的叶。再解释公开操作重复 insert(20) 会怎样。
解答 · 解答 4
先分裂,升起 18,父变为 [10,18,30],两叶为 [12] 及 [25]。因 ,下降右叶,插入成 [20,25]。父虽已满仍合法,此次操作不再需向它升键。重复公开插入先找到 20,在任何分裂前返回假,所以即使根已满也不改动。