量化交易中文教材

第 12 章 二叉搜索树与红黑树

本章合并原书第 12 章（二叉搜索树）与第 13 章（红黑树）。散列表回答"某个关键字在不在、在哪里"，但回答不了"比它大的下一个是谁""最小的是谁""落在 \([a,b]\) 里的有哪些"。订单簿的价格档位、按时间戳的 as-of 查找、滚动窗口里的有序样本，都需要有序动态集合。二叉搜索树给出这类操作的统一框架，红黑树则保证它在任何输入顺序下都不会退化。

学习目标

  1. 掌握二叉搜索树性质，会写中序遍历、搜索、最小/最大、后继/前驱、插入、删除，知道它们都是 \(O(h)\)。
  2. 理解 TRANSPLANT 与删除的四种情况，以及原书为何坚持"删除的就是传入的那个结点"。
  3. 理解随机构造二叉搜索树期望高度 \(O(\lg n)\) 的证明思路（指数高度 + Jensen 不等式），并知道它在单边行情这类有序输入下会失效。
  4. 记住红黑树的五条性质，能证明 \(n\) 个内部结点的红黑树高度不超过 \(2\lg(n+1)\)。
  5. 理解旋转，以及插入/删除修复的情况划分与代价：\(O(\lg n)\) 时间，至多 2 次/3 次旋转。
  6. 能用平衡树实现订单簿价格档位和 as-of 查找，并能在"平衡树 / tick 数组 / 排序数组 + 二分"之间做工程选择。

读前导读

这一章在解决什么问题。 订单簿的卖方一侧有几百个价位，每秒都有价位出现（新挂单）和消失（被吃光或撤光）。你需要随时回答："最低卖价是多少？""它上面一档是多少？""10.05 到 10.20 之间有哪些价位？"上一章的散列表能回答"10.05 这个价位在不在"，但它把数据打散了，回答不了"下一档是谁"。排序数组能回答，但插入一个新价位要把后面所有价位往后挪。二叉搜索树兼顾两者：数据按大小组织，又像链表一样插入删除只改几个指针。

二叉搜索树的思路你其实每天都在用：猜价格游戏——"比 10 元高还是低？""高。""比 15 元高还是低？""低。"……每问一次就排除一半。把所有价位组织成这样一棵"问答树"，根是第一个问题，左边是"更低"、右边是"更高"，找任何价位只需要走从根往下的一条路径，步数等于树的高度。

问题在于高度取决于插入顺序。单边上涨的行情里，新价位一个比一个高，每次都挂在最右边，树长成一条斜线，高度等于价位数，"问答"退化成从头数到尾。红黑树给每个结点涂上红或黑，用五条颜色规则逼着树保持矮胖：不管行情怎么走，高度永远不超过 \(2\lg(n+1)\)，2000 个价位最多 22 层。规则一旦被插入或删除打破，就用"重新涂色"和"旋转"在局部修好。

需要先想起来的数学。

  • 对数与树高的关系。 每层结点数最多翻倍，所以高度为 \(h\) 的二叉树最多有 \(2^{h+1}-1\) 个结点；反过来，\(n\) 个结点至少要 \(\lfloor\lg n\rfloor\) 层。\(n=1000\) 时约 10 层，\(n=10^6\) 时约 20 层。见 第 00 册第 04 章 级数与收敛 中的指数与对数。
  • 数学归纳法。 证明"对所有高度都成立"：先证最矮的情况，再证"若对矮的成立，则对高一层的也成立"。引理 13.1 就是这样证的。见 第 00 册第 08 章 读懂数学证明与符号。
  • 凸函数与 Jensen 不等式。 凸函数是"向上弯"的函数，如 \(2^x\)、\(x^2\)。Jensen 不等式：对凸函数 \(f\)，\(f(E[X])\le E[f(X)]\)。例：\(X\) 等可能取 0 或 2，\(E[X]=1\)，\(2^{E[X]}=2\)，而 \(E[2^X]=(1+4)/2=2.5\)。你在凸性调整（债券凸性让价格的期望高于按期望收益率算出的价格）中见过同一现象。见 第 00 册第 07 章 概率中的分析工具。
  • 组合数 \(\binom nk\)。 从 \(n\) 个里选 \(k\) 个的方法数，\(\binom n3=\frac{n(n-1)(n-2)}6\)。12.1.4 节用它做上界，你只需知道 \(\binom{n+3}3\) 大约是 \(n^3/6\)，是 \(n\) 的多项式。

怎么读这一章。 12.1.1–12.1.3 必读，尤其是"所有操作都是 \(O(h)\)"这个结论和后继的两种情况。12.1.4 的证明技巧精巧但第一次可以只看结论和最后一段"行情数据不是随机顺序"。12.2.1 的五条性质和引理 13.1 必读，它们解释了"为什么平衡"。12.2.3、12.2.4 的修复情况表第一次只需理解"插入至多 2 次旋转、删除至多 3 次"以及下面讲解框里的直觉，具体情况不必背。12.2.5 浏览即可。12.3 节量化实战必读，尤其是"单边行情下普通 BST 高度 1999"这个实验和 12.3.2 的工程选择。

12.1 二叉搜索树

12.1.1 定义与中序遍历

**二叉搜索树（binary search tree, BST）**用链式结构表示：每个结点有 key、卫星数据，以及 left、right、p 三个指针。它满足

二叉搜索树性质：若 \(y\) 在 \(x\) 的左子树中，则 \(y.key\le x.key\)；若 \(y\) 在 \(x\) 的右子树中，则 \(y.key\ge x.key\)。

同一集合可以对应许多不同形状的 BST（原书图 12.1：键 2,5,5,6,7,8 可以组成高度 2 的树，也可以组成高度 4 的树）。几乎所有操作的时间都与树高 \(h\) 成正比，所以形状至关重要。

