高级树：从平衡不变式到磁盘友好的多路索引

二叉搜索树最迷人的地方，也是它最危险的地方：树的形状完全取决于更新顺序。同一批键，换一个插入次序，可能得到接近完全平衡的树，也可能得到一条长链。搜索、插入和删除都只走一条根到叶的路径，所以真正决定性能的不是“有多少个节点”，而是“这条路径有多长”。

高级树的设计可以归结为同一个问题：我们愿意维护什么额外不变式，来换取可预测的路径长度？AVL 树严格限制左右子树高度差；红黑树用较宽松的颜色约束控制最长路径；顺序统计树和区间树在平衡树上维护可局部更新的摘要；B 树则把一个节点扩成一整页，让一次外存访问带回许多键。

本文默认键互不相同。若业务允许重复键，应明确规定“重复项总放右侧”、为节点保存计数，或用 (键, 唯一序号) 组成复合键。只写一句“左边小、右边大”却不定义相等键的去向，会让插入、排名和删除的语义在边界处失去一致性。

二叉搜索树是所有平衡方案的基线

二叉搜索树的核心不变式作用于每个节点，而不只是根。对节点 $x$：左子树所有键都小于 $x.key$，右子树所有键都大于 $x.key$；两棵子树还要递归满足同样的条件。于是中序遍历按“左子树、当前节点、右子树”访问时，得到严格递增序列。

查询都在一条路径上完成

搜索键 $k$ 时，从根开始比较。若 $k<x.key$ 就进入左子树，若 $k>x.key$ 就进入右子树。最小值沿左指针到底，最大值沿右指针到底。查找后继则分两种情况：

• 若 $x$ 有右子树，后继是右子树中的最小节点。
• 若 $x$ 没有右子树，就沿父指针向上，直到第一次从某个祖先的左侧回来；这个祖先就是后继。若始终从右侧回来，则 $x$ 已经是最大节点，没有后继。

这些过程最多走树高 $h$ 条边，因此时间都是 $O(h)$。中序遍历不同，它会访问每个节点一次，时间是 $\Theta(n)$，与树是否平衡无关。

插入简单，删除要分清“删谁”和“谁补位”

插入先执行一次失败的搜索，把新节点接到最后遇到的父节点下面。删除节点 $z$ 时有三种结构情形：

1. 左子树为空，用右子树替换 $z$。
2. 右子树为空，用左子树替换 $z$。
3. 两棵子树都非空，取右子树最小节点 $y$，也就是 $z$ 的后继。若 $y$ 不紧挨着 $z$，先用 $y.right$ 替换 ，再把 接给 ；最后用 替换 ，并把 接给 。

“替换”只改父子链接，不会自动接管被替换节点的孩子。把这个细节写进独立的 TRANSPLANT 操作，能避免双子节点删除时丢失子树。

BST-DELETE(T, z)
  若 z.left 为空：用 z.right 替换 z
  否则若 z.right 为空：用 z.left 替换 z
  否则：
    y = z.right 中的最小节点
    若 y.parent != z：
      用 y.right 替换 y
      y.right = z.right
    用 y 替换 z
    y.left = z.left

高度才是性能变量

若按 1, 2, 3, …, n 插入，树会退化成高度 $n-1$ 的右链，基本操作最坏为 $\Theta(n)$。一棵含 $n$ 个节点的二叉树，高度至少为 $\lfloor\log_2 n\rfloor$；只有形状足够紧凑时，操作才接近 $\mathrm{\Theta }$。

随机顺序插入互异键时，期望高度是 $O(\log n)$，但“期望”不是最坏情况保证。只要输入顺序可被外部控制，或者服务需要稳定尾延迟，就应维护显式的平衡条件。

小测

AVL 树用严格高度差换取更短路径

AVL 树仍是二叉搜索树，但每个节点还维护子树高度。若空子树高度记为 $-1$、叶子高度记为 $0$，节点 $x$ 的高度与平衡因子是

合法 AVL 树要求每个节点的平衡因子只能是 $-1$、$0$ 或 $1$。更新一个节点后，必须从它向根回溯，先更新孩子较低处的高度，再更新祖先高度；顺序反过来会让祖先读到旧值。

为什么高度一定是对数级

设 $N(h)$ 是高度为 $h$ 的 AVL 树至少需要的节点数。要让节点尽量少又恰好达到高度 $h$，两棵孩子子树的高度应为 $h-1$ 和 $h-2$，于是

这个递推与斐波那契数列同阶增长，因此 $N(h)=\Omega(\varphi^h)$，其中 $\varphi=(1+\sqrt5)/2$。反过来得到 。这份保证来自每个节点的局部高度差，而不是输入的随机性。

四种失衡形状其实只有两种旋转

设第一个失衡祖先为 $x$。若重路径连续向左，是“左—左”形，右旋 $x$；连续向右，是“右—右”形，左旋 $x$。若重路径先左后右，是“左—右”形，先左旋左孩子，再右旋 $x$；“右—左”形完全对称。

旋转不改变中序次序。以左旋为例，旋转前的顺序是

旋转后仍是同一顺序，只是 $y$ 成为局部根、$x$ 成为 $y$ 的左孩子、$\beta$ 改接为 $x$ 的右子树。

插入修复的边界

AVL 插入先按 BST 规则落到叶子，再沿递归返回路径更新高度并修复第一个失衡点。单旋或双旋能恢复该子树原有高度，所以一次插入只需常数次旋转，总时间由搜索与回溯决定，为 $O(\log n)$。

这里要谨慎区分插入与删除：删除可能让修复后的子树继续变矮，失衡可以向祖先传播。若实现完整 AVL 删除，不能直接套用“修一次就停止”的插入结论。

小测

红黑树用颜色约束给出最坏高度界

红黑树在 BST 节点上增加一位颜色。实现时通常只创建一个共享的黑色哨兵 nil，所有缺失孩子都指向它，根的父指针也指向它。这样修复代码可以读取缺失孩子的颜色，而不必在每一步先判断空指针。

一棵合法红黑树满足五条不变式：

1. 每个节点非红即黑。
2. 根是黑色。
3. 所有 nil 叶子都是黑色。
4. 红节点的两个孩子都是黑色，也就是根到叶路径上不能出现连续红节点。
5. 从任意节点出发，到其所有后代 nil 叶子的简单路径包含相同数量的黑节点。

第三条容易被忽略。nil 不保存业务键，却参与颜色与黑高计算；若画图时省略它，证明里仍不能省略。

黑高如何控制整棵树

定义 $bh(x)$ 为从 $x$ 向下到任一后代 nil 的路径上，不包含 $x$ 的黑节点数。第五条保证这个数与选择哪条路径无关。

先证明：以 $x$ 为根、黑高为 $bh(x)$ 的子树，至少含有

个内部节点。对 nil，黑高为 $0$，结论是 $0$ 个内部节点。对内部节点，两个孩子的黑高至少是 $bh(x)-1$；把两个孩子的最小节点数相加，再加当前节点，就得到归纳结论。

再看一条根到叶的最长路径。因为红节点不能连续出现，除根外至少一半节点是黑色，所以根的黑高至少为 $h/2$。若树有 $n$ 个内部节点，则

整理得到

因此搜索、前驱、后继、最小值和最大值都有 $O(\log n)$ 的最坏时间。红黑树不要求左右子树高度只差一层，它允许更宽松的形状，换来更新时较少的旋转。

小测

旋转与红黑树插入修复

旋转是常数时间的局部指针变换，它保留 BST 的中序顺序。左旋 $x$ 的前提是 $x.right$ 不是 nil。令 $y=x.right$，依次完成：把 $y.left$ 接到 ；让 接替 在父节点下的位置；把 设为 。每次改孩子指针时都要同步父指针，根节点旋转时还要更新 。右旋完全对称。