白话解释：用卖方价位 10.01、10.02、10.03、10.04、10.05、10.06、10.07 举例。一种好的摆法：根是 10.04；它左边挂 10.02（左边再挂 10.01、右边挂 10.03），右边挂 10.06（左 10.05、右 10.07）。任取一个结点，左边整片都比它小、右边整片都比它大——这就是 BST 性质。找 10.05：比 10.04 大往右，比 10.06 小往左，到了，走 2 步。若按 10.01、10.02、…… 的顺序依次插入，每个新价位都比已有的大，全部挂在右边，树变成 7 层的一条斜线，找 10.07 要走 6 步。同样 7 个价位，两种形状，代价差 3 倍；价位数越多，差距越大。 术语："子树"是某个结点及其下面挂着的全部结点；"树高"是从根走到最远叶子的边数；"中序遍历"是"先左、再自己、再右"的访问顺序，对 BST 恰好按从小到大输出。

**中序遍历（inorder tree walk）**先递归输出左子树，再输出根，再递归输出右子树，按序输出全部关键字：

def INORDER_TREE_WALK(x):
    if x is not NIL:
        INORDER_TREE_WALK(x.left)
        print(x.key)
        INORDER_TREE_WALK(x.right)

定理 12.1：对 \(n\) 个结点的子树，中序遍历用 \(\Theta(n)\) 时间。（下界显然；上界用代入法证 \(T(n)\le(c+d)n+c\)。）

顺带一个推论（习题 12.1-5）：既然中序遍历 \(O(n)\) 就能输出有序序列，任何基于比较、从任意序列建 BST 的算法在最坏情况下都需要 \(\Omega(n\lg n)\)，否则就违反了比较排序的下界。

12.1.2 查询

定理 12.2：SEARCH、MINIMUM、MAXIMUM、SUCCESSOR、PREDECESSOR 在高度为 \(h\) 的 BST 上都是 \(O(h)\)。

def ITERATIVE_TREE_SEARCH(x, k):
    while x is not NIL and k != x.key:
        x = x.left if k < x.key else x.right
    return x

def TREE_MINIMUM(x):
    while x.left is not NIL: x = x.left
    return x

def TREE_SUCCESSOR(x):
    if x.right is not NIL:
        return TREE_MINIMUM(x.right)          # 情况 1：右子树的最左结点
    y = x.p
    while y is not NIL and x == y.right:      # 情况 2：向上，直到"从左边上来"
        x, y = y, y.p
    return y

搜索沿一条从根向下的路径走，例如原书图 12.2 中找 13 的路径是 15→6→7→13。后继有两种情况：若 \(x\) 有右子树，后继是右子树中最左的结点（15 的后继是 17）；否则后继是 \(x\) 的最低祖先、且该祖先的左孩子也是 \(x\) 的祖先——从 \(x\) 往上走，直到某个结点是其父结点的左孩子，那个父结点就是后继（13 的后继是 15）。值得注意的是，找后继不需要比较关键字，只用树结构。

白话解释：后继就是"上一档"。用上面 7 个价位的平衡摆法：10.04 的上一档？它有右子树（10.06 那片），上一档一定在右边那片里，而且是那片里最小的，即一路往左走到底：10.05。10.03 的上一档？它没有右子树，说明比它大的都在"上面"。往上走：10.03 是 10.02 的右孩子（从右边上来，说明 10.02 比它小，继续走）；10.02 是 10.04 的左孩子（从左边上来，说明 10.04 比它大），停，答案是 10.04。规则就是"一直往上，直到第一次从左边上来"。

一个实用结论（习题 12.2-8）：从任意结点出发连续做 \(k\) 次 SUCCESSOR，总时间是 \(O(k+h)\)，而不是 \(O(kh)\)。这正是"从最优价开始往外遍历前 \(k\) 档"的代价。

12.1.3 插入与删除

插入沿路径向下找到一个 NIL 位置挂上新结点，需要一个"尾随指针" \(y\) 记录父结点：

def TREE_INSERT(T, z):
    y, x = NIL, T.root
    while x is not NIL:
        y = x
        x = x.left if z.key < x.key else x.right
    z.p = y
    if y is NIL:          T.root = z
    elif z.key < y.key:   y.left = z
    else:                 y.right = z

删除结点 \(z\) 有三种基本情形：无孩子直接摘掉；一个孩子就把孩子提上来；两个孩子则找后继 \(y\)（在右子树中，且没有左孩子）顶替 \(z\)。实际代码借助 TRANSPLANT（用以 \(v\) 为根的子树替换以 \(u\) 为根的子树）分成四种情况：

def TRANSPLANT(T, u, v):
    if u.p is NIL:          T.root = v
    elif u == u.p.left:     u.p.left = v
    else:                   u.p.right = v
    if v is not NIL:        v.p = u.p

def TREE_DELETE(T, z):
    if z.left is NIL:   TRANSPLANT(T, z, z.right)        # (a) 无左孩子
    elif z.right is NIL: TRANSPLANT(T, z, z.left)        # (b) 只有左孩子
    else:
        y = TREE_MINIMUM(z.right)                         # 后继
        if y.p != z:                                      # (d) 后继不是 z 的右孩子
            TRANSPLANT(T, y, y.right)
            y.right = z.right; y.right.p = y
        TRANSPLANT(T, z, y)                               # (c)/(d) 共同部分
        y.left = z.left; y.left.p = y

白话解释：删除最难的是"有两个孩子"的结点，比如上面摆法里的根 10.04 所在价位被撤光。不能简单拿掉，否则左右两片就断了。做法是找一个能"坐上这个位置"且不破坏左小右大的继任者——10.04 的后继 10.05：它比左边整片都大，又是右边整片里最小的，坐到根上正合适。10.05 原来的位置怎么办？后继一定没有左孩子（否则左孩子更小、才该是后继），所以把它的右子树（如果有）提上来补位即可，这就是情况 (d) 先做的那次 TRANSPLANT。TRANSPLANT 本身就是"让父结点改认一个新孩子"。