交互演示：旋转改变形状，不改变顺序

点击按钮观察局部树如何变形。演示同时列出中序序列，便于核对旋转前后的有序性。

为什么新节点先染红

按 BST 规则插入新节点 $z$ 后，把它的两个孩子设为 nil 并将 $z$ 染红。若染黑，所有经过 $z$ 的路径都会多一个黑节点，黑高错误可能扩散到许多祖先；染红不会改变任何路径的黑节点数，只可能产生两类局部问题：$z$ 是红根，或 $z$ 与红色父节点相邻。

修复循环只在 z.parent 为红时执行。此时祖父一定存在且为黑。下面描述“父节点是祖父左孩子”的一半情形；另一半交换左右方向即可。

三种插入情形

叔叔为红。 把父亲和叔叔染黑，祖父染红，再令 z 指向祖父继续向上。三条相关路径的黑节点数不变；红红冲突可能被推到更高层。

叔叔为黑，z 是父亲的右孩子。 先令 z 指向父亲并左旋，把折线“左—右”转成直线“左—左”。这一步进入下一种情形，不单独结束。

叔叔为黑，z 是父亲的左孩子。 父亲染黑、祖父染红，再右旋祖父。红红冲突消失，黑高保持不变，循环结束。

RB-INSERT-FIXUP(T, z)  // 展示父节点在祖父左侧的分支
  while z.parent.color == 红：
    y = z.parent.parent.right
    if y.color == 红：
      z.parent.color = 黑
      y.color = 黑
      z.parent.parent.color = 红
      z = z.parent.parent
    else：
      if z == z.parent.right：
        z = z.parent
        LEFT-ROTATE(T, z)
      z.parent.color = 黑
      z.parent.parent.color = 红
      RIGHT-ROTATE(T, z.parent.parent)
  T.root.color = 黑

只有“叔叔为红”会让循环再次迭代，而且 z 每次上移两层，所以总时间为 $O(\log n)$。一次插入至多执行两次旋转；重新着色次数可以是 $O(\log n)$。

小测

红黑树删除修复追踪“额外的一重黑”

红黑删除先执行 BST 删除，但必须额外记住两个对象：实际被移走或搬动的节点 $y$，以及补到 $y$ 原位置的节点 $x$。若 $z$ 有两个孩子，$y$ 是 $z$ 的后继；$y$ 被移到 $$ 的位置并继承 的颜色，而 保存 在原位置的颜色。

若被移走的 $y$ 原本是红色，黑高不变，也不会凭空制造相邻红节点，不需修复。若 $y$ 原本是黑色，经过它原位置的路径少了一个黑节点。可以把这份缺口理解为压到 $x$ 身上的“额外一重黑”。它是修复算法的逻辑状态，不是第三种颜色；节点字段仍只有红或黑。

即使 $x$ 是共享 nil，也必须让 x.parent 指向它当前补位位置的父节点，否则修复无法找到兄弟。这里共享哨兵的父指针是过程中的临时导航信息。

四种删除情形

下面假设 $x$ 是父节点的左孩子，兄弟 $w=x.parent.right$。右孩子情形完全镜像。循环开始时，$x$ 是非根的双黑节点；$w$ 不可能是 nil，否则两侧黑高在删除前就已不同。

兄弟为红。 父节点必黑，兄弟的孩子必黑。把兄弟染黑、父亲染红，左旋父亲，再重新取兄弟。双黑没有消失，但新兄弟已经是黑色，问题转为后三种之一。

兄弟为黑，两个侄子都黑。 把兄弟染红，相当于从 $x$ 和 $w$ 两侧各去掉一重黑，再令 $x$ 上移到父节点。只有这种情形会把循环继续推向根。

兄弟为黑，近侄子红、远侄子黑。 这里近侄子是 w.left，远侄子是 w.right。近侄子染黑、兄弟染红，再右旋兄弟，把形状转成“远侄子红”的下一种情形。

兄弟为黑，远侄子红。 兄弟继承父节点颜色，父节点染黑，远侄子染黑，左旋父节点。两边黑高恢复，令 $x$ 指向根以结束循环。

交互演示：根据兄弟与侄子颜色选择情形

选择颜色后，演示会给出应执行的动作。为避免方向混乱，画面固定 $x$ 在左、兄弟在右。

删除主体沿树高寻找后继并改链接，修复中只有“双黑侄子”情形会反复上移。总时间是 $O(\log n)$，一次删除修复至多旋转三次。

小测

增强树把全局问题变成局部摘要

很多查询不需要发明一棵全新的树。更常见的做法是在一棵最坏高度为 $O(\log n)$ 的树上，为每个节点维护一个摘要字段。设计时可以按四步检查：选择底层结构；定义摘要；证明插入、删除和旋转能维护摘要；最后设计新查询。

一个实用判据是：若节点 $x$ 的摘要只依赖 $x$ 自身、$x.left$、$x.right$ 以及两个孩子的摘要，那么一次局部修改只会影响从修改点到根的祖先链。红黑树高度为 $O(\log n)$，因此沿祖先链重算不会改变插入和删除的渐进复杂度。旋转只改变两个节点的子树组成，很多摘要还能在 时间内修正。

顺序统计树维护子树规模

给每个节点增加 size，令哨兵的规模为 $0$：

要找当前子树第 $i$ 小的节点，先计算当前根在子树内的排名

若 $i=r$ 就返回 $x$；若 $i<r$ 就去左子树；若 $i>r$ 就去右子树寻找第 $i-r$ 小。每一步下降一层，所以查询时间为 。

OS-SELECT(x, i)
  r = x.left.size + 1
  if i == r：return x
  if i < r：return OS-SELECT(x.left, i)
  return OS-SELECT(x.right, i - r)

已知节点指针 $x$ 时，它在整棵树中的排名从 x.left.size + 1 开始。沿父指针上升：若当前节点是父亲的右孩子，父亲及父亲的整棵左子树都排在 $x$ 前面，需要加上 parent.left.size + 1；若当前节点是左孩子，不增加。到根时得到全局排名。

更新与旋转如何维护 size

插入下降时，沿搜索路径的 size 各加一，新节点规模为一。删除后，从实际移除位置向根重算或递减。以左旋 $x$、令 $y=x.right$ 为例，旋转前 $y$ 覆盖的节点集合与旋转后局部根覆盖的集合相同，所以先执行

y.size = x.size
x.size = x.left.size + x.right.size + 1

更新顺序不能颠倒：先重算 $x$，会丢掉旋转前整个局部子树的总规模。右旋对称。

小测

区间树用最大右端点安全剪枝

区间树维护一个动态的闭区间集合。闭区间 $i=[i.low,i.high]$ 与 $j=[j.low,j.high]$ 重叠，当且仅当

端点相接的 [2,5] 与 [5,8] 也算重叠。若业务使用开区间或半开区间，等号是否成立必须随语义调整，不能原样复制闭区间判断。

底层红黑树按区间左端点 low 排序。每个节点保存

其中哨兵的 max 可设为 $-\infty$。这个字段只依赖节点和两个孩子，所以插入、删除沿祖先链更新，旋转只需重新计算参与旋转的两个节点。

搜索为何只走一条路

搜索查询区间 $q$ 时，若当前区间与 $q$ 重叠就返回。否则，只要左子树存在且 left.max >= q.low，就向左；其余情况向右。

INTERVAL-SEARCH(T, q)
  x = T.root
  while x != nil 且 x.int 与 q 不重叠：
    if x.left != nil 且 x.left.max >= q.low：
      x = x.left
    else：
      x = x.right
  return x

向右的理由最直观：若 left.max < q.low，左子树中每个区间的右端点都在查询左端点之前，因此左侧绝不可能重叠。