定理 12.3：INSERT 与 DELETE 在高度为 \(h\) 的 BST 上都是 \(O(h)\)。

原书章末注记特别说明了一个工程细节：许多教材删除两个孩子的结点时，是把后继的关键字和卫星数据复制到 \(z\)，再删掉后继结点。这样实际被释放的可能不是调用者传入的那个结点；若程序别处还持有指向后继结点的指针（比如订单 ID 索引指向树结点），就会留下指向已删除结点的陈旧指针（stale pointer）。本书的写法保证"删 \(z\) 就是删 \(z\)"，这在"散列表索引 + 树"组合的系统里正是需要的。

12.1.4 随机构造的二叉搜索树

树高在 \(\lfloor\lg n\rfloor\) 与 \(n-1\) 之间。按严格递增顺序插入 \(n\) 个键，得到的是一条高度 \(n-1\) 的链。平均情况又如何？定义 \(n\) 个不同关键字上的随机构造二叉搜索树（randomly built BST）：按随机顺序插入空树，\(n!\) 种排列等可能。

定理 12.4：随机构造的 BST 期望高度为 \(O(\lg n)\)。

证明思路. 直接分析高度 \(X_n\) 的期望很难，因为高度涉及 \(\max\)。改为分析指数高度 \(Y_n=2^{X_n}\)。

  1. 设根的秩为 \(R_n\)，等可能取 \(1..n\)。若 \(R_n=i\)，左右子树分别是 \(i-1\) 和 \(n-i\) 个键上的随机构造树，于是 \(Y_n=2\max(Y_{i-1},Y_{n-i})\)，约定 \(Y_0=0\)、\(Y_1=1\)。
  2. 用指示变量 \(Z_{n,i}=I\{R_n=i\}\)，且它与子树的形状独立，得
    \[E[Y_n]=\frac2n\sum_{i=1}^nE[\max(Y_{i-1},Y_{n-i})]\le\frac2n\sum_{i=1}^n\big(E[Y_{i-1}]+E[Y_{n-i}]\big)=\frac4n\sum_{i=0}^{n-1}E[Y_i].\]
  3. 用代入法和恒等式 \(\sum_{i=0}^{n-1}\binom{i+3}3=\binom{n+3}4\) 证明 \(E[Y_n]\le\frac14\binom{n+3}3\)。
  4. \(2^x\) 是凸函数，由 Jensen 不等式 \(2^{E[X_n]}\le E[Y_n]\le\frac{(n+3)(n+2)(n+1)}{24}\)，取对数得 \(E[X_n]=O(\lg n)\)。\(\square\)

推导拆解：为什么要绕道"指数高度"？ (1) 高度的递推是 \(X_n=1+\max(X_{i-1},X_{n-i})\)。对 \(\max\) 取期望很难，最自然的放缩 \(\max(a,b)\le a+b\) 用在高度上太粗：两棵高 10 的子树会被估成 20，误差一层层累积，最后只能证出 \(O(n)\)。 (2) 换成 \(Y=2^X\) 后，\(\max(2^a,2^b)\le2^a+2^b\) 就很准了：\(2^{10}+2^{10}=2^{11}\)，只多估了"1 层"。所以先在指数尺度上放缩，误差变得可控。递推 \(Y_n=2\max(\cdot)\) 中的 2 就是"多了根这一层"，对应 \(2^{1+X}=2\cdot2^X\)。 (3) 第 2 步的等号右边：\(\sum_i(E[Y_{i-1}]+E[Y_{n-i}])\) 中，\(i-1\) 和 \(n-i\) 都各自取遍 \(0..n-1\)，所以每个 \(E[Y_k]\) 出现两次，\(\frac2n\times2=\frac4n\)。 (4) 第 4 步：得到 \(E[2^{X_n}]\) 是 \(n\) 的三次多项式量级后，用 Jensen（\(2^x\) 是凸函数）得 \(2^{E[X_n]}\le E[2^{X_n}]\le Cn^3\)，两边取 \(\lg\)：\(E[X_n]\le3\lg n+\text{常数}\)，即 \(O(\lg n)\)。 这和你在固定收益里的经验一致：直接对收益率求期望再算价格，与先算价格再求期望不相等，差额来自凸性；这里我们正是利用这个不等号的方向得到上界。

技巧值得记住：用 \(\max(a,b)\le a+b\) 放缩，代价是把对数量变成指数量；再用 Jensen 回到原量。 思考题 12-3 还给出另一个视角：随机 BST 的构造过程与随机快速排序做的比较一一对应，每个结点就是划分其子树的主元，因此平均深度也是 \(O(\lg n)\)。

但"随机构造"是对输入顺序的假设。行情数据恰恰不是随机顺序的：单边上涨时，新出现的卖价档位一个比一个高，插入顺序几乎有序，普通 BST 会退化成链。这就是需要平衡树的直接原因，下面的实验会看到差距有多大。

12.2 红黑树

**红黑树（red-black tree）**是许多"平衡"搜索树方案之一，保证基本操作在最坏情况下 \(O(\lg n)\)。C++ 的 std::map/std::set、Java 的 TreeMap 通常都用红黑树实现。

12.2.1 五条性质

红黑树是每个结点多一位**颜色（color）**的 BST。把所有 NIL 看作叶（外部结点），带关键字的结点为内部结点。它满足：

  1. 每个结点是红色或黑色；
  2. 根是黑色；
  3. 每个叶（NIL）是黑色；
  4. 红结点的两个孩子都是黑色（不能有连续两个红结点）；
  5. 对每个结点，从它到其所有后代叶的简单路径上，黑结点数目相同。

实现上用一个黑色的哨兵 \(T.nil\) 代表所有 NIL 以及根的父结点。从结点 \(x\)（不含 \(x\)）到叶的路径上的黑结点数称为 \(x\) 的黑高（black-height） \(bh(x)\)，由性质 5 它是良定义的。

白话解释：五条性质里真正起作用的是 4 和 5，可以这样记。把黑结点想成"承重墙"，红结点想成"夹层"。性质 5 说：从任何结点往下走到底，不论走哪条路，经过的承重墙数量都一样——黑色骨架是完全平衡的。性质 4 说：夹层不能连着建两层，每个红结点下面必须紧跟黑结点。于是最长的路径是"黑红黑红……"交替，最短的是"全黑"，两者黑结点数相同，所以最长不会超过最短的两倍。性质 1–3 只是约定（颜色只有两种、根和 NIL 都算黑），方便叙述。 "良定义"的意思是：这个数不依赖于你选哪条路径去数，所以可以当成结点的一个属性来用。

引理 13.1：有 \(n\) 个内部结点的红黑树，高度至多 \(2\lg(n+1)\)。

证明. 先对高度归纳证明：以 \(x\) 为根的子树至少含 \(2^{bh(x)}-1\) 个内部结点。高度为 0 时 \(x\) 是叶，\(2^0-1=0\) 成立。否则 \(x\) 有两个孩子，每个孩子的黑高是 \(bh(x)\) 或 \(bh(x)-1\)，由归纳假设各至少有 \(2^{bh(x)-1}-1\) 个内部结点，合计至少 \(2(2^{bh(x)-1}-1)+1=2^{bh(x)}-1\)。

再由性质 4，从根到叶的任何路径上至少一半结点（不含根）是黑色，所以根的黑高至少 \(h/2\)，于是 \(n\ge2^{h/2}-1\)，即 \(h\le2\lg(n+1)\)。\(\square\)

推导拆解：证明分两半。 前半（归纳）："黑高为 \(b\) 的子树至少有 \(2^b-1\) 个内部结点"。直觉：只看黑色骨架，它是一棵每条路径都有 \(b\) 个黑结点的满树，满二叉树 \(b\) 层有 \(2^b-1\) 个结点。归纳步里"孩子的黑高是 \(bh(x)\) 或 \(bh(x)-1\)"：孩子是红的，不计入，黑高与 \(x\) 相同；孩子是黑的，它本身被计入了 \(x\) 的黑高，所以它自己的黑高少 1。取较小的那个就得到下界。最后的 \(+1\) 是 \(x\) 自己。 后半（性质 4）：高度 \(h\) 的路径上，红结点不能相邻，所以至少一半是黑的，根的黑高 \(\ge h/2\)。代入前半：\(n\ge2^{h/2}-1\)。移项 \(2^{h/2}\le n+1\)，取 \(\lg\) 得 \(h/2\le\lg(n+1)\)。 数值：\(n=2000\) 时 \(h\le2\lg2001\approx21.9\)；而普通 BST 最坏可达 1999。

这个证明说明了平衡的来源：性质 5 让"黑色骨架"完全平衡，性质 4 保证红结点最多让路径长度翻倍（习题 13.1-5：从任一结点出发，最长路径至多是最短路径的两倍）。因此第 12.1 节的所有查询在红黑树上都是 \(O(\lg n)\)。

习题 13.1-4 揭示了红黑树的另一个身份：把每个红结点并入它的黑父结点，就得到一棵所有叶深度相同、结点度数为 2、3、4 的树——2-3-4 树，它是 B 树（本册第 18 章）的特例。

12.2.2 旋转

插入删除会破坏红黑性质，修复时需要改颜色，也需要改结构。结构修改用旋转（rotation）——一种保持 BST 性质的 \(O(1)\) 局部操作。

左旋（left rotation）作用于结点 \(x\)（其右孩子 \(y\ne T.nil\)）：\(y\) 成为子树新根，\(x\) 成为 \(y\) 的左孩子，\(y\) 原来的左子树改挂为 \(x\) 的右子树。右旋是其逆操作。设三棵子树为 \(\alpha,\beta,\gamma\)，旋转前后中序次序都是 \(\alpha<x<\beta<y<\gamma\)。

def LEFT_ROTATE(T, x):
    y = x.right
    x.right = y.left
    if y.left is not T.nil: y.left.p = x
    y.p = x.p
    if x.p is T.nil:      T.root = y
    elif x == x.p.left:   x.p.left = y
    else:                 x.p.right = y
    y.left = x
    x.p = y

白话解释：旋转像调整一根挂了三串钥匙的晾衣杆的提起点。原来提着 \(x\)，\(y\) 挂在 \(x\) 右下方；左旋就是改为提着 \(y\)，\(x\) 落到 \(y\) 左下方。子树 \(\beta\) 原来在 \(y\) 左边（比 \(y\) 小、比 \(x\) 大），现在挂到 \(x\) 右边，位置关系仍然是"比 \(x\) 大、比 \(y\) 小"。从左往右读一遍，顺序始终是 \(\alpha,x,\beta,y,\gamma\)，大小关系一点没变，只是"谁在上面"换了。效果是：右边那串变短一层，左边那串变长一层——这正是用来纠正"右边太重"的工具。

旋转只改指针，不改其他属性。还有两个事实：一棵 \(n\) 结点 BST 上恰有 \(n-1\) 种可能的旋转（每条边一种，习题 13.2-2）；任意两棵 \(n\) 结点的 BST 可以通过 \(O(n)\) 次旋转互相转换（习题 13.2-4）。

12.2.3 插入（压缩讲解）

做法：先像普通 BST 一样插入新结点 \(z\)，染成红色，再调用 RB-INSERT-FIXUP。为什么染红？染黑必然破坏性质 5（经过 \(z\) 的路径多一个黑结点）；染红只可能破坏性质 2（\(z\) 是根）或性质 4（\(z\) 的父结点也是红的），而这两种都容易修。