向左看似只知道“左侧可能重叠”，为什么可以舍弃右侧？设左子树中达到 left.max 的区间为 $i'$。若左侧最终没有任何重叠，而 i'.high >= q.low，那么不重叠只能说明 $q.high < i'.low$。右子树所有区间的左端点又不小于 $i'.low$，所以它们也都在 的右边。也就是说，若左侧选择失败，右侧同样不可能成功。搜索因此能安全地只沿一条路径下降，最坏时间为 。

交互演示：观察 max 如何排除整棵子树

拖动查询区间。演示会按区间树的决策顺序寻找任意一个重叠项，并解释每次向左或向右的理由。

小测

B 树把一个节点扩展成一页

红黑树把一次比较对应到一个二叉节点。若数据远大于内存，真正昂贵的常常是把一个存储页读入内存，而不是页内做几十或几百次比较。B 树让一个节点容纳许多有序键和孩子指针，使一次页读取完成一次多路分支，显著缩短根到叶的页数。

分析 B 树时应分开两种成本：

• 页访问次数：读写了多少个外存页，主要由树高决定。
• CPU 时间：在页内移动、比较了多少个键，受节点容量和页内搜索方式影响。

节点通常按页大小设计。根可以长期保留在内存；访问下一层前读取相应孩子页，修改节点后再写回。即使底层介质不含机械部件，“成块传输比逐条随机读取更合算”的页级模型仍适用于数据库索引和文件系统。

最小度数定义容量边界

设 B 树的最小度数为整数 $t\ge2$。节点 $x$ 有 $x.n$ 个非降序键；内部节点有 $x.n+1$ 个孩子。第 $i$ 个键把第 $i$ 与第 棵子树的键域分开。

合法 B 树还满足：

• 所有叶子位于同一深度。
• 除根外，每个节点至少有 $t-1$ 个键；内部节点至少有 $t$ 个孩子。
• 每个节点至多有 $2t-1$ 个键、$2t$ 个孩子；达到上限称为满节点。
• 非空根至少有一个键；根若不是叶子，至少有两个孩子。

当 $t=2$ 时，每个非根节点有 1..3 个键，内部节点有 2..4 个孩子，这就是常说的 2-3-4 树。

高度上界来自最低装载率

高度为 $h$ 的最稀疏非空 B 树，根有一个键和两个孩子；深度 $1$ 有至少两个节点，此后每层节点数至少再乘 $t$。除根外每个节点至少有 $t-1$ 个键，因此

于是

分支因子越大，对数的底越大，树越矮。这正是 B 树减少页访问的核心。

小测

B 树搜索与插入坚持单向下行

B 树搜索在节点内找到最小下标 $i$，使得 $k\le x.key_i$；若相等就返回当前位置。若不等且 $x$ 是叶子，搜索失败；否则读取第 $i$ 个孩子并继续。访问节点形成一条根到叶路径，因此页读取次数为

若在每个节点中线性扫描至多 $2t-1$ 个键，CPU 时间为 $O(th)=O(t\log_t n)$；若页内用二分查找，每层比较 $O(\log t)$ 次，总比较数可写成 。

分裂满节点

满孩子 $y$ 有 $2t-1$ 个键。分裂时，把中位键 $y.key_t$ 提升到非满父节点；左半仍由 $y$ 保存前 $t-1$ 个键，新节点 保存后 个键。若 不是叶子，它的前 个孩子留在 ，后 个孩子转给 。父节点多一个键和一个孩子。

分裂本身在页内搬移 $\Theta(t)$ 个键或指针，只需常数次页写入。若根已满，先创建空的新根，把旧根设为它的孩子，再分裂旧根。B 树只在根分裂时增高，而且是在顶部增高。

为什么要“下去之前先分裂”

朴素插入先走到满叶子，才发现没有位置，只能回到父节点；若父节点也满，还要继续回溯。自顶向下插入采用更强的不变式：绝不下降到满节点。

每次准备进入孩子前，先检查孩子是否满。若满，立即分裂，再根据待插键与刚提升的中位键比较，选择左半或右半继续。到达叶子时，它一定非满，直接把键插入有序位置。这样一次插入只向下走一遍。