修复循环在 \(z.p\) 为红时继续。此时 \(z.p\) 不是根，所以祖父 \(z.p.p\) 存在且为黑。以 \(z.p\) 是祖父的左孩子为例（另一侧对称），看叔结点 \(y=z.p.p.right\)：

情况 条件 动作 结果
1 叔结点红 父、叔染黑，祖父染红，\(z\leftarrow\) 祖父 问题上移两层，可能继续循环
2 叔黑，\(z\) 是右孩子（"内侧"） \(z\leftarrow z.p\)，左旋 \(z\) 转为情况 3
3 叔黑，\(z\) 是左孩子（"外侧"） 父染黑，祖父染红，右旋祖父 不再有连续红结点，循环结束

最后把根染黑（修复性质 2）。正确性由一个三条的循环不变式保证：\(z\) 是红的；若 \(z.p\) 是根则 \(z.p\) 是黑的；树至多违反一条性质，且只能是性质 2（\(z\) 是红根）或性质 4（\(z\) 与 \(z.p\) 都红）。

原书图 13.4 的例子：插入 4 后，4 与父结点 5 都红、叔结点 8 红，属情况 1，重新着色后 \(z\) 上移到 7；7 与父 2 都红、叔 14 黑、7 是右孩子，属情况 2，左旋 2；此时属情况 3，重新着色并右旋 11，7 成为新根。

白话解释：新结点 \(z\) 染红后，唯一可能的毛病是"它和父结点都是红的"（两层夹层连在一起）。祖父一定是黑的（否则原树就已违规），所以要看的就是叔叔： 叔叔红（情况 1）：父辈两兄弟都是红的。把父、叔都改黑，祖父改红——从祖父往下看，每条路径的黑结点数没变，但"红"被往上推了两层，可能和曾祖父撞色，于是对祖父重复同样的检查。这一步只涂色、不动结构。 叔叔黑（情况 2、3）：不能靠涂色解决，因为父染黑会让父那边比叔那边多一个黑结点。这时用一次旋转把父结点提到祖父的位置，再把它涂黑、原祖父涂红，两边黑结点数相等，问题彻底解决。情况 2 是"\(z\) 在内侧"，先转一下把它变成"外侧"，再按情况 3 处理。

代价：只有情况 1 会让循环继续，每次 \(z\) 上移两层，所以循环 \(O(\lg n)\) 次；情况 2、3 执行后循环结束，所以一次插入至多 2 次旋转。

12.2.4 删除（压缩讲解）

删除基于 TREE-DELETE，多做三件事：记录实际被删除或被移动的结点 \(y\)（\(z\) 少于两个孩子时 \(y=z\)，否则 \(y\) 是后继）及其原始颜色；记录移到 \(y\) 原位置的结点 \(x\)（可能是 \(T.nil\)，此时也要正确设置 \(x.p\)，所以 RB-TRANSPLANT 无条件赋值 \(v.p=u.p\)）；若 \(y\) 有两个孩子的情形，\(y\) 继承 \(z\) 的颜色。

若 \(y\) 原来是红色，删除或移动它不破坏任何性质：黑高不变，不会出现相邻红结点，根仍是黑的。若 \(y\) 原来是黑色，经过它的路径少了一个黑结点。原书的处理方法很巧妙：认为 \(x\) 带着一重"额外的黑"（extra black）——把 \(y\) 的黑色推给 \(x\)，性质 5 就仍然成立，代价是 \(x\) 变成了"双重黑"或"红黑"，违反性质 1。RB-DELETE-FIXUP 的任务就是把这重额外的黑向上推，直到能消掉它。

金融直觉："额外的黑"很像会计里的暂记挂账。删掉一个黑结点后，经过它的路径"少了一个黑"，账不平了。与其立刻全树调整，不如先把这个缺口记在 \(x\) 名下（\(x\) 多背一重黑），让性质 5 在账面上保持平衡，然后逐步清理这笔挂账：如果 \(x\) 本来是红的，直接把它涂黑，挂账冲销；如果能从兄弟那边"借"一个黑（情况 3、4，通过旋转把兄弟子树的结点挪过来），挂账就地消化；借不到（情况 2，兄弟和侄子全黑），就把兄弟也"减一重黑"（涂红），两边一起少一个，挂账转移到父结点名下，再往上处理。每次上移一层，最多到根，所以 \(O(\lg n)\)。

以 \(x\) 是左孩子为例，看兄弟 \(w\)：

情况 条件 动作 结果
1 \(w\) 红 \(w\) 染黑，父染红，左旋父结点 新兄弟为黑，转入 2/3/4
2 \(w\) 黑，两个侄子都黑 \(w\) 染红，\(x\leftarrow x.p\) 额外的黑上移一层
3 \(w\) 黑，近侄红、远侄黑 交换 \(w\) 与近侄颜色，右旋 \(w\) 转为情况 4
4 \(w\) 黑，远侄红 \(w\) 取父色，父与远侄染黑，左旋父 额外的黑消去，循环结束

若 \(x\) 本身是"红黑"（颜色属性为红），循环直接结束，最后一行把它染黑即可。只有情况 2 可能让循环继续且不做旋转，所以删除的修复是 \(O(\lg n)\) 时间、至多 3 次旋转。

在实际编程中，红黑树的修复代码极易写错（本章的示例代码在开发时也踩过"插入返回值在 fixup 后被改写"的坑），所以一定要配一个性质检查器，在随机增删下反复验证五条性质和 BST 性质——下面的实战代码就是这样做的。

12.2.5 其他平衡树（了解即可）