B-TREE-INSERT(T, k)
  若根已满：
    创建空的新根 s
    s.child[0] = 旧根
    分裂 s 的第 0 个孩子
  INSERT-NONFULL(T.root, k)
 
INSERT-NONFULL(x, k)
  若 x 是叶子：把 k 插到有序位置并写回
  否则：
    找到目标孩子 i 并读取它
    若 child[i] 已满：
      分裂 child[i]
      重新比较 k 与提升到 x 的中位键
    下降到确定的非满孩子

交互演示：最小度数为 2 的分裂

依次插入键，观察满根如何在下降前分裂。演示只展示结构变化，所有节点都遵守 1..3 个键的容量边界。

插入访问 $O(h)$ 个页，CPU 时间为 $O(th)$。尾递归版本可以改写为循环，使任一时刻只需在内存中保留常数个相关页。

小测

B 树删除在下降前避免孩子下溢

B 树删除比插入多一个难点：键可能位于内部节点，而且下降后不能让非根节点少于 $t-1$ 个键。为实现单向下行，递归入口采用比合法性更强的条件：每次递归进入节点 $x$ 时，$x$ 至少有 $t$ 个键。 这样即使在子树中删掉一个键，节点仍至少保留 $t-1$ 个键。

待删键就在当前节点

若当前节点是叶子，直接移除键并紧缩数组。

若当前节点是内部节点，设待删键 $k$ 左右相邻孩子为 $y$ 和 $z$：

1. 若 $y$ 至少有 $t$ 个键，用 $k$ 的前驱 $k'$ 替换 $k$，再递归删除 $y$ 中的 $$。

前驱是左子树最右侧的键，后继是右子树最左侧的键。内部键替换可能需要在返回时写回当前页，这是删除中少数需要回到上层完成赋值的地方；查找路径仍只有一条。

待删键不在当前节点

先确定可能包含 $k$ 的孩子 $c$。若 $c$ 已有至少 $t$ 个键，可直接下降。若它只有 $t-1$ 个键，下降前必须补强：

• 若某个相邻兄弟至少有 $t$ 个键，就向兄弟借一个。父节点的分隔键下移到 $c$，兄弟靠近 $c$ 的键上移到父节点；若是内部节点，还要把相应孩子指针一起转移。
• 若相邻兄弟也只有 $t-1$ 个键，就把 $c$、父节点的一个分隔键和一个兄弟合并，再下降到合并节点。

借键是三方轮转，不是把兄弟键直接塞进孩子。少了“父键下移、兄弟键上移”这一步，父节点的分隔范围会失真。

根是唯一允许例外的节点

合并可能让内部根失去最后一个键。此时根只剩一个孩子，就删除空根，让唯一孩子成为新根，树高减一。空树根可以是没有键的叶子。除根以外，任何节点都不能通过“临时少一个键，稍后再修”来逃避容量下界。

删除每下降一层只做常数次页读写，所以页访问是 $O(h)=O(\log_t n)$；页内移动至多 $O(t)$ 个键或指针，CPU 时间为 $O(th)$。

小测

选型时先看瓶颈，再看不变式成本

这些树没有一个在所有场景中都最好。它们解决的是不同的瓶颈。

实现完成后，不要只测“能不能搜到”。更有效的测试是为不变式写检查器：BST 检查上下界；AVL 自底向上核对高度与平衡因子；红黑树检查根、红红相邻和每条路径黑高；增强树重算摘要并对比；B 树检查键数量边界、分隔范围、孩子数以及所有叶子深度。

随机插入删除能覆盖大量形状，但还应专门构造边界序列：单调键、反复删除根、红黑删除的四类兄弟颜色、B 树连续根分裂、向左右兄弟借键、合并后根收缩。复杂树的错误通常不是发生在“普通路径”，而是发生在一次指针重接后，某个看似无关的摘要、父指针或哨兵状态没有同步。

小测