原书思考题和章末注记介绍了几种替代方案，它们在量化系统里也都能见到：

  • AVL 树（思考题 13-3）：每个结点左右子树高度差至多 1，高度为 \(h\) 的 AVL 树至少有 \(F_h\) 个结点（Fibonacci 数），因此高度 \(O(\lg n)\)；插入只需 \(O(1)\) 次旋转。比红黑树更"严格"平衡，查询略快，修改略慢。
  • 树堆（treap）（思考题 13-4）：每个结点有随机优先级，键满足 BST 性质、优先级满足最小堆序；等价于按优先级顺序插入普通 BST，所以无论输入顺序如何，形状都是"随机构造"的，期望高度 \(\Theta(\lg n)\)，且插入的期望旋转次数小于 2。实现比红黑树简单得多，本册第 14 章的实战代码就用它做扩张。
  • 伸展树（splay tree）：无显式平衡条件，每次访问把结点旋转到根，摊还 \(O(\lg n)\)；对"最近访问的价位最可能再次访问"的模式很友好。
  • 跳表（skip list）：在链表上加多层索引，期望 \(O(\lg n)\)；Redis 的有序集合（ZSET）用的就是跳表。
  • 持久化（思考题 13-1）：插入时只复制从根到修改位置的路径、其余结点共享（路径复制），每次修改 \(O(\lg n)\) 时间与空间，就能保存每个历史版本——可用于订单簿快照回放。注意若结点有父指针，就必须复制整棵树，所以持久化树通常不存父指针。
  • 连接（思考题 13-2）：已知 \(S_1\) 中所有键 \(\le x\le S_2\) 中所有键，可在 \(O(\lg n)\) 内合并为一棵红黑树。

12.3 量化实战

12.3.1 为什么订单簿不能用普通 BST

限价订单簿（limit order book）的每一侧都是按价格排序的动态集合：新价位出现要插入，价位上的挂单被吃光或撤光要删除；最优买价是买方的最大值，最优卖价是卖方的最小值；"前五档"就是从最优价开始连续 4 次后继；as-of 查找（"某时刻之前最后一笔报价是什么"）就是 PREDECESSOR/FLOOR 查询。这些正是本章的操作集合。

下面的代码实现了原书的红黑树（插入、删除、两类修复、性质检查器），并做三件事：比较单边行情与随机顺序下普通 BST 与红黑树的高度；用两万次随机增删对照 Python 排序结果并反复检查红黑性质；用 FLOOR 做 as-of 查找，与 numpy.searchsorted 对照。

import numpy as np, sys
sys.setrecursionlimit(10000)
RED, BLACK = 0, 1

class Node:
    __slots__ = ("key", "val", "color", "left", "right", "p")
    def __init__(self, key, val, color, nil):
        self.key, self.val, self.color = key, val, color
        self.left = self.right = self.p = nil

class RBTree:
    """CLRS 第 13 章红黑树：哨兵 T.nil，插入/删除各带 FIXUP。"""
    def __init__(self):
        self.nil = Node(None, None, BLACK, None)
        self.nil.left = self.nil.right = self.nil.p = self.nil
        self.root = self.nil
    # ---- 旋转 ----
    def _rot(self, x, d):                 # d='L' 左旋, d='R' 右旋
        a, b = ("right", "left") if d == "L" else ("left", "right")
        y = getattr(x, a)
        setattr(x, a, getattr(y, b))
        if getattr(y, b) is not self.nil: getattr(y, b).p = x
        y.p = x.p
        if x.p is self.nil: self.root = y
        elif x is x.p.left: x.p.left = y
        else: x.p.right = y
        setattr(y, b, x); x.p = y
    # ---- 查询：都是 O(h) ----
    def search(self, k):
        x = self.root
        while x is not self.nil and k != x.key:
            x = x.left if k < x.key else x.right
        return x
    def minimum(self, x):
        while x.left is not self.nil: x = x.left
        return x
    def floor(self, k):                   # 关键字 <= k 的最大结点（as-of 查询）
        x, best = self.root, self.nil
        while x is not self.nil:
            if x.key <= k: best, x = x, x.right
            else: x = x.left
        return best
    def successor(self, x):
        if x.right is not self.nil: return self.minimum(x.right)
        y = x.p
        while y is not self.nil and x is y.right: x, y = y, y.p
        return y
    # ---- 插入 ----
    def insert(self, k, v=None):
        z = new = Node(k, v, RED, self.nil)
        y, x = self.nil, self.root
        while x is not self.nil:
            y = x; x = x.left if k < x.key else x.right
        z.p = y
        if y is self.nil: self.root = z
        elif k < y.key: y.left = z
        else: y.right = z
        while z.p.color == RED:           # RB-INSERT-FIXUP
            gp = z.p.p
            other, rot1, rot2 = ("right", "L", "R") if z.p is gp.left else ("left", "R", "L")
            y = getattr(gp, other)        # 叔结点
            if y.color == RED:            # 情况 1：叔红 → 重新着色，z 上移两层
                z.p.color = y.color = BLACK; gp.color = RED; z = gp
            else:
                if z is getattr(z.p, other):   # 情况 2：z 是"内侧"孩子 → 旋转成情况 3
                    z = z.p; self._rot(z, rot1)
                z.p.color = BLACK; z.p.p.color = RED   # 情况 3
                self._rot(z.p.p, rot2)
        self.root.color = BLACK
        return new                        # 注意：fixup 中 z 已上移，要返回新结点本身
    # ---- 删除 ----
    def _transplant(self, u, v):
        if u.p is self.nil: self.root = v
        elif u is u.p.left: u.p.left = v
        else: u.p.right = v
        v.p = u.p                         # 即使 v 是 nil 也赋值
    def delete(self, z):
        y, y_color = z, z.color
        if z.left is self.nil:  x = z.right; self._transplant(z, z.right)
        elif z.right is self.nil: x = z.left; self._transplant(z, z.left)
        else:
            y = self.minimum(z.right); y_color = y.color; x = y.right
            if y.p is z: x.p = y
            else:
                self._transplant(y, y.right); y.right = z.right; y.right.p = y
            self._transplant(z, y); y.left = z.left; y.left.p = y; y.color = z.color
        if y_color == BLACK:              # RB-DELETE-FIXUP：x 带着"额外的黑"
            while x is not self.root and x.color == BLACK:
                side, other, rot1, rot2 = ("left", "right", "L", "R") if x is x.p.left else ("right", "left", "R", "L")
                w = getattr(x.p, other)   # 兄弟
                if w.color == RED:        # 情况 1
                    w.color = BLACK; x.p.color = RED; self._rot(x.p, rot1); w = getattr(x.p, other)
                if getattr(w, side).color == BLACK and getattr(w, other).color == BLACK:
                    w.color = RED; x = x.p                       # 情况 2：额外的黑上移
                else:
                    if getattr(w, other).color == BLACK:         # 情况 3
                        getattr(w, side).color = BLACK; w.color = RED; self._rot(w, rot2); w = getattr(x.p, other)
                    w.color = x.p.color; x.p.color = BLACK       # 情况 4
                    getattr(w, other).color = BLACK; self._rot(x.p, rot1); x = self.root
            x.color = BLACK
    # ---- 检查 ----
    def height(self, x=None):
        x = self.root if x is None else x
        return -1 if x is self.nil else 1 + max(self.height(x.left), self.height(x.right))
    def check(self):                      # 验证 5 条红黑性质 + BST 性质，返回黑高
        assert self.root.color == BLACK
        def bh(x, lo, hi):
            if x is self.nil: return 0
            assert lo <= x.key <= hi
            if x.color == RED: assert x.left.color == BLACK and x.right.color == BLACK
            l, r = bh(x.left, lo, x.key), bh(x.right, x.key, hi)
            assert l == r
            return l + (x.color == BLACK)
        return bh(self.root, -np.inf, np.inf)
    def inorder(self):
        out, st, x = [], [], self.root
        while st or x is not self.nil:
            while x is not self.nil: st.append(x); x = x.left
            x = st.pop(); out.append(x.key); x = x.right
        return out

def bst_height_after_inserts(keys):       # 不平衡的普通 BST，只记录深度
    root, maxd = None, 0
    left, right, key = {}, {}, {}
    for i, k in enumerate(keys):
        if root is None: root = i; key[i] = k; continue
        x, d = root, 0
        while True:
            d += 1
            nxt = left if k < key[x] else right
            if x in nxt: x = nxt[x]
            else: nxt[x] = i; key[i] = k; break
        maxd = max(maxd, d)
    return maxd

rng = np.random.default_rng(1)
n = 2000
trend = np.round(10 + 0.01 * np.arange(n), 2)          # 单边上涨行情：价位按递增顺序出现
shuffled = rng.permutation(trend)
for name, ks in [("单边行情(递增插入)", trend), ("随机顺序插入", shuffled)]:
    t = RBTree()
    for k in ks: t.insert(float(k))
    print(f"{name}: 普通BST高度 {bst_height_after_inserts(list(ks)):5d} | 红黑树高度 {t.height():3d}"
          f" | 界 2lg(n+1)={2*np.log2(n+1):.1f} | 黑高 {t.check()}")

# 随机增删 2 万次，与 Python 有序列表对照，并检查红黑性质
t, ref, nodes = RBTree(), [], {}
for step in range(20000):
    if ref and rng.random() < 0.45:
        k = ref.pop(rng.integers(len(ref))); t.delete(nodes.pop(k))
    else:
        k = int(rng.integers(0, 10**6))
        if k not in nodes: nodes[k] = t.insert(k); ref.append(k)
    if step % 500 == 0: t.check()             # 每 500 步验证一次全部性质
t.check()
print("随机增删后: 中序遍历 == 排序结果:", t.inorder() == sorted(ref), f" n={len(ref)}, 高度={t.height()}")

# as-of 查询：找时刻 t 之前（含）最后一笔报价
ts = np.sort(rng.choice(np.arange(34_200_000, 54_000_000, 1000), 3000, replace=False))
quotes = RBTree()
for i, s in enumerate(ts): quotes.insert(int(s), round(10 + 0.01 * i, 2))
for q in [34_200_000, 40_000_500, 53_999_999]:
    x = quotes.floor(q)
    print(f"as-of {q}:", "无报价" if x is quotes.nil else f"时间戳 {x.key}, 价格 {x.val}",
          "| 与 searchsorted 一致:", (x.key if x is not quotes.nil else None) ==
          (int(ts[np.searchsorted(ts, q, side='right') - 1]) if q >= ts[0] else None))

运行输出：

单边行情(递增插入): 普通BST高度  1999 | 红黑树高度  18 | 界 2lg(n+1)=21.9 | 黑高 10
随机顺序插入: 普通BST高度    28 | 红黑树高度  12 | 界 2lg(n+1)=21.9 | 黑高 7
随机增删后: 中序遍历 == 排序结果: True  n=1901, 高度=13
as-of 34200000: 无报价 | 与 searchsorted 一致: True
as-of 40000500: 时间戳 39991000, 价格 18.59 | 与 searchsorted 一致: True
as-of 53999999: 时间戳 53999000, 价格 39.99 | 与 searchsorted 一致: True

读结果。 单边行情下普通 BST 高度 1999——完全退化为链，每次找最优价都要走两千步；红黑树高度 18，在 \(2\lg(n+1)\approx21.9\) 的界内。随机顺序时普通 BST 高 28，与定理 12.4 的 \(O(\lg n)\) 一致（作为补充：已知随机 BST 的期望高度渐近于 \(4.311\ln n\) 减去一个 \(\ln\ln n\) 量级的修正项，\(n=2000\) 时约为 29），但仍比红黑树高一倍多。第一行的红黑树高度（18）比第二行（12）大，原因是递增插入总在最右侧触发修复，产生较多红结点，但无论如何都不会越过引理 13.1 的界。as-of 查询在 \(O(\lg n)\) 内完成，结果与对排序数组二分查找一致。

12.3.2 工程选择：平衡树、tick 数组还是排序数组

同样是"有序动态集合"，实盘系统不一定选红黑树：

  • 数据静态、只查不改（回测时的历史报价序列）：排序数组 + 二分查找最快，numpy.searchsorted 或 pandas.merge_asof 即是。
  • 价格离散且范围有限（股票、期货都有最小变动价位）：用"价格 → 档位下标"的直接寻址数组（上一章 11.1 节），配合一个指向最优价的游标；插入删除 \(O(1)\)，找下一个非空档位通常只需扫描几格。高频撮合引擎多用这种结构，缓存命中率远好于指针型的树。
  • 价格范围大且稀疏、需要频繁增删和有序遍历（跨品种、期权链、加密资产的深度簿）：平衡树（红黑树、B 树变体、跳表）。
  • 需要历史版本（订单簿快照回放、组合状态审计）：持久化平衡树（思考题 13-1）。

Python 研究环境里很少手写红黑树：标准库没有有序映射，常用第三方 sortedcontainers.SortedDict/SortedList（基于分块排序列表，而非平衡树），或直接用 bisect 维护排序列表。理解本章的意义在于：知道这些容器的复杂度保证从哪里来，以及在什么输入下会出问题。

市场微观结构里订单簿的规则与动态见第 07 册；本册第 14 章会在平衡树上"扩张"出累计挂单量，回答"吃掉 \(Q\) 股要穿透到哪个价位"。

本章小结

二叉搜索树用"左小右大"的性质组织有序动态集合，所有基本操作都是 \(O(h)\)；中序遍历 \(\Theta(n)\) 给出有序序列；后继可以不比较关键字只靠树结构找到；删除用 TRANSPLANT 分四种情况，保证删除的就是传入的结点。随机顺序插入时期望高度 \(O(\lg n)\)，但有序输入会让它退化成链。红黑树用五条颜色性质把高度锁在 \(2\lg(n+1)\) 以内；插入把新结点染红、按叔结点颜色分三种情况修复，至多 2 次旋转；删除用"额外的黑"的概念、按兄弟及侄子颜色分四种情况修复，至多 3 次旋转；两者都是 \(O(\lg n)\)。

概念 关键结论
BST 性质 左子树键 \(\le x.key\le\) 右子树键
BST 操作 全部 \(O(h)\)；\(\lfloor\lg n\rfloor\le h\le n-1\)
连续 \(k\) 次后继 \(O(k+h)\)
随机构造 BST \(E[\text{高度}]=O(\lg n)\)；\(E[2^{X_n}]\le\frac14\binom{n+3}3\)
红黑性质 结点红或黑；根黑；叶黑；红结点的孩子黑；各路径黑结点数相同
引理 13.1 子树至少 \(2^{bh(x)}-1\) 个内部结点；\(h\le2\lg(n+1)\)
旋转 \(O(1)\)，保持中序次序
RB 插入 \(O(\lg n)\)，至多 2 次旋转
RB 删除 \(O(\lg n)\)，至多 3 次旋转

练习

基础

  1. 对关键字 \(\{1,4,5,10,16,17,21\}\) 分别画出高度为 2、3、4、5、6 的二叉搜索树。（原书 12.1-1。）
  2. 写出非递归的中序遍历：一种用栈，另一种不用栈但利用父指针。（原书 12.1-3。）
  3. 证明：若 BST 中结点有两个孩子，则其后继没有左孩子，前驱没有右孩子。（原书 12.2-5。）
  4. 依次把 41, 38, 31, 12, 19, 8 插入一棵空红黑树，画出每一步的结果；再依次删除 8, 12, 19, 31, 38, 41。（原书 13.3-2、13.4-3。建议用本章代码的 check 验证你的手算。）
  5. 证明黑高为 \(k\) 的红黑树内部结点数最少 \(2^k-1\)、最多 \(2^{2k}-1\)。（原书 13.1-6。）

进阶

  1. 证明从任意结点出发连续调用 \(k\) 次 TREE-SUCCESSOR 的总时间为 \(O(k+h)\)。（原书 12.2-8。提示：每条边最多被经过两次。）
  2. 用 BST 插入加中序遍历来排序，最坏和最好时间分别是多少？与快速排序有什么对应关系？（原书 12.3-3、思考题 12-3。）
  3. 证明任意 \(n\) 结点 BST 可以用 \(O(n)\) 次旋转变成任意另一棵 \(n\) 结点 BST。（原书 13.2-4。提示：先用至多 \(n-1\) 次右旋变成右链。）
  4. 结点没有父指针时，如何实现 RB-INSERT？（原书 13.3-6。提示：下降时用栈记录路径。）
  5. 思考题 13-1：用路径复制实现持久化 BST 的插入。设想每秒对订单簿做一次快照，一天 4 小时交易、每秒约 50 次价位变动、平均树高 15，估算持久化方案比"每秒全量复制 2000 个价位"节省多少结点复制。
  6. 思考题 13-4：证明 treap 插入的期望旋转次数小于 2。

原书推荐习题：12.1-3、12.2-1、12.2-6、12.2-8、12.3-3、12.3-6、13.1-5、13.1-6、13.2-4、13.3-2、13.3-6、13.4-3，思考题 12-3、12-4、13-1、13-4。

原书对照

本章小节 原书章节 PDF 页码
12.1.1–12.1.2 定义、遍历、查询 12.1 What is a BST；12.2 Querying p.307–315
12.1.3 插入与删除 12.3 Insertion and deletion p.315–320
12.1.4 随机构造 BST 12.4 Randomly built BSTs p.320–324
12.2.1 红黑性质 13.1 Properties of red-black trees p.329–333
12.2.2 旋转 13.2 Rotations p.333–335
12.2.3 插入 13.3 Insertion p.336–343
12.2.4 删除 13.4 Deletion p.344–351
12.2.5 其他平衡树 思考题 13-1～13-4、章末注记 p.352–359
BST 思考题 Problems 12-1～12-4 p.324–328