元信息：《Introduction to Algorithms》（第 3 版），Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 著；本笔记负责 PDF 第 249–449 页（Part III Data Structures 起）。

Part III 数据结构（Data Structures）（PDF p.249–252）

导言：动态集合

动态集合（dynamic set）：算法中操作的集合会随时间增长、收缩或变化，不同于数学中不变的集合。Part III 的 5 章（第 10–14 章）讨论在计算机上表示有限动态集合及其操作的基本技术。
字典（dictionary）：只支持插入、删除、成员测试三种操作的动态集合。更复杂的例子如第 6 章的最小优先队列（min-priority queue）：插入元素、取出最小元素。实现动态集合的最佳方式取决于需要支持哪些操作。
元素的表示：每个元素是一个对象，通过指针可以检查和修改其属性。有些动态集合假定对象有一个标识用的关键字（key）；若关键字互不相同，可以把动态集合看作关键字的集合。对象还可携带卫星数据（satellite data）——集合实现本身不使用，只是随对象一起移动；对象也可能含有由集合操作维护的属性（数据或指向集合中其他对象的指针）。
有些动态集合假定关键字来自全序集（totally ordered set）（如实数、按字典序的单词），从而可以定义最小元素、"比给定元素大的下一个元素"等。

动态集合上的典型操作

分为查询（queries）（只返回信息）和修改操作（modifying operations）（改变集合）两类：

操作	类型	含义
`SEARCH(S, k)`	查询	返回指向 $x.key = k$ 的元素的指针 $x$，若不存在返回 NIL
`INSERT(S, x)`	修改	把 $x$ 指向的元素加入 $S$（假定 $x$ 中集合实现需要的属性已初始化）
`DELETE(S, x)`	修改	给定指向元素 $x$ 的指针（不是关键字值），从 $S$ 中删除 $x$
`MINIMUM(S)` / `MAXIMUM(S)`	查询	在全序集上返回关键字最小/最大元素的指针
`SUCCESSOR(S, x)`	查询	返回下一个更大元素的指针；$x$ 为最大元素时返回 NIL
`PREDECESSOR(S, x)`	查询	返回下一个更小元素的指针；$x$ 为最小元素时返回 NIL

常见误区：DELETE 的参数是指针，不是关键字；如果只知道关键字，需要先 SEARCH。SUCCESSOR/PREDECESSOR 可推广到关键字不互异的情形；通常约定对 $n$ 个关键字调用一次 MINIMUM 再调用 $n-1$ 次 SUCCESSOR，即可按序枚举全部元素。时间一般以集合大小 $n$ 衡量，例如第 13 章的结构能在 $O(\lg n)$ 时间内支持上述所有操作。

Part III 概览

第 10 章：栈、队列、链表、有根树等简单结构，以及在不支持指针的环境中如何用数组实现对象和指针。
第 11 章：散列表（hash table），支持 INSERT/DELETE/SEARCH；最坏情况 SEARCH 为 $\Theta(n)$，但期望时间 $O(1)$，分析依赖概率。
第 12 章：二叉搜索树，支持上表全部操作；最坏 $\Theta(n)$，随机构造的二叉搜索树上期望 $O(\lg n)$。
第 13 章：红黑树（red-black tree），平衡搜索树，所有操作最坏 $O(\lg n)$。（第 18 章的 B 树是另一种平衡搜索树。）
第 14 章：扩张（augment）红黑树，以支持动态顺序统计量和区间集合。
第 6 章的堆（heap）也是重要的数据结构。

第 10 章基本数据结构（Elementary Data Structures）（PDF p.253–273）

本章用基于指针的简单结构表示动态集合：栈、队列、链表、有根树，并说明如何用数组合成对象和指针。

10.1 栈和队列（Stacks and queues）（PDF p.253–257）

栈和队列是 DELETE 删除的元素事先确定的动态集合。

栈（stack）：删除最近插入的元素，后进先出（LIFO, last-in first-out）。
队列（queue）：删除在集合中停留最久的元素，先进先出（FIFO, first-in first-out）。

栈的数组实现

用数组 $S[1..n]$ 实现最多 $n$ 个元素的栈；属性 $S.top$ 指向最近插入元素的下标。栈由 $S[1..S.top]$ 构成，$S[1]$ 为栈底，$S[S.top]$ 为栈顶。$S.top = 0$ 时栈空。对空栈执行 POP 称为下溢（underflow），$S.top$ 超过 $n$ 称为上溢（overflow）（伪代码中不处理上溢）。INSERT 叫 PUSH，DELETE 叫 POP（不带元素参数），源自自助餐厅弹簧托盘叠。

def STACK_EMPTY(S):
    return S.top == 0

def PUSH(S, x):
    S.top += 1
    S[S.top] = x

def POP(S):
    if STACK_EMPTY(S):
        raise Error("underflow")
    S.top -= 1
    return S[S.top + 1]      # 元素仍在数组里，但已不属于栈

三个操作均为 $O(1)$ 时间。图 10.1 示例：栈有 4 个元素（栈顶 9，$S.top=4$）；PUSH 17、PUSH 3 后 $S.top=6$；POP 返回 3 后 $S.top=5$，3 仍留在数组中但已不在栈里，栈顶为 17。

队列的数组实现（循环数组）

INSERT 称 ENQUEUE（入队），DELETE 称 DEQUEUE（出队，不带元素参数）。队列有队头（head）和队尾（tail），像排队付款的顾客。

用 $Q[1..n]$ 实现最多 $n-1$ 个元素的队列：$Q.head$ 指向队头，$Q.tail$ 指向下一个新元素将要插入的位置。元素位于 $Q.head, Q.head+1, \dots, Q.tail-1$，并且环绕（wrap around）：位置 1 紧跟在位置 $n$ 之后。

$Q.head = Q.tail$ 时队列为空；初始 $Q.head = Q.tail = 1$。空队列出队 → 下溢。
$Q.head = Q.tail + 1$，或 $Q.head = 1$ 且 $Q.tail = Q.length$ 时队列满，再入队 → 上溢。（这就是为何容量是 $n-1$：留一个空位区分"空"和"满"。）

def ENQUEUE(Q, x):           # 省略上溢检查，n = Q.length
    Q[Q.tail] = x
    Q.tail = 1 if Q.tail == Q.length else Q.tail + 1

def DEQUEUE(Q):              # 省略下溢检查
    x = Q[Q.head]
    Q.head = 1 if Q.head == Q.length else Q.head + 1
    return x

均为 $O(1)$。图 10.2：$Q[1..12]$，初始 5 个元素位于 $Q[7..11]$（head=7, tail=12）；依次入队 17、3、5 后 tail 环绕到 3；出队返回 15，head=8，新队头为 6。

习题 10.1 概括

10.1-1 / 10.1-3：在 $S[1..6]$ / $Q[1..6]$ 上手工模拟给定的操作序列。
10.1-2：在一个数组 $A[1..n]$ 中实现两个栈，除非两栈元素总数达到 $n$ 否则都不溢出（提示思路：两栈分别从两端向中间生长）。
10.1-4：给 ENQUEUE/DEQUEUE 加上溢出与下溢检测。
10.1-5：双端队列（deque, double-ended queue），两端都可插入/删除，写 4 个 $O(1)$ 过程。
10.1-6：用两个栈实现队列并分析时间（摊还 $O(1)$）；10.1-7：用两个队列实现栈。

10.2 链表（Linked lists）（PDF p.257–262）

**链表（linked list）**中对象按线性顺序排列，但顺序由对象中的指针决定，而不是数组下标。它为动态集合提供简单灵活的表示，支持（不一定高效）Part III 导言列出的全部操作。

双向链表（doubly linked list） $L$：每个元素有 key、next、prev 属性（可附卫星数据）。$x.prev = \text{NIL}$ 表示 $x$ 是表头（head）；$x.next = \text{NIL}$ 表示 $x$ 是表尾（tail）。$L.head$ 指向第一个元素；$L.head = \text{NIL}$ 表示空表。
其他形式：单向链表（singly linked）（省略 prev）；有序（sorted）表（表头为最小元素，表尾为最大）与无序表；循环链表（circular list）（表头的 prev 指向表尾，表尾的 next 指向表头，形成环）。本节其余部分假定链表无序且双向。

搜索、插入、删除

def LIST_SEARCH(L, k):       # 线性查找第一个 key == k 的元素
    x = L.head
    while x is not NIL and x.key != k:
        x = x.next
    return x                 # 最坏 Θ(n)

def LIST_INSERT(L, x):       # 把 x 拼接到表头
    x.next = L.head
    if L.head is not NIL:
        L.head.prev = x
    L.head = x
    x.prev = NIL             # O(1)

def LIST_DELETE(L, x):       # 给定指针 x，将其"剪"出链表
    if x.prev is not NIL:
        x.prev.next = x.next
    else:
        L.head = x.next
    if x.next is not NIL:
        x.next.prev = x.prev # O(1)

图 10.3：表示集合 $\{1,4,9,16\}$ 的链表（顺序 9,16,4,1）；LIST-SEARCH(L,4) 返回第三个元素，LIST-SEARCH(L,7) 返回 NIL；插入 key=25 后其成为新表头；再删除 key=4 的对象。注意：LIST-DELETE 本身 $O(1)$，但若按关键字删除，需先 LIST-SEARCH，最坏 $\Theta(n)$。属性记法可级联，例如 L.head.prev。

哨兵（sentinel）

若忽略头尾边界条件，删除只需两行：x.prev.next = x.next; x.next.prev = x.prev。哨兵是一个哑对象（dummy object），用来简化边界条件：给链表配一个对象 $L.nil$，它代表 NIL 但具有其他对象的全部属性，代码中所有 NIL 引用都换成 $L.nil$。这样普通双向链表变成带哨兵的双向循环链表（circular, doubly linked list with a sentinel）：$L.nil$ 位于表头和表尾之间，$L.nil.next$ 指向表头，$L.nil.prev$ 指向表尾；表尾的 next 和表头的 prev 都指向 $L.nil$。因此可以去掉 $L.head$ 属性。空表只含哨兵，$L.nil.next = L.nil.prev = L.nil$。

def LIST_SEARCH_(L, k):
    x = L.nil.next
    while x is not L.nil and x.key != k:
        x = x.next
    return x

def LIST_INSERT_(L, x):
    x.next = L.nil.next
    L.nil.next.prev = x
    L.nil.next = x
    x.prev = L.nil

def LIST_DELETE_(L, x):
    x.prev.next = x.next
    x.next.prev = x.prev

要点与误区：哨兵很少降低渐近时间界，但能减小常数因子；在链表上主要是让代码更清晰，只省 $O(1)$ 时间。在某些循环中使用哨兵可以收紧循环体，从而降低 $n$ 或 $n^2$ 项的系数。但要慎用：大量小链表时，每个哨兵的额外存储会造成可观浪费。本书只在确实简化代码时才用哨兵。

习题 10.2 概括

10.2-1：单向链表上 INSERT 能否 $O(1)$？DELETE 呢？（INSERT 可以；按指针删除需要前驱，一般不行。）
10.2-2 / 10.2-3：用单向链表实现栈、队列，操作保持 $O(1)$（队列需维护尾指针）。
10.2-4：在 LIST-SEARCH′ 中消去 $x \ne L.nil$ 的测试（把 $k$ 放入哨兵的 key）。
10.2-5：用单向循环链表实现字典操作并分析时间。
10.2-6：用合适的链表在 $O(1)$ 内支持不相交集合的 UNION。
10.2-7：$\Theta(n)$ 非递归、常数额外空间地反转单向链表。
10.2-8（星号）：异或链表，每个结点只存 $x.np = x.next \oplus x.prev$（NIL 表示为 0），实现 SEARCH/INSERT/DELETE，并在 $O(1)$ 内反转链表。

10.3 指针和对象的实现（Implementing pointers and objects）（PDF p.262–266）

在没有显式指针类型的语言中，用数组和数组下标合成对象和指针。

多数组表示（multiple-array representation）

对一组具有相同属性的对象，每个属性用一个数组。例：用 key、next、prev 三个数组表示图 10.3(a) 的链表；对给定下标 $x$，key[x]、next[x]、prev[x] 共同表示一个对象，指针 $x$ 就是三个数组的公共下标。例如 key 4 存在 key[2]、key 16 存在 key[5]，16 后面跟着 4，所以 next[5]=2、prev[2]=5。NIL 通常用不可能是合法下标的整数（如 0 或 $-1$）表示；变量 $L$ 存表头下标（图 10.5 中 $L=7$）。

单数组表示（single-array representation）

计算机内存字用 $0..M-1$ 的整数寻址；对象通常占据连续内存，指针是对象首地址，属性通过"指针 + 偏移量（offset）"访问。同样，可以用一个数组 $A$ 存所有对象：对象占用连续子数组 $A[j..k]$，每个属性对应 $0..k-j$ 中的一个偏移，指向对象的指针为 $j$。图 10.6 中 key、next、prev 的偏移分别为 0、1、2，所以读 $i.prev$ 就是读 $A[i+2]$。单数组表示的灵活之处是允许不同长度的对象存在同一数组中，但管理**异构（heterogeneous）对象集合比同构（homogeneous）**更难；本书的数据结构多由同构元素构成，所以用多数组表示即可。

对象的分配与释放（Allocating and freeing objects）

插入元素时需要分配一个当前未使用的对象。有些系统由**垃圾回收器（garbage collector）**判定哪些对象未被使用；许多简单应用可以自己负责把不用的对象还给存储管理器。设多数组长度为 $m$，动态集合当前有 $n \le m$ 个元素，则其余 $m-n$ 个对象空闲。

把空闲对象组织成单向链表，称为自由表（free list）：只用 next 数组，表头存于全局变量 free。自由表可能与链表 $L$ 交织在同一组数组中，但每个对象要么在 $L$ 中，要么在自由表中，不会同时属于两者。自由表像栈一样工作：下一次分配的对象是最近释放的那个。

def ALLOCATE_OBJECT():
    if free is NIL:
        raise Error("out of space")
    x = free
    free = x.next            # 相当于 POP
    return x

def FREE_OBJECT(x):
    x.next = free            # 相当于 PUSH
    free = x

二者都是 $O(1)$，很实用。自由表初始包含全部 $n$ 个未分配对象（此处 $n$ 指数组长度）。一个自由表可以服务多个链表（图 10.8：两个链表 $L_1$、$L_2$ 和一个自由表交织在 key/next/prev 数组中）。对于任何同构对象集合，只要让某个属性充当自由表的 next 即可复用这套过程。图 10.7 示例：ALLOCATE-OBJECT 返回下标 4，置 key[4]=25 并 LIST-INSERT(L,4)，新自由表头为原 next[4]=8；再 LIST-DELETE(L,5) 后 FREE-OBJECT(5)，5 成为新自由表头，后跟 8。

习题 10.3 概括

10.3-1：分别用多数组和单数组表示序列 ⟨13,4,8,19,5,11⟩ 的双向链表。
10.3-2：为单数组表示写 ALLOCATE/FREE。
10.3-3：为何分配/释放时无需设置 prev？（自由表是单向的，只用 next。）
10.3-4：让链表元素紧凑地存于前 $m$ 个位置（虚拟内存分页环境中有用），提示用栈的数组实现。
10.3-5：COMPACTIFY-LIST(L,F)：$\Theta(n)$ 时间、常数额外空间，把 $L$ 的元素移到位置 $1..n$，自由表占 $n+1..m$，并证明正确性。

10.4 有根树的表示（Representing rooted trees）（PDF p.267–270）

上一节表示链表的方法可推广到任何同构数据结构。每个树结点是一个对象，含 key 属性，其余属性是指向其他结点的指针，因树的类型而异。

二叉树（binary tree）：属性 p、left、right 分别指向父结点、左孩子、右孩子。$x.p = \text{NIL}$ 表示 $x$ 是根；无左孩子则 $x.left = \text{NIL}$，右孩子同理。$T.root$ 指向整棵树的根，$T.root = \text{NIL}$ 表示空树（图 10.9）。
孩子数有界的树：若每个结点最多 $k$ 个孩子（$k$ 为常数），可用 $child_1, \dots, child_k$ 代替 left/right。但孩子数无界时无法预先确定要分配多少属性；即使 $k$ 有界但很大而多数结点孩子很少，也会浪费大量内存。
左孩子右兄弟表示（left-child, right-sibling representation）（图 10.10）：对任意 $n$ 结点有根树只用 $O(n)$ 空间。每个结点有父指针 $p$，此外只有两个指针：
1. $x.left\text{-}child$ 指向 $x$ 最左边的孩子；
2. $x.right\text{-}sibling$ 指向 $x$ 右侧紧邻的兄弟。无孩子时 left-child 为 NIL；$x$ 是其父结点最右孩子时 right-sibling 为 NIL。
其他表示：第 6 章的堆基于完全二叉树，用单个数组加最后结点下标表示；第 21 章（不相交集合）的树只向根方向遍历，因而只保留父指针。最佳方案取决于应用。

习题 10.4 概括

10.4-1：根据给定的 index/key/left/right 表格画出根为下标 6 的二叉树。
10.4-2：$O(n)$ 递归打印 $n$ 结点二叉树所有关键字；10.4-3：用栈的 $O(n)$ 非递归版本；10.4-4：$O(n)$ 打印左孩子右兄弟表示的任意有根树。
10.4-5（星号）：$O(n)$ 非递归、常数额外空间、且不（哪怕临时）修改树的遍历——需利用父指针。
10.4-6（星号）：每个结点只用两个指针加一个布尔值，使得父结点或所有孩子都能在与孩子数成线性的时间内访问到（最右孩子的 sibling 指针指回父结点，布尔值标记这一点）。

第 10 章思考题（PDF p.270–273）

10-1 链表比较：对无序单向、有序单向、无序双向、有序双向四种链表，给出 SEARCH、INSERT、DELETE、SUCCESSOR、PREDECESSOR、MINIMUM、MAXIMUM 的最坏渐近时间表。（参考结论：有序表 INSERT 需 $\Theta(n)$ 找位置；单向表 DELETE 和 PREDECESSOR 需 $\Theta(n)$ 找前驱；无序表 SUCCESSOR/MIN/MAX 需 $\Theta(n)$；有序双向表 MAX 若无尾指针为 $\Theta(n)$ 等。）
10-2 用链表实现可合并堆（mergeable heap）：支持 MAKE-HEAP、INSERT、MINIMUM、EXTRACT-MIN、UNION（脚注：支持 MINIMUM 和 EXTRACT-MIN 的叫可合并最小堆，支持 MAXIMUM 和 EXTRACT-MAX 的叫可合并最大堆）。分 (a) 有序表、(b) 无序表、(c) 无序表且被合并集合不相交三种情况，尽量提高效率并分析时间。
10-3 在有序紧凑链表中搜索：$n$ 元素链表紧凑存放在数组前 $n$ 个位置，关键字互异且有序（对所有 next[i] ≠ NIL 有 key[i] < key[next[i]]），$L$ 为首元素下标。随机算法在 $O(\sqrt n)$ 期望时间内搜索：

def COMPACT_LIST_SEARCH(L, n, k):
    i = L
    while i is not NIL and key[i] < k:
        j = RANDOM(1, n)                  # 随机跳到某位置
        if key[i] < key[j] and key[j] <= k:
            i = j                         # 跳跃有益：j 是普通遍历必经之处
            if key[i] == k:
                return i
        i = next[i]
    if i is NIL or key[i] > k:
        return NIL
    return i

因为表是紧凑的，$1..n$ 中任何 $j$ 都对应表中对象而非自由表槽位。分析时改用两段式的 COMPACT-LIST-SEARCH′(L,n,k,t)：先做 $t$ 次随机跳跃的 for 循环，再做普通 while 遍历；假定两者 RANDOM 序列相同。题目步骤：(a) 若原算法 while 循环迭代 $t$ 次，则 $t$ 版本返回相同答案，总迭代次数至少 $t$；设 $X_t$ 为 $t$ 次 for 迭代后位置 $i$ 到目标的链上距离，(b) 期望时间 $O(t + E[X_t])$；(c) $E[X_t] \le \sum_{r=1}^{n}(1-r/n)^t$（利用式 C.25）；(d) $\sum_{r=0}^{n-1} r^t \le n^{t+1}/(t+1)$；(e) $E[X_t] \le n/(t+1)$；(f) 期望时间 $O(t + n/t)$；(g) 取 $t=\sqrt n$ 得 $O(\sqrt n)$；(h) 为何要求关键字互异——有重复关键字时随机跳跃在渐近意义上不一定有帮助。

章末注记（Chapter notes）

Aho–Hopcroft–Ullman 与 Knuth 是基础数据结构的经典参考；Goodrich–Tamassia、Main、Shaffer、Weiss 等结合具体语言；Gonnet 提供许多操作的实验性能数据。栈和队列的起源不清楚；Knuth 认为 A. M. Turing 在 1947 年为子程序链接发展了栈。指针结构似乎是"民间发明"，早期鼓存储计算机已用指针；G. M. Hopper 1951 年的 A-1 语言用二叉树表示代数公式；Newell、Shaw、Simon 1956 年的 IPL-II 语言推广了指针的使用，1957 年的 IPL-III 包含显式栈操作。

第 10 章本章要点

栈（LIFO）与队列（FIFO）都可用数组实现，所有操作 $O(1)$；循环队列用 $n$ 个槽最多存 $n-1$ 个元素，以区分空和满。
双向链表：按指针插入/删除 $O(1)$，按关键字搜索 $\Theta(n)$。哨兵把边界判断消掉，代码更短，只改善常数。
在没有指针的环境中，可用多数组（每属性一个数组）或单数组（指针+偏移）表示对象；用自由表（本质是栈）在 $O(1)$ 内分配和回收同构对象。
二叉树用 p/left/right；孩子数无界的树用左孩子右兄弟表示，空间 $O(n)$。

第 10 章与量化交易的关联

订单簿与撮合引擎：同一价位上的委托按时间优先排队，是典型 FIFO 队列；撤单需要按订单 ID 定位后 $O(1)$ 删除，通常用"散列表（订单 ID → 链表结点指针）+ 双向链表"实现，这正是 LIST-DELETE 接收指针而非关键字的意义。
流式数据与滑动窗口：固定长度循环数组（ring buffer）是行情 tick 缓存、滚动均值/波动率等滑动窗口指标的标准实现；双端队列（习题 10.1-5）是 $O(1)$ 摊还的滑动窗口最大/最小值（单调队列）算法的基础，常用于突破类因子和回撤计算。
低延迟系统实现：自由表 + 对象池（ALLOCATE-OBJECT/FREE-OBJECT）就是交易系统中避免运行时动态分配、减少 GC 停顿的内存池技术；多数组表示对应 "struct of arrays" 的列式内存布局，利于缓存和向量化（因子计算的列式存储思想相同）。
栈在回测引擎中主要用于表达式求值（因子表达式解析、逆波兰式）等，关联较间接。

第 10 章推荐习题

10.1-2（一个数组两个栈）：空间共享技巧。
10.1-5、10.1-6：双端队列与"两个栈实现队列"，考查摊还分析与滑动窗口基础结构。
10.2-7：原地反转单向链表，指针操作基本功。
10.3-4 / 10.3-5：紧凑存储与内存池，贴近系统实现。
10.4-3、10.4-5：非递归树遍历（显式栈、常数空间）。
思考题 10-3：随机跳跃搜索 $O(\sqrt n)$，练习期望分析与 $t$ 的最优选择。

第 11 章散列表（Hash Tables）（PDF p.274–306）

许多应用只需要字典操作 INSERT、SEARCH、DELETE，例如编译器的符号表（symbol table），关键字是任意的标识符字符串。散列表（hash table）是实现字典的有效结构：最坏情况下搜索与链表一样需要 $\Theta(n)$，但在合理假设下平均搜索时间为 $O(1)$。散列表是普通数组的推广：直接寻址利用了"$O(1)$ 访问任意数组位置"的能力（11.1）；当实际存储的关键字数远小于可能的关键字总数时，散列表用与实际关键字数成正比的数组，下标由关键字计算得出。11.2 讲用链接法（chaining）处理冲突（collision），11.3 讲散列函数，11.4 讲开放寻址（open addressing），11.5 讲关键字集合静态时最坏 $O(1)$ 的完全散列（perfect hashing）。

11.1 直接寻址表（Direct-address tables）（PDF p.275–276）

当关键字全域 $U = \{0, 1, \dots, m-1\}$ 不太大且没有两个元素关键字相同时，用数组 $T[0..m-1]$ 作直接寻址表（direct-address table），每个位置称为槽（slot），槽 $k$ 指向关键字为 $k$ 的元素，若无此元素则 $T[k] = \text{NIL}$（图 11.1：$U=\{0..9\}$，实际关键字 $K=\{2,3,5,8\}$）。

def DIRECT_ADDRESS_SEARCH(T, k): return T[k]
def DIRECT_ADDRESS_INSERT(T, x): T[x.key] = x
def DIRECT_ADDRESS_DELETE(T, x): T[x.key] = NIL

三者都是 $O(1)$。变体：可以把对象直接存在槽内以节省空间，用特殊关键字表示空槽；由于下标即关键字，往往不必存关键字，但那样就需另有办法判断槽是否为空。

习题：11.1-1 找直接寻址表中的最大元素（最坏 $\Theta(m)$）；11.1-2 用**位向量（bit vector）**表示无卫星数据的集合；11.1-3 关键字可重复且带卫星数据时的 $O(1)$ 直接寻址表（每槽挂双向链表）；11.1-4（星号）在超大、未初始化的数组上实现直接寻址字典，初始化 $O(1)$——用一个附加的栈式数组记录有效条目，互相校验。

11.2 散列表（Hash tables）（PDF p.277–282）

直接寻址的缺点：$U$ 很大时存 $|U|$ 大小的表不现实，且实际关键字集 $K$ 相对 $U$ 很小时大部分空间浪费。散列表把存储需求降到 $\Theta(|K|)$，同时保持搜索 $O(1)$——但这是平均情况，而直接寻址是最坏情况。

关键字 $k$ 存放在槽 $h(k)$ 中，散列函数（hash function） $h: U \to \{0, 1, \dots, m-1\}$，$m$ 通常远小于 $|U|$；称 $k$ 散列到（hashes to）槽 $h(k)$，$h(k)$ 是 $k$ 的散列值（hash value）。两个关键字散列到同一槽称为冲突（collision）。理想是让 $h$ 看起来"随机"以减少冲突（"to hash"本意就是切碎、混合），但 $h$ 必须是确定性的；由于 $|U| > m$，冲突不可能完全避免，所以必须有冲突解决方法。

链接法（chaining）

把散列到同一槽的所有元素放进同一个链表；槽 $j$ 存指向该链表表头的指针，没有元素时为 NIL（图 11.3）。

def CHAINED_HASH_INSERT(T, x):  # 插到链表 T[h(x.key)] 头部
    LIST_INSERT(T[h(x.key)], x)   # 最坏 O(1)（假设 x 不在表中）
def CHAINED_HASH_SEARCH(T, k):  # 在 T[h(k)] 中查 key == k
    return LIST_SEARCH(T[h(k)], k) # 正比于链表长度
def CHAINED_HASH_DELETE(T, x):  # 从 T[h(x.key)] 删除 x
    LIST_DELETE(T[h(x.key)], x)   # 双向链表时 O(1)

要点：插入之所以 $O(1)$，部分是因为假定 $x$ 尚不在表中（如有必要可先搜索，代价增加）。DELETE 以元素 $x$ 而非关键字为参数，所以不必先搜索；但链表必须是双向的才能 $O(1)$ 删除——单向链表需要先找到前驱，删除和搜索渐近时间相同。

链接法的分析

装载因子（load factor） $\alpha = n/m$：$m$ 个槽存 $n$ 个元素时每条链的平均元素数，可小于、等于或大于 1。

最坏情况很糟：所有 $n$ 个关键字散列到同一槽，搜索 $\Theta(n)$ 加计算散列的时间，不比一个链表好。散列表不是为最坏情况而用的（11.5 的完全散列例外）。
**简单均匀散列（simple uniform hashing）**假设：任一元素等可能地散列到 $m$ 个槽中任何一个，且与其他元素散列到哪里无关。记 $T[j]$ 链表长度为 $n_j$，则 $n = n_0 + n_1 + \dots + n_{m-1}$（式 11.1），$E[n_j] = \alpha$。假设计算 $h(k)$ 为 $O(1)$。

定理 11.1：链接法、简单均匀散列下，**不成功搜索（unsuccessful search）**的平均时间为 $\Theta(1+\alpha)$。证明：不在表中的 $k$ 等可能散列到任一槽，需要查到链表 $T[h(k)]$ 末尾，期望长度 $E[n_{h(k)}] = \alpha$；加上计算 $h(k)$ 共 $\Theta(1+\alpha)$。

定理 11.2：同样假设下，**成功搜索（successful search）**的平均时间也为 $\Theta(1+\alpha)$。证明思路：假定要找的元素等可能是表中 $n$ 个元素之一。找 $x$ 时检查的元素数 = 1 + 链表中排在 $x$ 前面的元素数；新元素插在表头，故排在 $x$ 前面的都是在 $x$ 之后插入且散列到同一槽的元素。设 $x_i$ 为第 $i$ 个插入的元素，$k_i = x_i.key$，指示变量 $X_{ij} = I\{h(k_i) = h(k_j)\}$，$E[X_{ij}] = 1/m$。于是

E\left[\frac1n\sum_{i=1}^n\Big(1+\sum_{j=i+1}^n X_{ij}\Big)\right] = 1 + \frac{1}{nm}\sum_{i=1}^n (n-i) = 1 + \frac{n-1}{2m} = 1 + \frac{\alpha}{2} - \frac{\alpha}{2n}.

总时间 $\Theta(2 + \alpha/2 - \alpha/2n) = \Theta(1+\alpha)$。

含义：若槽数至少与元素数成正比，$n = O(m)$，则 $\alpha = O(1)$，搜索平均常数时间；插入最坏 $O(1)$、双向链表删除最坏 $O(1)$，因此所有字典操作平均 $O(1)$。

习题 11.2 概括：11.2-1 简单均匀散列下 $n$ 个不同关键字的期望冲突对数（$\binom n2/m$）；11.2-2 用 $h(k)=k \bmod 9$ 手工插入 5,28,19,15,20,33,12,17,10；11.2-3 链表保持有序对各操作时间的影响（不成功搜索可提前终止但渐近不变，插入变为 $\Theta(1+\alpha)$）；11.2-4 在表内用自由表管理未用槽；11.2-5 若 $|U| > nm$，必有 $n$ 个关键字散列到同一槽（鸽笼原理），所以最坏 $\Theta(n)$；11.2-6 已知各链长与最长链长 $L$，在期望 $O(L(1+1/\alpha))$ 内均匀随机抽取一个关键字（拒绝采样）。

11.3 散列函数（Hash functions）（PDF p.283–290）

三种构造方案：**除法散列（division method）和乘法散列（multiplication method）**是启发式的；**全域散列（universal hashing）**利用随机化给出可证明的好性能。

什么是好的散列函数

好的散列函数（近似）满足简单均匀散列假设。但通常无法验证，因为很少知道关键字的分布，且关键字可能不独立。偶尔知道分布：若关键字是 $[0,1)$ 上独立均匀分布的实数，则 $h(k) = \lfloor km \rfloor$ 满足简单均匀散列。实践中常用启发式方法，并利用关键字分布的定性信息：如编译器符号表中 pt 和 pts 这类相近符号常一起出现，好的散列函数应尽量让这些变体散列到不同槽。好方法是让散列值独立于数据中可能存在的任何模式，例如除以一个与关键字分布模式无关的素数取余。有些应用需要比简单均匀散列更强的性质，例如希望"相近"的关键字散列值相距很远（线性探查时尤其需要），全域散列往往能提供。

把关键字解释为自然数：多数散列函数假设全域为自然数集 $\mathbb N = \{0,1,2,\dots\}$。字符串可按适当基数表示为整数：pt 在 ASCII 中是 (112, 116)，按 128 进制为 $112 \times 128 + 116 = 14452$。

11.3.1 除法散列

h(k) = k \bmod m.

例：$m=12, k=100$ 时 $h(k)=4$。只需一次除法，很快。

应避免某些 $m$：$m$ 不应是 2 的幂，若 $m = 2^p$，$h(k)$ 就只是 $k$ 的最低 $p$ 位；除非知道低 $p$ 位模式等可能，否则应让散列依赖关键字所有位。
若 $k$ 是以 $2^p$ 为基数解释的字符串，取 $m = 2^p - 1$ 很糟：字符置换后散列值不变（习题 11.3-3）。
好的选择：不太接近 2 的整数幂的素数。例：用链接法存约 $n=2000$ 个字符串（每字符 8 位），能接受不成功搜索平均查 3 个元素，取 $m = 701$（接近 $2000/3$ 的素数，不接近 2 的幂），$h(k) = k \bmod 701$。

11.3.2 乘法散列

两步：用常数 $A$（$0<A<1$）乘 $k$ 取小数部分，再乘以 $m$ 下取整：

h(k) = \lfloor m\,(kA \bmod 1) \rfloor,\quad kA \bmod 1 = kA - \lfloor kA \rfloor.

优点：$m$ 的取值不关键，通常取 $m = 2^p$，便于实现。设机器字长 $w$ 位、$k$ 可放进一个字，限定 $A = s/2^w$，$s$ 是 $0 < s < 2^w$ 的整数。用 $k$ 乘以 $w$ 位整数 $s = A\cdot 2^w$，得 $2w$ 位结果 $r_1 2^w + r_0$（$r_1$ 为高位字，$r_0$ 为低位字），所需 $p$ 位散列值就是 $r_0$ 的最高 $p$ 位（图 11.4）。对任意 $A$ 都可用，但有的 $A$ 更好；Knuth 建议

A \approx (\sqrt5 - 1)/2 = 0.6180339887\ldots \tag{11.2}

例：$k = 123456$，$p=14$，$m = 2^{14} = 16384$，$w = 32$。取最接近 $(\sqrt5-1)/2$ 的 $s/2^{32}$，即 $A = 2654435769/2^{32}$。$k \cdot s = 327706022297664 = 76300 \cdot 2^{32} + 17612864$，故 $r_1 = 76300$，$r_0 = 17612864$，$r_0$ 的最高 14 位得 $h(k) = 67$。

11.3.3 全域散列（Universal hashing，星号节）

动机：如果恶意对手知道固定的散列函数，可以选出 $n$ 个全部散列到同一槽的关键字，使平均检索时间 $\Theta(n)$。任何固定散列函数都有这种弱点；唯一有效的办法是以与实际关键字无关的方式随机选择散列函数。全域散列在执行开始时从精心设计的函数类中随机选一个函数，像随机快速排序一样，保证没有哪个输入总是引发最坏情况；同一输入在不同运行中表现可能不同，但对任何输入平均性能都好。编译器例子中，程序员选的标识符不再能稳定地导致差性能；只有当随机选中的函数恰好对这组标识符不好时才差，而这种概率小且对同样大小的任何标识符集都相同。

定义：$\mathcal H$ 是把 $U$ 映射到 $\{0,\dots,m-1\}$ 的有限散列函数集合。若对每对不同关键字 $k, l \in U$，满足 $h(k) = h(l)$ 的 $h \in \mathcal H$ 至多有 $|\mathcal H|/m$ 个，则称 $\mathcal H$ 是全域的（universal）。即随机选 $h$ 时，$k, l$ 冲突的概率不超过 $1/m$（相当于 $h(k)$、$h(l)$ 独立随机选取时的冲突概率）。

定理 11.3：从全域散列函数类中随机选 $h$，用链接法把 $n$ 个关键字散列到大小为 $m$ 的表 $T$ 中。若 $k$ 不在表中，则 $k$ 所散列到的链表期望长度 $E[n_{h(k)}] \le \alpha = n/m$；若 $k$ 在表中，则包含 $k$ 的链表期望长度 $E[n_{h(k)}] \le 1 + \alpha$。证明：期望是对散列函数的选取求的，不依赖关键字分布的任何假设。对不同关键字 $k,l$ 定义 $X_{kl} = I\{h(k)=h(l)\}$，由全域性 $E[X_{kl}] \le 1/m$。令 $Y_k = \sum_{l \in T, l \ne k} X_{kl}$（与 $k$ 散列到同一槽的其他关键字数），$E[Y_k] \le \sum_{l\in T, l\ne k} 1/m$。

$k \notin T$：$n_{h(k)} = Y_k$，其他关键字共 $n$ 个，$E[n_{h(k)}] \le n/m = \alpha$。
$k \in T$：$n_{h(k)} = Y_k + 1$，其他关键字 $n-1$ 个，$E[n_{h(k)}] \le (n-1)/m + 1 = 1 + \alpha - 1/m < 1 + \alpha$。

推论 11.4：用全域散列和链接法，在初始为空、有 $m$ 个槽的表上，处理任何包含 $O(m)$ 个 INSERT 的 $n$ 个 INSERT/SEARCH/DELETE 操作序列，期望时间 $\Theta(n)$。证明：插入数 $O(m)$ 故 $n=O(m)$、$\alpha = O(1)$；INSERT/DELETE 常数时间，由定理 11.3 每次 SEARCH 期望 $O(1)$；由期望线性性总计 $O(n)$；每个操作 $\Omega(1)$，所以 $\Theta(n)$。意义：对手再也无法挑出迫使最坏运行时间的操作序列。

构造全域散列函数类：选足够大的素数 $p$，使所有可能的关键字都在 $0..p-1$ 内。记 $\mathbb Z_p = \{0,1,\dots,p-1\}$，$\mathbb Z_p^* = \{1,\dots,p-1\}$。由于全域大于槽数，$p > m$。对 $a \in \mathbb Z_p^*$、$b \in \mathbb Z_p$ 定义

h_{ab}(k) = ((ak + b) \bmod p) \bmod m, \tag{11.3}

\mathcal H_{pm} = \{h_{ab} : a \in \mathbb Z_p^*, b \in \mathbb Z_p\}. \tag{11.4}

例：$p=17, m=6$，$h_{3,4}(8) = ((24+4) \bmod 17) \bmod 6 = 11 \bmod 6 = 5$。每个 $h_{ab}$ 把 $\mathbb Z_p$ 映到 $\mathbb Z_m$；输出范围大小 $m$ 是任意的（不必是素数），11.5 节会用到。该类共 $p(p-1)$ 个函数。

定理 11.5：$\mathcal H_{pm}$ 是全域的。证明：取不同的 $k, l \in \mathbb Z_p$，令 $r = (ak+b) \bmod p$，$s = (al+b) \bmod p$。

$r \ne s$：因为 $r - s \equiv a(k-l) \pmod p$，$p$ 是素数且 $a$、$k-l$ 模 $p$ 都非零，乘积模 $p$ 非零（定理 31.6）。所以在"模 $p$ 层"没有冲突。
$(a,b)$（$a\ne0$）的 $p(p-1)$ 种选择与 $(r,s)$（$r\ne s$）的 $p(p-1)$ 种取值一一对应：给定 $r,s$ 可解出 $a = ((r-s)((k-l)^{-1} \bmod p)) \bmod p$，$b = (r - ak) \bmod p$。所以随机均匀选 $(a,b)$ 时，$(r,s)$ 等可能是任意一对不同的模 $p$ 值。
于是 $k,l$ 冲突的概率等于随机选取的不同值 $r,s$ 满足 $r \equiv s \pmod m$ 的概率。固定 $r$，在其余 $p-1$ 个 $s$ 中满足 $s\ne r$ 且 $s \equiv r \pmod m$ 的个数至多 $\lceil p/m \rceil - 1 \le ((p+m-1)/m) - 1 = (p-1)/m$。概率至多 $((p-1)/m)/(p-1) = 1/m$。故 $\Pr\{h_{ab}(k) = h_{ab}(l)\} \le 1/m$。

习题 11.3 概括：11.3-1 链表中每个元素带长字符串关键字及其散列值，搜索时先比较散列值再比较字符串；11.3-2 把 $r$ 个字符的 128 进制长串用常数个字的存储做除法散列（Horner 法则逐位取模）；11.3-3 $m = 2^p - 1$ 时字符置换不变性及其不良应用；11.3-4 计算 $m=1000$、$A=(\sqrt5-1)/2$ 时 61–65 的散列位置；11.3-5（星号）$\epsilon$-全域族必有 $\epsilon \ge 1/|B| - 1/|U|$；11.3-6（星号）多项式散列 $h_b(\langle a_0,\dots,a_{n-1}\rangle) = (\sum_j a_j b^j) \bmod p$ 构成的族是 $((n-1)/p)$-全域的。

11.4 开放寻址法（Open addressing）（PDF p.290–298）

开放寻址中所有元素都存在散列表本身，每个表项要么是动态集合的元素，要么是 NIL；没有链表，也没有元素存在表外。因此表可能被"填满"，装载因子 $\alpha$ 永远不超过 1。它完全避免了指针：不沿指针走，而是计算要检查的槽序列；省下的指针内存可以提供更多槽，可能带来更少冲突和更快检索。

插入时连续地检查（称为探查（probe））散列表，直到找到空槽。探查顺序不是固定的 $0,1,\dots,m-1$（那样需 $\Theta(n)$），而是取决于关键字：把散列函数扩展为以探查号（probe number）（从 0 开始）为第二输入：

h: U \times \{0,1,\dots,m-1\} \to \{0,1,\dots,m-1\}.

要求对每个 $k$，探查序列（probe sequence） $\langle h(k,0), h(k,1), \dots, h(k,m-1)\rangle$ 是 $\langle 0,1,\dots,m-1\rangle$ 的一个排列，从而表填满前每个位置都会被考虑。以下假设表中元素就是关键字（无卫星数据）。

def HASH_INSERT(T, k):
    for i in range(m):              # i = 0 .. m-1
        j = h(k, i)
        if T[j] is NIL:
            T[j] = k
            return j
    raise Error("hash table overflow")

def HASH_SEARCH(T, k):
    for i in range(m):
        j = h(k, i)
        if T[j] == k:
            return j
        if T[j] is NIL:             # 若 k 存在，当初就会插在这里
            return NIL
    return NIL

删除的困难：删除槽 $i$ 中的关键字时，不能简单置 NIL，否则那些插入时探查过槽 $i$ 并发现它已被占的关键字将找不到。解决：存入特殊值 DELETED；HASH-INSERT 把 DELETED 槽当作空槽可以插入；HASH-SEARCH 无需修改，遇到 DELETED 继续往下查。但这样搜索时间不再仅取决于 $\alpha$，所以需要删除关键字时更常用链接法。

均匀散列（uniform hashing）假设：每个关键字的探查序列等可能是 $\langle 0,\dots,m-1\rangle$ 的 $m!$ 种排列中的任一种。它把简单均匀散列从"一个值"推广到"整个探查序列"。真正的均匀散列难实现，实践中用近似（如双重散列）。下面三种常用技术都保证探查序列是排列，但都不满足均匀散列假设，因为它们最多只能产生 $m^2$ 种探查序列（而不是 $m!$）；双重散列产生的序列最多，效果最好。

线性探查（linear probing）

给定普通散列函数 $h': U \to \{0,\dots,m-1\}$（称辅助散列函数（auxiliary hash function）），

h(k,i) = (h'(k) + i) \bmod m,\quad i = 0,1,\dots,m-1.

先探查 $T[h'(k)]$，再 $T[h'(k)+1]$，……到 $T[m-1]$ 后环绕到 $T[0], T[1], \dots$，直到 $T[h'(k)-1]$。初始探查位置决定整个序列，所以只有 $m$ 种不同探查序列。易实现，但存在一次群集（primary clustering）：被占槽形成长串，增加平均搜索时间。原因是一个前面有 $i$ 个满槽的空槽下一个被填的概率是 $(i+1)/m$，长串越来越长。

二次探查（quadratic probing）

h(k,i) = (h'(k) + c_1 i + c_2 i^2) \bmod m, \tag{11.5}

$c_1, c_2$ 为正的辅助常数。后续位置的偏移按探查号的二次方式变化。比线性探查好得多，但为了充分利用表，$c_1, c_2, m$ 的取值受限（思考题 11-3 给出一种选法）。若两个关键字初始探查位置相同，则整个探查序列相同（$h(k_1,0) = h(k_2,0) \Rightarrow h(k_1,i) = h(k_2,i)$），导致较轻的二次群集（secondary clustering）。同样只有 $m$ 种探查序列。

双重散列（double hashing）

开放寻址最好的方法之一，产生的排列具有随机排列的许多特征：

h(k,i) = (h_1(k) + i\,h_2(k)) \bmod m,

$h_1, h_2$ 均为辅助散列函数。初始探查 $T[h_1(k)]$，之后每次偏移 $h_2(k)$（模 $m$）。探查序列以两种方式依赖于 $k$（初始位置、步长或两者都可能不同）。

图 11.5 例：$m=13$，$h_1(k) = k \bmod 13$，$h_2(k) = 1 + (k \bmod 11)$。插入 14：$14 \equiv 1 \pmod{13}$，$14 \equiv 3 \pmod{11}$，所以先查槽 1（被 79 占），再查槽 5（被 98 占），再查槽 9（空），放入槽 9。

要求：$h_2(k)$ 必须与 $m$ 互素，才能搜索整个表（习题 11.4-4）。两种办法：(1) $m$ 取 2 的幂，$h_2$ 总产生奇数；(2) $m$ 取素数，$h_2$ 总返回小于 $m$ 的正整数，例如

h_1(k) = k \bmod m,\quad h_2(k) = 1 + (k \bmod m'),

$m'$ 略小于 $m$（如 $m-1$）。例：$k=123456$，$m=701$，$m'=700$，则 $h_1(k)=80$，$h_2(k)=257$：先查位置 80，然后每隔 257 个槽（模 $m$）查一次。

当 $m$ 为素数或 2 的幂时，每个 $(h_1(k), h_2(k))$ 对给出不同的探查序列，共 $\Theta(m^2)$ 种（线性/二次探查只有 $\Theta(m)$ 种），性能非常接近理想的均匀散列。其他 $m$ 原则上可以，但难以高效地生成与 $m$ 互素的 $h_2(k)$，部分原因是这类数的相对密度 $\phi(m)/m$ 可能很小。

开放寻址的分析

仍用 $\alpha = n/m$，每槽至多一个元素，$n \le m$，$\alpha \le 1$。假设均匀散列（给定关键字的探查序列是固定的；这里是指在关键字分布和散列函数作用下，每种探查序列等可能）。

定理 11.6：开放寻址散列表装载因子 $\alpha = n/m < 1$，在均匀散列假设下，不成功搜索的期望探查次数至多 $1/(1-\alpha)$。证明：不成功搜索中除最后一次外每次探查都访问一个被占用且不含目标关键字的槽，最后一次访问空槽。设 $X$ 为探查次数，事件 $A_i$ 为"发生第 $i$ 次探查且探查到被占槽"。$\{X \ge i\} = A_1 \cap \dots \cap A_{i-1}$，

\Pr\{A_1\cap\cdots\cap A_{i-1}\} = \Pr\{A_1\}\Pr\{A_2\mid A_1\}\cdots\Pr\{A_{i-1}\mid A_1\cap\cdots\cap A_{i-2}\}.

$\Pr\{A_1\} = n/m$；对 $j>1$，在前 $j-1$ 次都探查到被占槽的条件下，第 $j$ 次也探查到被占槽的概率是 $(n-j+1)/(m-j+1)$（在剩下 $m-(j-1)$ 个未查槽中找到剩余 $n-(j-1)$ 个元素之一）。由 $n<m$ 得 $(n-j)/(m-j) \le n/m$，所以

\Pr\{X \ge i\} = \frac nm\cdot\frac{n-1}{m-1}\cdots\frac{n-i+2}{m-i+2} \le \left(\frac nm\right)^{i-1} = \alpha^{i-1}.

由 $E[X] = \sum_{i\ge1}\Pr\{X\ge i\}$（式 C.25）：

E[X] \le \sum_{i=1}^\infty \alpha^{i-1} = \sum_{i=0}^\infty \alpha^i = \frac{1}{1-\alpha}.

直观解释：$1/(1-\alpha) = 1 + \alpha + \alpha^2 + \cdots$：第一次探查总要做；约以概率 $\alpha$ 第一次碰到占用槽需第二次；约以概率 $\alpha^2$ 前两次都占用需第三次……数值：表半满时不成功搜索平均至多 $1/(1-0.5) = 2$ 次；90% 满时至多 10 次。

推论 11.7：均匀散列下，向装载因子 $\alpha$ 的开放寻址表插入一个元素平均至多 $1/(1-\alpha)$ 次探查。证明：只有有空位时才插入，$\alpha<1$；插入 = 一次不成功搜索 + 放入找到的第一个空槽。

定理 11.8：$\alpha < 1$，在均匀散列且表中每个关键字等可能被搜索的假设下，成功搜索的期望探查次数至多

\frac1\alpha \ln\frac{1}{1-\alpha}.

证明：搜索 $k$ 重现插入 $k$ 时的探查序列。若 $k$ 是第 $i+1$ 个插入的，由推论 11.7 期望探查至多 $1/(1-i/m) = m/(m-i)$。对 $n$ 个关键字平均：

\frac1n\sum_{i=0}^{n-1}\frac{m}{m-i} = \frac mn\sum_{i=0}^{n-1}\frac{1}{m-i} = \frac1\alpha\sum_{k=m-n+1}^{m}\frac1k \le \frac1\alpha\int_{m-n}^{m}\frac{dx}{x} = \frac1\alpha\ln\frac{m}{m-n} = \frac1\alpha\ln\frac{1}{1-\alpha}.

数值：半满时成功搜索期望探查少于 1.387 次；90% 满时少于 2.559 次。

习题 11.4 概括：11.4-1 用 $m=11$ 分别以线性探查、二次探查（$c_1=1,c_2=3$）、双重散列（$h_1=k$，$h_2 = 1 + (k \bmod (m-1))$）插入 10,22,31,4,15,28,17,88,59；11.4-2 写 HASH-DELETE 并修改 HASH-INSERT 以处理 DELETED；11.4-3 计算 $\alpha = 3/4$ 和 $7/8$ 时成功/不成功搜索的探查上界（不成功：4、8；成功：约 1.85、2.38）；11.4-4（星号）若 $\gcd(m, h_2(k)) = d \ge 1$，不成功搜索只查表的 $1/d$ 便回到起点；11.4-5（星号）求使不成功搜索期望探查数等于成功搜索两倍的非零 $\alpha$（约 0.7）。

11.5 完全散列（Perfect hashing，星号节）（PDF p.298–303）

当关键字集合是静态的（static）（存入后不再改变，如编程语言的保留字、CD-ROM 上的文件名），散列也能提供最坏情况的优秀性能。若搜索在最坏情况下只需 $O(1)$ 次内存访问，称为完全散列（perfect hashing）。

方案：两级散列，每级都用全域散列（图 11.6）。

第一级与链接法基本相同：用从全域散列族（$\mathcal H_{pm}$，$p$ 为大于所有关键字的素数）中精心选取的 $h$ 把 $n$ 个关键字散列到 $m$ 个槽。
但不为槽 $j$ 建链表，而是建一个小的二级散列表 $S_j$，配散列函数 $h_j \in \mathcal H_{p,m_j}$。精心选 $h_j$ 可保证二级无冲突。为此令 $S_j$ 的大小 $m_j = n_j^2$（$n_j$ 为散列到槽 $j$ 的关键字数）。虽然平方关系看似会使总存储过大，但选好第一级函数可以让期望总空间为 $O(n)$。
脚注：$n_j = m_j = 1$ 时不需要散列函数，取 $a = b = 0$。

图 11.6 例：$K = \{10,22,37,40,52,60,70,72,75\}$，外层 $h(k) = ((ak+b) \bmod p) \bmod m$，$a=3, b=42, p=101, m=9$。$h(75) = 2$，所以 75 进入槽 2；二级表 $S_j$ 大小 $m_j = n_j^2$，$h_j(k) = ((a_jk+b_j) \bmod p) \bmod m_j$；$h_2(75) = 7$，所以 75 存在 $S_2$ 的槽 7。所有二级表都无冲突，最坏常数时间搜索。

定理 11.9：用从全域类中随机选取的 $h$ 把 $n$ 个关键字存入大小 $m = n^2$ 的表，出现任何冲突的概率小于 $1/2$。证明：共有 $\binom n2$ 对可能冲突，每对冲突概率 $1/m$。冲突数 $X$ 的期望

E[X] = \binom n2\cdot\frac{1}{n^2} = \frac{n^2-n}{2}\cdot\frac{1}{n^2} < \frac12

（类似 5.4.1 节生日悖论分析）。由 Markov 不等式 $\Pr\{X \ge t\} \le E[X]/t$，取 $t=1$ 即得。因此随机选的 $h$ 更可能无冲突；对静态集合 $K$，试几次就能找到无冲突函数。但 $n$ 大时 $m = n^2$ 太大，所以只在每个槽内部用定理 11.9 的方法：外层把关键字散列到 $m = n$ 个槽，槽 $j$ 用大小 $m_j = n_j^2$ 的二级表。

存储为 $O(n)$：第一级 $m = n$ 时，主表、各 $m_j$、各二级函数参数 $a_j, b_j$ 共 $O(n)$。关键是二级表总大小。

定理 11.10：用全域类中随机选的 $h$ 把 $n$ 个关键字存入大小 $m = n$ 的表，则

E\left[\sum_{j=0}^{m-1} n_j^2\right] < 2n.

证明：利用恒等式 $a^2 = a + 2\binom a2$（式 11.6，对非负整数 $a$）：

E\Big[\sum_j n_j^2\Big] = E\Big[\sum_j n_j\Big] + 2E\Big[\sum_j\binom{n_j}{2}\Big] = n + 2E\Big[\sum_j\binom{n_j}{2}\Big].

$\sum_j \binom{n_j}{2}$ 正是表中冲突的关键字对总数，由全域性期望至多 $\binom n2\frac1m = \frac{n(n-1)}{2m} = \frac{n-1}{2}$（$m=n$）。所以 $E[\sum n_j^2] \le n + 2\cdot\frac{n-1}{2} = 2n - 1 < 2n$。

推论 11.11：同上设定且 $m_j = n_j^2$，所有二级表期望总存储 $E[\sum_j m_j] = E[\sum_j n_j^2] < 2n$（式 11.7）。

推论 11.12：同上设定，二级表总存储 $\ge 4n$ 的概率小于 $1/2$。证明：对式 11.7 用 Markov 不等式，$X = \sum m_j$，$t = 4n$：$\Pr\{\sum m_j \ge 4n\} \le E[\sum m_j]/(4n) < 2n/4n = 1/2$。所以试几个随机函数就能很快找到存储合理的一个。

习题 11.5-1（星号）：开放寻址 + 均匀散列下 $n$ 个关键字插入无冲突的概率 $p(n,m) \le e^{-n(n-1)/2m}$；$n$ 超过 $\sqrt m$ 时无冲突概率迅速趋于零。

第 11 章思考题（PDF p.303–305）

11-1 最长探查的界：开放寻址表大小 $m$，存 $n \le m/2$ 项。(a) 均匀散列下第 $i$ 次插入需要严格多于 $k$ 次探查的概率至多 $2^{-k}$；(b) 第 $i$ 次插入需多于 $2\lg n$ 次探查的概率为 $O(1/n^2)$；(c) 令 $X = \max_i X_i$，$\Pr\{X > 2\lg n\} = O(1/n)$；(d) 最长探查序列期望长度 $E[X] = O(\lg n)$。
11-2 链接法中槽大小的界：$n$ 个槽、$n$ 个关键字，等可能散列。$M$ 为最满槽中的关键字数，证明 $E[M] = O(\lg n/\lg\lg n)$。步骤：(a) 某特定槽恰有 $k$ 个关键字的概率 $Q_k = (1/n)^k(1-1/n)^{n-k}\binom nk$；(b) $P_k = \Pr\{M=k\} \le nQ_k$；(c) 由 Stirling 近似 $Q_k < e^k/k^k$；(d) 存在 $c>1$ 使 $k_0 = c\lg n/\lg\lg n$ 时 $Q_{k_0} < 1/n^3$，从而 $k \ge k_0$ 时 $P_k < 1/n^2$；(e) $E[M] \le \Pr\{M > c\lg n/\lg\lg n\}\cdot n + \Pr\{M \le c\lg n/\lg\lg n\}\cdot c\lg n/\lg\lg n$，得 $O(\lg n/\lg\lg n)$。（这是"球入箱"最大负载的经典结论。）
11-3 二次探查：$m$ 为 2 的幂，搜索方案：$j = h(k)$，$i=0$；探查位置 $j$，找到或空则终止；$i \leftarrow i+1$，若 $i = m$ 终止，否则 $j \leftarrow (i + j) \bmod m$ 继续。(a) 证明这是式 11.5 的特例（$c_1 = c_2 = 1/2$，即偏移为三角数 $i(i+1)/2$）；(b) 证明最坏情况下会检查所有位置。
11-4 散列与认证（authentication）：定义 $k$-全域（k-universal）：对任意 $k$ 个不同关键字的固定序列，随机 $h$ 下 $\langle h(x^{(1)}),\dots,h(x^{(k)})\rangle$ 等可能是 $m^k$ 种序列之一。(a) 2-全域 ⇒ 全域；(b) $U$ 为 $\mathbb Z_p$ 上的 $n$ 元组，$h_a(x) = (\sum_j a_jx_j) \bmod p$，证明 $\mathcal H = \{h_a\}$ 是全域但非 2-全域（提示：零向量对所有函数取相同值）；(c) 加常数项 $h'_{ab}(x) = (\sum_j a_jx_j + b) \bmod p$ 后是 2-全域的；(d) Alice 和 Bob 秘密约定 2-全域族中的 $h$，Alice 发送消息 $m$ 及认证标签 $t = h(m)$；对手截获后替换为 $(m', t')$，无论计算能力多强、即使知道族 $\mathcal H$，骗过 Bob 的概率至多 $1/p$。

章末注记

Knuth 与 Gonnet 是散列分析的经典参考。Knuth 认为 H. P. Luhn（1953）发明了散列表和链接法；几乎同时 G. M. Amdahl 提出开放寻址。Carter 与 Wegman 1979 年提出全域散列函数类。11.5 节的静态完全散列由 Fredman、Komlós、Szemerédi 提出；Dietzfelbinger 等将其扩展到动态集合，插入删除摊还期望 $O(1)$。

第 11 章本章要点

直接寻址：全域小时最坏 $O(1)$；散列表：空间 $\Theta(|K|)$，平均 $O(1)$，最坏 $\Theta(n)$。
链接法：简单均匀散列下成功/不成功搜索都是 $\Theta(1+\alpha)$；$n = O(m)$ 时所有字典操作平均 $O(1)$；支持删除时链表须双向。
散列函数：除法法取远离 2 的幂的素数 $m$；乘法法 $m$ 可取 $2^p$，$A \approx 0.618$；全域散列 $h_{ab}(k) = ((ak+b)\bmod p)\bmod m$ 使任意两键冲突概率 $\le 1/m$，可抵御对手构造的坏输入。
开放寻址：均匀散列下不成功搜索/插入 $\le 1/(1-\alpha)$ 次探查，成功搜索 $\le \frac1\alpha\ln\frac1{1-\alpha}$；双重散列最接近均匀散列；删除需 DELETED 标记，故需要删除时多用链接法。
完全散列：静态集合用两级全域散列，二级表大小 $n_j^2$，最坏 $O(1)$ 查找、期望 $O(n)$ 空间。

第 11 章与量化交易的关联

系统实现：散列表是交易系统最基础的组件——订单 ID → 订单对象、证券代码 → 行情/持仓对象、因子名 → 计算结果缓存。撮合引擎中"散列表 + 双向链表"实现 $O(1)$ 撤单；Python dict、C++ unordered_map/开放寻址表（如 abseil flat_hash_map）就是本章两种冲突策略的工程化版本。
延迟与最坏情况：低延迟交易关心尾延迟而非平均值。本章指出散列的最坏情况是 $\Theta(n)$，开放寻址在 $\alpha$ 接近 1 时探查次数急剧上升（90% 满时不成功搜索平均 10 次），所以实盘系统要预分配容量、控制装载因子、避免运行时 rehash；若代码集合固定（如当日证券列表），可以用完全散列做最坏 $O(1)$ 查找。
数据处理与回测：大规模面板数据的 groupby/join（按代码、日期聚合）底层就是散列；全域散列/随机种子可防止特定键分布造成性能退化。思考题 11-4 的认证标签思想对应消息完整性校验，与交易通信安全有间接关系。
与因子研究、风险模型、定价的数学内容无直接关联。

第 11 章推荐习题

11.2-1、11.2-3：期望冲突数与有序链表的影响，巩固装载因子分析。
11.3-4：手算乘法散列。
11.4-1、11.4-2：三种探查方式手工模拟与 DELETED 处理，理解开放寻址删除陷阱。
11.4-3：给定装载因子估算探查次数，帮助做容量规划。
思考题 11-2：链接法最大链长 $O(\lg n/\lg\lg n)$，练习概率界。
思考题 11-4：$k$-全域与消息认证，理解随机化与对抗模型。

第 12 章二叉搜索树（Binary Search Trees）（PDF p.307–328）

搜索树支持 SEARCH、MINIMUM、MAXIMUM、PREDECESSOR、SUCCESSOR、INSERT、DELETE 等许多操作，所以既可作字典也可作优先队列。二叉搜索树的基本操作时间与树高成正比：$n$ 结点完全二叉树为 $\Theta(\lg n)$ 最坏；若树退化为 $n$ 个结点的链，则为 $\Theta(n)$。12.4 节证明随机构造的二叉搜索树期望高度 $O(\lg n)$。实践中不能总保证随机构造，所以第 13 章给出高度 $O(\lg n)$ 的红黑树，第 18 章的 B 树适合磁盘上的数据库。树的基本数学性质见附录 B。

12.1 什么是二叉搜索树（PDF p.307–310）

二叉搜索树（binary search tree）组织为一棵二叉树，用链式结构表示：每个结点除 key 和卫星数据外，有 left、right、p 指向左孩子、右孩子、父结点；缺失时为 NIL。根是唯一父结点为 NIL 的结点。

二叉搜索树性质（binary-search-tree property）：设 $x$ 是树中结点。若 $y$ 在 $x$ 的左子树中，则 $y.key \le x.key$；若 $y$ 在 $x$ 的右子树中，则 $y.key \ge x.key$。

图 12.1：(a) 6 个结点、高度 2 的树，根为 6，左子树键 2、5、5 都不大于 6，右子树 7、8 都不小于 6；(b) 同样关键字、高度 4 的低效树。同一集合可对应不同的二叉搜索树；多数操作的最坏时间与树高成正比。

中序遍历（inorder tree walk）：先递归输出左子树，再输出根，再递归输出右子树，可按序输出所有关键字。类似地，**先序遍历（preorder）**先输出根，**后序遍历（postorder）**最后输出根。

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 两棵树的中序输出均为 2,5,5,6,7,8。正确性由二叉搜索树性质归纳可得。

定理 12.1：若 $x$ 是 $n$ 结点子树的根，INORDER-TREE-WALK(x) 需 $\Theta(n)$ 时间。证明：访问所有 $n$ 个结点故 $T(n) = \Omega(n)$。空子树上 $T(0) = c$。$n>0$ 时设左子树 $k$ 个结点、右子树 $n-k-1$ 个，$T(n) \le T(k) + T(n-k-1) + d$。用代入法证 $T(n) \le (c+d)n + c$：$n=0$ 成立；$n>0$ 时 $T(n) \le ((c+d)k + c) + ((c+d)(n-k-1) + c) + d = (c+d)n + c - (c+d) + c + d = (c+d)n + c$。

习题 12.1 概括：12.1-1 对 $\{1,4,5,10,16,17,21\}$ 画高度 2–6 的二叉搜索树；12.1-2 二叉搜索树性质与最小堆性质的区别，最小堆性质不能在 $O(n)$ 内按序输出（否则违反比较排序下界）；12.1-3 非递归中序遍历（用栈；或不用栈但需比较指针相等）；12.1-4 先序/后序遍历；12.1-5 由于比较排序最坏 $\Omega(n\lg n)$，任何基于比较的从任意列表构造 BST 的算法最坏也要 $\Omega(n\lg n)$（因为构造后中序遍历 $O(n)$ 即可排序）。

12.2 查询二叉搜索树（PDF p.310–315）

本节所有查询都在高度为 $h$ 的树上 $O(h)$ 时间完成。

搜索：

def TREE_SEARCH(x, k):              # 递归版
    if x is NIL or k == x.key:
        return x
    if k < x.key:
        return TREE_SEARCH(x.left, k)
    return TREE_SEARCH(x.right, k)

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

从根开始沿一条向下的简单路径：$k$ 小于 $x.key$ 则进左子树（由性质知 $k$ 不可能在右子树），大于则进右子树。时间 $O(h)$。图 12.2 例：查找 13 的路径为 15→6→7→13。

最小值和最大值：从根一直沿 left 指针走到 NIL 即最小；沿 right 即最大。

def TREE_MINIMUM(x):    # 假定 x 非 NIL
    while x.left is not NIL:
        x = x.left
    return x

def TREE_MAXIMUM(x):
    while x.right is not NIL:
        x = x.right
    return x

正确性：若 $x$ 无左子树，右子树中的键都 $\ge x.key$，所以最小是 $x.key$；若有左子树，最小值在左子树中。时间 $O(h)$。图 12.2 中最小为 2，最大为 20。

后继和前驱：后继是中序遍历次序中的下一个结点；关键字互异时是大于 $x.key$ 的最小键所在结点。可以不比较关键字，仅凭树结构找到。

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

情况 1：右子树非空，后继是右子树中最左的结点（例：15 的后继是 17）。
情况 2：右子树为空且后继 $y$ 存在，则 $y$ 是 $x$ 的最低祖先，且 $y$ 的左孩子也是 $x$ 的祖先（每个结点是其自身的祖先）。从 $x$ 往上走，直到遇到某个结点是其父结点的左孩子，该父结点即后继（例：13 的后继是 15）。时间 $O(h)$（沿树向上或向下一条简单路径）。TREE-PREDECESSOR 对称，也是 $O(h)$。关键字不互异时，把后继/前驱定义为这两个过程的返回结果。

定理 12.2：SEARCH、MINIMUM、MAXIMUM、SUCCESSOR、PREDECESSOR 在高度 $h$ 的二叉搜索树上都可在 $O(h)$ 时间完成。

习题 12.2 概括：12.2-1 判断哪些查找序列不可能出现（检查序列是否在区间不断收缩，c、e 不可能）；12.2-2 递归版 MIN/MAX；12.2-3 写 TREE-PREDECESSOR；12.2-4 Bunyan 教授关于搜索路径左/上/右三集合 $a\le b\le c$ 的错误断言，找最小反例；12.2-5 有两个孩子的结点，其后继无左孩子、前驱无右孩子；12.2-6 证明情况 2 的刻画；12.2-7 用 TREE-MINIMUM + $n-1$ 次 TREE-SUCCESSOR 做中序遍历为 $\Theta(n)$（每条边最多走两次）；12.2-8 从任意结点连续 $k$ 次 SUCCESSOR 共 $O(k+h)$；12.2-9 叶结点 $x$ 的父结点 $y$ 的键要么是大于 $x.key$ 的最小键，要么是小于 $x.key$ 的最大键。

12.3 插入和删除（PDF p.315–320）

插入较直接；删除较复杂。二者都要保持二叉搜索树性质。

插入：TREE-INSERT 接收结点 $z$（$z.key = v$，$z.left = z.right = \text{NIL}$），把它放到树中合适位置。

def TREE_INSERT(T, z):
    y = NIL                 # 尾随指针：x 的父结点
    x = T.root
    while x is not NIL:     # 自根向下寻找要替换的 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

$x$ 沿一条简单路径向下寻找一个 NIL 用 $z$ 替换；需要尾随指针 $y$，因为找到 NIL 时已越过需要修改的结点一步。时间 $O(h)$。图 12.3：把 13 插入树中，沿 12→18→15 走到 15 的左孩子位置。

删除的三种基本情况：

$z$ 无孩子：修改父结点，用 NIL 替换 $z$。
$z$ 只有一个孩子：把孩子提升到 $z$ 的位置。
$z$ 有两个孩子：找到 $z$ 的后继 $y$（必在 $z$ 的右子树中），让 $y$ 占据 $z$ 的位置；$z$ 原右子树的其余部分成为 $y$ 的新右子树，$z$ 的左子树成为 $y$ 的新左子树。这种情况较棘手，因为 $y$ 是否为 $z$ 的右孩子有区别。

实际代码按图 12.4 的四种情况组织：

(a) $z$ 无左孩子：用右孩子 $r$（可能为 NIL）替换 $z$。涵盖"无孩子"和"只有右孩子"。
(b) $z$ 只有左孩子 $l$：用 $l$ 替换 $z$。
否则 $z$ 有两个孩子，找后继 $y$（在右子树中，且无左孩子，见习题 12.2-5）：
- (c) $y$ 是 $z$ 的右孩子：直接用 $y$ 替换 $z$，保留 $y$ 的右孩子 $x$，令 $z$ 的左孩子 $l$ 成为 $y$ 的左孩子。
- (d) $y$ 在 $z$ 的右子树中但不是右孩子：先用 $y$ 的右孩子 $x$ 替换 $y$，让 $y$ 成为 $r$ 的父结点；再用 $y$ 替换 $z$，让 $y$ 成为 $l$ 的父结点。

子过程 TRANSPLANT 用以 $v$ 为根的子树替换以 $u$ 为根的子树：$u$ 的父结点变成 $v$ 的父结点，且 $u$ 的父结点以 $v$ 为相应孩子。

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
    # 注意：不更新 v.left / v.right，这是调用者的责任

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)            # z 的后继
        if y.p != z:                         # 情况 (d)
            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

除第 5 行的 TREE-MINIMUM 外每行都是常数时间，所以 TREE-DELETE 为 $O(h)$。

定理 12.3：INSERT 和 DELETE 在高度 $h$ 的二叉搜索树上都可在 $O(h)$ 时间完成。

习题 12.3 概括：12.3-1 递归版 TREE-INSERT；12.3-2 搜索某值检查的结点数 = 插入它时检查的结点数 + 1；12.3-3 用 BST 插入 + 中序遍历排序，最坏 $\Theta(n^2)$（有序输入），最好 $\Theta(n\lg n)$；12.3-4 删除是否"可交换"（不可交换，给反例）；12.3-5 结点只存后继指针 succ 而不存父指针，实现 $O(h)$ 的 SEARCH/INSERT/DELETE；12.3-6 两孩子时改用前驱代替后继需改动什么，以及前驱/后继交替使用的"公平策略"。

12.4 随机构造的二叉搜索树（Randomly built BST，星号节）（PDF p.320–324）

树高随插入删除变化：若按严格递增顺序插入 $n$ 项，树是高度 $n-1$ 的链；另一方面总有 $h \ge \lfloor \lg n\rfloor$（习题 B.5-4）。与快速排序类似，平均情况更接近最好情况。插入与删除混合时对平均高度所知甚少；仅插入时分析可行。定义 $n$ 个关键字上的随机构造二叉搜索树（randomly built binary search tree）：把关键字按随机顺序插入初始为空的树，$n!$ 种排列等可能。（习题 12.4-3：这与"所有 $n$ 键 BST 等可能"不同。）

定理 12.4：$n$ 个不同关键字的随机构造二叉搜索树期望高度为 $O(\lg n)$。

证明：

定义 $X_n$ 为高度，指数高度（exponential height） $Y_n = 2^{X_n}$。$R_n$ 为根关键字在 $n$ 个关键字中的秩（rank），等可能取 $1..n$。若 $R_n = i$，左子树是 $i-1$ 个键的随机构造树，右子树是 $n-i$ 个键的随机构造树。高度 = 1 + 两子树高度较大者，所以 $Y_n = 2\max(Y_{i-1}, Y_{n-i}).$ 基础：$Y_1 = 2^0 = 1$，约定 $Y_0 = 0$。
指示变量 $Z_{n,i} = I\{R_n = i\}$，$E[Z_{n,i}] = 1/n$（式 12.1），$Y_n = \sum_{i=1}^n Z_{n,i}(2\max(Y_{i-1},Y_{n-i}))$。
$Z_{n,i}$ 与 $Y_{i-1}$、$Y_{n-i}$ 独立：选定 $R_n = i$ 后，左子树就是在秩小于 $i$ 的 $i-1$ 个键上随机构造的树，除了键数外其结构不受 $R_n$ 影响；右子树同理。于是 $E[Y_n] = \sum_{i=1}^n E[Z_{n,i}]\,E[2\max(Y_{i-1},Y_{n-i})] = \frac2n\sum_{i=1}^n E[\max(Y_{i-1},Y_{n-i})] \le \frac2n\sum_{i=1}^n (E[Y_{i-1}] + E[Y_{n-i}]).$ 每个 $E[Y_0],\dots,E[Y_{n-1}]$ 出现两次，得递归式 $E[Y_n] \le \frac4n\sum_{i=0}^{n-1}E[Y_i]. \tag{12.2}$
用代入法证 $E[Y_n] \le \frac14\binom{n+3}{3}$，借助恒等式 $\sum_{i=0}^{n-1}\binom{i+3}{3} = \binom{n+3}{4}$（式 12.3，习题 12.4-1）。基础：$0 = E[Y_0] \le \frac14\binom33 = \frac14$；$1 = E[Y_1] \le \frac14\binom43 = 1$。归纳： $E[Y_n] \le \frac4n\sum_{i=0}^{n-1}\frac14\binom{i+3}{3} = \frac1n\binom{n+3}{4} = \frac1n\cdot\frac{(n+3)!}{4!(n-1)!} = \frac14\cdot\frac{(n+3)!}{3!\,n!} = \frac14\binom{n+3}{3}.$
$f(x) = 2^x$ 是凸函数（习题 12.4-4），由 Jensen 不等式 $2^{E[X_n]} \le E[2^{X_n}] = E[Y_n]$，所以 $2^{E[X_n]} \le \frac14\binom{n+3}{3} = \frac{(n+3)(n+2)(n+1)}{24} = \frac{n^3+6n^2+11n+6}{24}.$ 两边取对数得 $E[X_n] = O(\lg n)$。

技巧要点：直接分析 $E[\max]$ 困难，转而分析指数高度并用 $\max(a,b) \le a+b$ 放缩，最后用 Jensen 不等式回到高度。

习题 12.4 概括：12.4-1 证明式 12.3；12.4-2 构造平均结点深度 $\Theta(\lg n)$ 但高度 $\omega(\lg n)$ 的树，并给出这种树高度的渐近上界（$O(\sqrt{n\lg n})$）；12.4-3 $n=3$ 时比较两种"随机"概念；12.4-4 证明 $2^x$ 凸；12.4-5（星号）随机快速排序对除 $O(1/n^k)$ 比例外的所有输入排列都是 $O(n\lg n)$。

第 12 章思考题（PDF p.324–328）

12-1 带相等关键字的 BST：(a) 用 TREE-INSERT 插入 $n$ 个相同关键字的渐近性能（$\Theta(n^2)$，退化为链）。改进：在比较前检查 $z.key = x.key$，相等时采用：(b) 结点存布尔标志 $x.b$，每次遇到相等关键字时在左右之间交替；(c) 在结点上挂一个相等关键字的链表；(d) 随机选左或右（给出最坏性能并非正式推导期望时间）。分别求插入 $n$ 个相同项的渐近时间。
12-2 基数树（radix tree）：字典序定义——字符串 $a = a_0\dots a_p$ 小于 $b = b_0\dots b_q$，若 (1) 存在 $j \le \min(p,q)$ 使前 $j$ 位相同且 $a_j < b_j$，或 (2) $p<q$ 且 $a$ 是 $b$ 的前缀。例：$10100 < 10110$（规则 1，$j=3$），$10100 < 101000$（规则 2）。图 12.5 的基数树存储 1011、10、011、100、0：在深度 $i$ 处若 $a_i = 0$ 往左、为 1 往右；结点的键由根到它的路径决定，无需存储；深色结点不对应树中的键，只为通向其他结点而存在。题目：对长度总和为 $n$ 的不同位串集合 $S$，用基数树在 $\Theta(n)$ 内按字典序排序（例的输出：0, 011, 10, 100, 1011）——先序遍历即可。
12-3 随机构造 BST 的平均结点深度：证明平均深度 $O(\lg n)$（比定理 12.4 弱，但揭示与随机快速排序的相似性）。总路径长度 $P(T) = \sum_{x\in T} d(x,T)$。(a) 平均深度 $= P(T)/n$，需证 $E[P(T)] = O(n\lg n)$；(b) $P(T) = P(T_L) + P(T_R) + n - 1$；(c) 平均总路径长度 $P(n) = \frac1n\sum_{i=0}^{n-1}(P(i) + P(n-i-1) + n-1)$；(d) 改写为 $P(n) = \frac2n\sum_{k=1}^{n-1}P(k) + \Theta(n)$；(e) 结合思考题 7-3 得 $P(n) = O(n\lg n)$；(f) 描述一种快速排序实现，使排序所做的比较与把元素插入 BST 时所做的比较完全相同（顺序可不同）——BST 的每个结点就是对其子树元素做划分的主元。
12-4 不同二叉树的数目：$b_n$ 为 $n$ 结点不同二叉树数。(a) $b_0 = 1$，$b_n = \sum_{k=0}^{n-1}b_kb_{n-1-k}$；(b) 生成函数 $B(x) = \sum b_nx^n$ 满足 $B(x) = xB(x)^2 + 1$，闭式 $B(x) = \frac{1}{2x}(1 - \sqrt{1-4x})$；(c) 用 $\sqrt{1-4x}$ 在 0 处的 Taylor 展开（或广义二项式展开）证明 $b_n = \frac{1}{n+1}\binom{2n}{n}$（第 $n$ 个 Catalan 数）；(d) $b_n = \frac{4^n}{\sqrt\pi n^{3/2}}(1 + O(1/n))$。

章末注记

Knuth 对简单 BST 及其变体有很好的讨论；BST 大约在 1950 年代末被多人独立发现。基数树常被称为 trie（取自 retrieval 中间字母）。许多教材（包括本书前两版）在删除有两个孩子的结点时，删除后继 $y$ 并把 $y$ 的关键字和卫星数据复制到 $z$；缺点是实际被删的结点可能不是传入的那个，若程序其他部分持有指向树结点的指针，可能留下指向已删结点的"陈旧（stale）"指针。本版方法虽稍复杂，但保证删除 $z$ 时删除的就是 $z$ 本身。15.5 节介绍已知搜索频率时构造最优二叉搜索树。12.4 节的证明归功于 Aslam；Martínez 与 Roura 给出使结果仍为随机 BST 的随机化插入删除算法（其随机 BST 定义与本章略有不同）。

第 12 章本章要点

二叉搜索树性质：左子树键 $\le$ 结点键 $\le$ 右子树键；中序遍历 $\Theta(n)$ 输出有序序列。
SEARCH、MIN、MAX、SUCCESSOR、PREDECESSOR、INSERT、DELETE 都是 $O(h)$；$h$ 在 $\lfloor\lg n\rfloor$ 与 $n-1$ 之间。
后继的两种情况：右子树最左结点；或向上找第一个"作为左孩子"的祖先的父结点。
删除用 TRANSPLANT 分四种情况，保证删除的就是传入的结点。
随机构造 BST 期望高度 $O(\lg n)$：指数高度 + Jensen 不等式；BST 构造与随机快速排序的比较一一对应。

第 12 章与量化交易的关联

订单簿价格档位：限价订单簿需要按价格有序地维护档位，支持插入新价位、删除空价位、查最优价（MIN/MAX）、找相邻价位（SUCCESSOR/PREDECESSOR）。这正是有序动态集合；实盘用平衡树（第 13 章）或基于价格刻度的数组，普通 BST 因可能退化（例如价格单调变化时按顺序插入）不宜直接使用——12.4 节"按递增顺序插入得到链"的结论在行情单边走势时就会出现。
滚动分位数/排名：需要在滑动窗口上维护有序集合（滚动中位数、截面排名因子），基础是有序树结构，第 14 章的顺序统计树进一步支持 $O(\lg n)$ 求秩。
回测与数据检索：按时间戳查找最近的事件（"as-of join"，找不晚于 $t$ 的最后一笔报价）就是 PREDECESSOR 查询。
思考题 12-2 的 trie 在证券代码前缀检索、符号表中有应用，关联较弱。

第 12 章推荐习题

12.1-3：非递归中序遍历（栈/无栈两种）。
12.2-1、12.2-6、12.2-8：搜索路径性质与后继的刻画、连续后继的摊还界。
12.3-3：BST 排序的最好/最坏情况，联系快速排序。
12.3-6：前驱替代后继的删除变体。
思考题 12-3：随机 BST 与随机快速排序的等价性，概率分析的好练习。
思考题 12-4：Catalan 数与生成函数。

第 13 章红黑树（Red-Black Trees）（PDF p.329–359）

第 12 章说明高度为 $h$ 的二叉搜索树可在 $O(h)$ 内完成基本操作；树高大时不比链表快。红黑树是许多"平衡（balanced）"搜索树方案之一，保证基本动态集合操作最坏 $O(\lg n)$。

13.1 红黑树的性质（Properties of red-black trees）（PDF p.329–333）

红黑树是每个结点多一位存储——颜色（color）（RED 或 BLACK）——的二叉搜索树。通过约束从根到叶的任何简单路径上的结点颜色，保证没有一条路径比其他路径长出一倍以上，因而树近似平衡。结点属性：color、key、left、right、p。若孩子或父结点不存在，对应指针为 NIL；把这些 NIL 视为指向二叉搜索树的叶（外部结点，external nodes）的指针，而带关键字的普通结点是内部结点（internal nodes）。

红黑性质（red-black properties）：

每个结点是红色或黑色。
根是黑色。
每个叶（NIL）是黑色。
如果一个结点是红色，则它的两个孩子都是黑色（不能有连续两个红结点）。
对每个结点，从该结点到其所有后代叶的简单路径上，黑结点数目相同。

哨兵：为方便处理边界，用一个哨兵 $T.nil$ 代表所有 NIL（所有叶和根的父结点）。它与普通结点属性相同，color 为 BLACK，其余属性（p、left、right、key）可取任意值（过程中为了方便可以设置它们）。这样可以把结点 $x$ 的 NIL 孩子当作父结点为 $x$ 的普通结点。为每个 NIL 单独设哨兵虽能让每个 NIL 的父结点有定义，但浪费空间。画图时通常省略叶（图 13.1(c)）。

黑高（black-height） $bh(x)$：从结点 $x$（不含 $x$）出发到达一个叶的任意简单路径上的黑结点数。由性质 5 该定义良好。红黑树的黑高定义为根的黑高。

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

先证以任一结点 $x$ 为根的子树至少含 $2^{bh(x)} - 1$ 个内部结点，对 $x$ 的高度归纳。高度 0 时 $x$ 是叶（$T.nil$），$2^0 - 1 = 0$，成立。归纳步：$x$ 高度为正、是有两个孩子的内部结点；每个孩子的黑高为 $bh(x)$（孩子为红）或 $bh(x)-1$（孩子为黑）。孩子高度小于 $x$，由归纳假设每个孩子子树至少 $2^{bh(x)-1}-1$ 个内部结点，所以 $x$ 子树至少 $(2^{bh(x)-1}-1)+(2^{bh(x)-1}-1)+1 = 2^{bh(x)}-1$ 个。
设树高 $h$。由性质 4，从根到叶的任何简单路径上（不含根）至少一半结点是黑色，所以根的黑高至少 $h/2$，于是 $n \ge 2^{h/2} - 1$，即 $\lg(n+1) \ge h/2$，$h \le 2\lg(n+1)$。

推论：SEARCH、MINIMUM、MAXIMUM、SUCCESSOR、PREDECESSOR 在红黑树上都是 $O(\lg n)$（第 12 章算法中把 NIL 换成 $T.nil$）。TREE-INSERT 和 TREE-DELETE 虽然也是 $O(\lg n)$，但不保证结果仍是红黑树；13.3、13.4 节给出 $O(\lg n)$ 的保持红黑性质的插入与删除。

习题 13.1 概括：13.1-1 对 $\{1..15\}$ 的高度 3 完全 BST 给出黑高为 2、3、4 的三种着色；13.1-2 对图 13.1 用 TREE-INSERT 插入 36，染红/染黑是否仍是红黑树（红：违反性质 4；黑：违反性质 5）；13.1-3 "松弛红黑树"（根可红）把根染黑后仍是红黑树；13.1-4 把每个红结点并入黑父结点后，黑结点度数可能为 2、3、4，所有叶深度相同（即 2-3-4 树）；13.1-5 从 $x$ 出发的最长简单路径至多是最短路径的两倍；13.1-6 黑高为 $k$ 的红黑树内部结点数最多 $2^{2k}-1$、最少 $2^k-1$；13.1-7 红内部结点与黑内部结点之比最大约 2:1，最小为 0。

13.2 旋转（Rotations）（PDF p.333–335）

在红黑树上执行 TREE-INSERT/TREE-DELETE 可能违反红黑性质；恢复时需要修改某些结点的颜色和指针结构。指针结构的修改通过**旋转（rotation）**完成——一种保持二叉搜索树性质的局部操作。

**左旋（left rotation）**在结点 $x$ 上进行，假定其右孩子 $y \ne T.nil$：以 $x$–$y$ 链为"支点"，使 $y$ 成为子树新根，$x$ 成为 $y$ 的左孩子，$y$ 原左孩子成为 $x$ 的右孩子。
**右旋（right rotation）**是其逆操作。
图 13.2：设子树 $\alpha, \beta, \gamma$，旋转前后中序次序都是 $\alpha$ 中的键 < $x.key$ < $\beta$ 中的键 < $y.key$ < $\gamma$ 中的键。

def LEFT_ROTATE(T, x):        # 假定 x.right != T.nil，根的父结点为 T.nil
    y = x.right                       # 设置 y
    x.right = y.left                  # y 的左子树成为 x 的右子树
    if y.left is not T.nil:
        y.left.p = x
    y.p = x.p                         # 把 x 的父结点连接到 y
    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 放在 y 的左边
    x.p = y

RIGHT-ROTATE 对称。两者均 $O(1)$，只改变指针，结点其他属性不变。图 13.3 示例：对键 11 的结点左旋后，其右孩子 18 上升，18 的左子树（根 14）成为 11 的右子树；两棵树的中序遍历输出相同。

习题 13.2 概括：13.2-1 写 RIGHT-ROTATE；13.2-2 $n$ 结点 BST 恰有 $n-1$ 种可能的旋转（每条边一种）；13.2-3 左旋后 $\alpha$ 中结点深度 +1、$\beta$ 不变、$\gamma$ 中 −1；13.2-4 任意 $n$ 结点 BST 可用 $O(n)$ 次旋转变为任意另一棵（先用至多 $n-1$ 次右旋变成右链）；13.2-5（星号）"右转换"的不可达例子及 $O(n^2)$ 次右旋上界。

13.3 插入（Insertion）（PDF p.336–343）

先像普通 BST 一样插入 $z$ 并染红（习题 13.3-1 问为何染红而不是黑：染黑必然破坏性质 5，而染红只可能破坏性质 2 或 4，且易修复），再调用 RB-INSERT-FIXUP 重新着色并旋转。

def RB_INSERT(T, z):
    y = T.nil
    x = T.root
    while x is not T.nil:
        y = x
        x = x.left if z.key < x.key else x.right
    z.p = y
    if y is T.nil:
        T.root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z
    z.left = T.nil
    z.right = T.nil
    z.color = RED
    RB_INSERT_FIXUP(T, z)

与 TREE-INSERT 的四点不同：NIL 全部换成 $T.nil$；把 $z$ 的 left、right 设为 $T.nil$；把 $z$ 染红；调用 RB-INSERT-FIXUP 恢复红黑性质。

def RB_INSERT_FIXUP(T, z):
    while z.p.color == RED:
        if z.p == z.p.p.left:
            y = z.p.p.right                 # y 是 z 的叔结点（uncle）
            if y.color == RED:              # 情况 1：叔结点红
                z.p.color = BLACK
                y.color = BLACK
                z.p.p.color = RED
                z = z.p.p                   # z 上移两层
            else:
                if z == z.p.right:          # 情况 2：叔黑，z 是右孩子
                    z = z.p
                    LEFT_ROTATE(T, z)       # 转化为情况 3
                z.p.color = BLACK           # 情况 3：叔黑，z 是左孩子
                z.p.p.color = RED
                RIGHT_ROTATE(T, z.p.p)
        else:
            ...  # 与 then 分支对称（left 与 right 互换）
    T.root.color = BLACK

（情况 2 会落入情况 3，二者不互斥。）

可能被破坏的性质：性质 1、3 仍成立（新红结点的两个孩子是黑哨兵）；性质 5 也成立（$z$ 替换了一个黑哨兵，而 $z$ 是红的且孩子是哨兵）。只可能破坏性质 2（$z$ 是根）或性质 4（$z$ 的父结点是红色），都因 $z$ 染红导致。

循环不变式（每次迭代开始时）：

(a) $z$ 是红色。
(b) 若 $z.p$ 是根，则 $z.p$ 是黑色。
(c) 若树违反红黑性质，则至多违反一条，且只可能是性质 2 或性质 4：违反性质 2 是因为 $z$ 是根且为红；违反性质 4 是因为 $z$ 和 $z.p$ 都是红。 (b) 用来保证代码引用 $z.p.p$ 时它存在。
初始化：调用时 $z$ 是新加的红结点；若 $z.p$ 是根，它原本就是黑的且未改变；性质 1、3、5 成立；若违反性质 2，红根必是唯一内部结点 $z$，其父结点与孩子都是黑哨兵，不同时违反性质 4；若违反性质 4，只能是 $z$ 与 $z.p$ 都红，且无其他违反。
终止：循环因 $z.p$ 为黑而终止（$z$ 为根时 $z.p = T.nil$ 为黑），所以不违反性质 4；唯一可能违反的是性质 2，第 16 行把根染黑恢复。
保持：共 6 种情况，按 $z.p$ 是祖父的左孩子还是右孩子对称地各分 3 种；只讨论左孩子。由于循环只在 $z.p$ 为红时进入，由 (b) 知 $z.p$ 不是根，所以 $z.p.p$ 存在且为黑。用"叔结点" $y$ 的颜色区分情况 1 和情况 2/3。
- 情况 1：叔结点 $y$ 为红（图 13.5）。$z.p.p$ 是黑的，把 $z.p$ 和 $y$ 都染黑，修复 $z$ 与 $z.p$ 连续红的问题，再把 $z.p.p$ 染红以保持性质 5；然后把 $z.p.p$ 当作新 $z$ 重复循环，$z$ 上移两层。无论 $z$ 是左孩子还是右孩子都做同样操作。新 $z' = z.p.p$ 为红（a 成立）；$z'.p$ 颜色不变，若为根则仍为黑（b 成立）；若 $z'$ 是根，则唯一违反的是性质 2；若不是根且 $z'.p$ 为红，则只在 $z'$ 与 $z'.p$ 间违反性质 4（c 成立）。
- 情况 2：叔结点 $y$ 为黑且 $z$ 是右孩子；情况 3：叔结点 $y$ 为黑且 $z$ 是左孩子（图 13.6）。情况 2 中令 $z = z.p$ 并左旋，立即转为情况 3；因为 $z$ 与 $z.p$ 都红，旋转不影响黑高和性质 5。情况 3 中把 $z.p$ 染黑、$z.p.p$ 染红并对 $z.p.p$ 右旋，保持性质 5；此后不再有连续两个红结点，$z.p$ 为黑，循环结束。不变式：情况 2 让 $z$ 指向红色的 $z.p$，此后 $z$ 和其颜色不变（a）；情况 3 把 $z.p$ 染黑（b）；性质 1、3、5 保持，唯一染红的结点经旋转后成为黑结点的孩子，不引入性质 2 违反，并修复了唯一的性质 4 违反（c）。

图 13.4 示例：插入 4 后 $z=4$ 与父 5 都红，叔 8 红 → 情况 1，重新着色后 $z$ 上移到 7；7 与父 2 都红，叔 14 黑，7 是右孩子 → 情况 2，对 2 左旋；此时 $z=2$ 是左孩子 → 情况 3，重新着色并对 11 右旋，得到合法红黑树（7 为根）。

分析：RB-INSERT 第 1–16 行 $O(\lg n)$。RB-INSERT-FIXUP 中只有情况 1 会让循环继续，此时 $z$ 上移两层，所以循环至多 $O(\lg n)$ 次。总时间 $O(\lg n)$，且至多两次旋转（执行情况 2 或 3 后循环终止）。

习题 13.3 概括：13.3-1 为何新结点染红；13.3-2 依次插入 41,38,31,12,19,8 画出红黑树；13.3-3 设图 13.5/13.6 各子树黑高为 $k$，标注各结点黑高验证性质 5；13.3-4 证明 RB-INSERT-FIXUP 从不把 $T.nil$ 染红；13.3-5 用 RB-INSERT 插入 $n>1$ 个结点后至少有一个红结点；13.3-6 无父指针时如何高效实现 RB-INSERT（用栈记录搜索路径）。

13.4 删除（Deletion）（PDF p.344–351）

删除也是 $O(\lg n)$，但比插入复杂。基于 TREE-DELETE，先定制 TRANSPLANT：

def RB_TRANSPLANT(T, u, v):
    if u.p is T.nil:
        T.root = v
    elif u == u.p.left:
        u.p.left = v
    else:
        u.p.right = v
    v.p = u.p          # 无条件赋值，即使 v 是哨兵 T.nil 也赋值

与 TRANSPLANT 的区别：用 $T.nil$ 代替 NIL；对 $v.p$ 的赋值无条件执行——即使 $v = T.nil$ 也可赋值，后面正要利用这一点。

def RB_DELETE(T, z):
    y = z
    y_original_color = y.color
    if z.left is T.nil:
        x = z.right
        RB_TRANSPLANT(T, z, z.right)
    elif z.right is T.nil:
        x = z.left
        RB_TRANSPLANT(T, z, z.left)
    else:
        y = TREE_MINIMUM(z.right)          # z 的后继
        y_original_color = y.color
        x = y.right
        if y.p == z:
            x.p = y                        # 即使 x 是 T.nil
        else:
            RB_TRANSPLANT(T, y, y.right)
            y.right = z.right
            y.right.p = y
        RB_TRANSPLANT(T, z, y)
        y.left = z.left
        y.left.p = y
        y.color = z.color                  # y 继承 z 的颜色
    if y_original_color == BLACK:
        RB_DELETE_FIXUP(T, x)

与 TREE-DELETE 结构相同，额外的工作：

维护结点 $y$：它是从树中被删除或在树中被移动的结点。$z$ 少于两个孩子时 $y = z$ 被删除；$z$ 有两个孩子时 $y$ 是 $z$ 的后继，移到 $z$ 的位置。
保存 $y$ 的原始颜色 y_original_color（$y$ 的颜色可能改变：两孩子情形下 $y$ 继承 $z$ 的颜色），最后检查：若原色为黑，移除或移动 $y$ 可能破坏红黑性质。
记录移入 $y$ 原位置的结点 $x$：$y$ 的唯一孩子，或 $y$ 无孩子时为 $T.nil$（$y$ 没有左孩子）。
$x.p$ 总被设为 $y$ 原父结点在树中的位置，即使 $x$ 是 $T.nil$。除非 $y$ 的原父结点就是 $z$（即 $z$ 有两孩子且后继 $y$ 是 $z$ 的右孩子），否则该赋值发生在 RB-TRANSPLANT 第 6 行；当 $y.p = z$ 时，由于 $z$ 要被移除，$y$ 将上移占据 $z$ 的位置，所以令 $x.p = y$。
若 $y$ 原为红色，删除/移动后红黑性质仍成立：(1) 黑高不变；(2) 不会产生相邻红结点——$y$ 带着 $z$ 的颜色占据 $z$ 的位置；若 $y$ 不是 $z$ 的右孩子，$y$ 的右孩子 $x$ 替代 $y$，$y$ 红则 $x$ 必黑；(3) $y$ 红就不可能是根，根仍黑。
若 $y$ 原为黑色，可能出现三个问题：(1) $y$ 原是根且 $y$ 的一个红孩子成为新根，违反性质 2；(2) $x$ 与 $x.p$ 都红，违反性质 4；(3) 移动 $y$ 使原先包含 $y$ 的路径少一个黑结点，$y$ 的所有祖先违反性质 5。

"额外的黑"（extra black）：为修正性质 5，认为占据 $y$ 原位置的 $x$ 带有一重"额外的黑"——即把含 $x$ 的路径黑结点计数加 1，性质 5 就成立；删除/移动黑结点 $y$ 时把它的"黑"推给 $x$。但这样 $x$ 既非红也非黑，违反性质 1：$x$ 是双重黑（doubly black）（贡献 2）或红黑（red-and-black）（贡献 1）。$x$ 的 color 属性仍是 RED（红黑）或 BLACK（双重黑）——额外的黑体现在"$x$ 指向该结点"上，而不是在颜色属性中。

def RB_DELETE_FIXUP(T, x):
    while x is not T.root and x.color == BLACK:
        if x == x.p.left:
            w = x.p.right                       # w 是 x 的兄弟
            if w.color == RED:                  # 情况 1：兄弟红
                w.color = BLACK
                x.p.color = RED
                LEFT_ROTATE(T, x.p)
                w = x.p.right                   # 转为情况 2/3/4
            if w.left.color == BLACK and w.right.color == BLACK:
                w.color = RED                   # 情况 2：兄弟黑，两侄子黑
                x = x.p                         # 额外的黑上移
            else:
                if w.right.color == BLACK:      # 情况 3：兄弟黑，左侄红右侄黑
                    w.left.color = BLACK
                    w.color = RED
                    RIGHT_ROTATE(T, w)
                    w = x.p.right               # 转为情况 4
                w.color = x.p.color             # 情况 4：兄弟黑，右侄红
                x.p.color = BLACK
                w.right.color = BLACK
                LEFT_ROTATE(T, x.p)
                x = T.root                      # 终止循环
        else:
            ...  # 与 then 分支对称（left 与 right 互换）
    x.color = BLACK

RB-DELETE-FIXUP 恢复性质 1、2、4（习题 13.4-1、13.4-2 处理性质 2 和 4，正文聚焦性质 1）。while 循环的目标是把额外的黑沿树上移，直到：

$x$ 指向红黑结点，此时在最后一行把 $x$ 染成（单一）黑；
$x$ 指向根，此时直接"去掉"额外的黑；
经过适当旋转和重新着色后退出循环。

循环内 $x$ 总指向非根的双重黑结点。$w$ 指向 $x$ 的兄弟；由于 $x$ 双重黑，$w$ 不可能是 $T.nil$，否则从 $x.p$ 到（单黑）叶 $w$ 的路径黑结点数会少于到 $x$ 的路径。

验证性质 5 的关键思路：每种变换都保持从所示子树的根（含）到各子树 $\alpha, \beta, \dots, \zeta$ 的黑结点数（含 $x$ 的额外黑）不变。例如情况 1（图 13.7(a)）中，根到 $\alpha$ 或 $\beta$ 的黑结点数变换前后都是 3，到 $\gamma, \delta, \epsilon, \zeta$ 都是 2。情况 2（图 13.7(b)）需引入根颜色 $c$：定义 count(RED)=0、count(BLACK)=1，根到 $\alpha$ 的黑结点数前后都是 $2 + \text{count}(c)$；变换后新 $x$ 的颜色属性为 $c$，它实际上是红黑（$c$ = RED）或双重黑（$c$ = BLACK）。其他情况类似（习题 13.4-5）。

四种情况（不互斥）：

情况 1：$x$ 的兄弟 $w$ 是红色。$w$ 的孩子必为黑；交换 $w$ 与 $x.p$ 的颜色，对 $x.p$ 左旋，不破坏任何红黑性质。$x$ 的新兄弟（原 $w$ 的某个孩子）为黑，转为情况 2、3 或 4。
情况 2：$w$ 黑，$w$ 的两个孩子都黑。从 $x$ 和 $w$ 各去掉一重黑：$x$ 只剩一重黑，$w$ 变红；为补偿，在 $x.p$ 上加一重额外的黑——令 $x = x.p$ 重复循环。若从情况 1 进入情况 2，新 $x$ 原本是红色（红黑），$c$ = RED，循环测试时终止，最后把它染黑。
情况 3：$w$ 黑，$w$ 左孩子红、右孩子黑。交换 $w$ 与 $w.left$ 的颜色，对 $w$ 右旋，不违反红黑性质。$x$ 的新兄弟是有红色右孩子的黑结点，转为情况 4。
情况 4：$w$ 黑，$w$ 右孩子红。做一些颜色修改（$w$ 取 $x.p$ 的颜色，$x.p$ 与 $w.right$ 染黑）并对 $x.p$ 左旋，去掉 $x$ 的额外黑使其成为单黑，不违反红黑性质；令 $x = T.root$ 使循环终止。

分析：不含 FIXUP 时 RB-DELETE 为 $O(\lg n)$。FIXUP 中情况 1、3、4 在常数次颜色修改和至多 3 次旋转后终止；只有情况 2 可能让循环重复，此时 $x$ 至多上移 $O(\lg n)$ 次，且不做旋转。所以 RB-DELETE-FIXUP $O(\lg n)$、至多 3 次旋转，RB-DELETE 总时间 $O(\lg n)$。

习题 13.4 概括：13.4-1 FIXUP 后根必黑；13.4-2 若 $x$ 与 $x.p$ 都红，FIXUP 恢复性质 4；13.4-3 对 13.3-2 的树依次删除 8,12,19,31,38,41；13.4-4 FIXUP 中哪些行可能检查/修改 $T.nil$；13.4-5 对图 13.7 各情况写出黑结点计数（用 count(c)、count(c')）并验证不变；13.4-6 情况 1 开始时 $x.p$ 必为黑；13.4-7 插入 $x$ 后立刻删除，所得红黑树不一定与原树相同。

第 13 章思考题（PDF p.352–358）

13-1 持久动态集合（persistent dynamic sets）：需要保留动态集合更新前的各版本，称为持久的。每次修改复制整个集合太慢太费空间。用 BST 实现：每个版本有独立的根；插入键 5 时（图 13.8，原树键 2,3,4,7,8,10），新建键 5 的结点，它成为新建的键 7 结点的左孩子（不能修改原 7 结点），新 7 成为新 8 结点的左孩子（新 8 的右孩子仍是原 10 结点），新 8 成为新根 $r'$（键 4）的右孩子，$r'$ 的左孩子是原 3 结点。只复制部分路径并与原树共享其余结点（路径复制）。假设结点只有 key/left/right、无父指针。(a) 指出插入键 $k$ 或删除结点 $y$ 时需要改变的结点（从根到被修改位置路径上的所有结点）；(b) 写 PERSISTENT-TREE-INSERT；(c) 高度 $h$ 时时间和空间为 $O(h)$；(d) 若结点有父指针，则需 $\Omega(n)$ 时间和空间（每个结点都要复制）；(e) 用红黑树使每次插入/删除最坏 $O(\lg n)$ 时间和空间。
13-2 红黑树的连接操作（join）：给定 $S_1$、$S_2$ 和元素 $x$，满足 $x_1.key \le x.key \le x_2.key$（对所有 $x_1\in S_1, x_2\in S_2$），返回 $S_1\cup\{x\}\cup S_2$。(a) 在树属性 $T.bh$ 中存黑高，RB-INSERT/RB-DELETE 可维护它而不增加结点存储和渐近时间；下降时可 $O(1)$ 得到每个访问结点的黑高；(b) 设 $T_1.bh \ge T_2.bh$，$O(\lg n)$ 找出 $T_1$ 中黑高为 $T_2.bh$ 的黑结点中键最大者 $y$（沿右脊下降）；(c) $O(1)$ 用 $T_y\cup\{x\}\cup T_2$ 替换 $T_y$（$x$ 为新子树根，左 $T_y$ 右 $T_2$）；(d) $x$ 染红以保持性质 1、3、5，再用类似 RB-INSERT-FIXUP 的方法在 $O(\lg n)$ 内恢复性质 2、4；(e) 对称情形 $T_1.bh \le T_2.bh$；(f) RB-JOIN 总时间 $O(\lg n)$。
13-3 AVL 树：AVL 树是**高度平衡（height balanced）**的 BST：每个结点左右子树高度差至多 1；结点存高度 $x.h$。(a) $n$ 结点 AVL 树高度 $O(\lg n)$（提示：高度为 $h$ 的 AVL 树至少有 $F_h$ 个结点，$F_h$ 为第 $h$ 个 Fibonacci 数）；(b) 插入后某结点左右孩子高度可能相差 2，写 BALANCE(x) 用旋转恢复平衡；(c) 递归 AVL-INSERT(x, z)；(d) AVL-INSERT 为 $O(\lg n)$ 时间且只做 $O(1)$ 次旋转。
13-4 树堆（treap）：依次收到元素时也想"随机构造"BST。treap 中每个结点有 key 和独立随机选取的 priority（假设都互异），键满足 BST 性质，优先级满足最小堆序：若 $v$ 是 $u$ 的左孩子则 $v.key < u.key$；右孩子则 $v.key > u.key$；$v$ 是 $u$ 的孩子则 $v.priority > u.priority$（"tree + heap"）。等价理解：treap 等于把结点按优先级从小到大的顺序插入普通 BST 得到的树。图 13.9 例：根 G:4，其下 B:7、H:5 等。(a) 给定键与优先级都互异的结点集合，treap 唯一；(b) 期望高度 $\Theta(\lg n)$，搜索期望 $\Theta(\lg n)$；(c) TREAP-INSERT：先赋随机优先级，做普通 BST 插入，再通过旋转把新结点向上移动直到恢复最小堆序（图 13.10：插入 C:25、D:9、F:2 的过程，F:2 优先级最小最终成为根）；(d) 期望时间 $\Theta(\lg n)$；旋转（写操作）比搜索（读操作）代价高，因此希望旋转次数少——下面证明期望旋转次数为常数。定义**左脊（left spine）**为从根只走左边到最小键结点的简单路径，**右脊（right spine）**对称，脊长为其结点数（图 13.11）。(e) 插入 $x$ 后，设 $C$ 为 $x$ 左子树右脊长度、$D$ 为 $x$ 右子树左脊长度，则旋转次数 $= C + D$；不妨设键为 $1..n$，对 $y\ne x$、$k = x.key$、$i = y.key$ 定义 $X_{ik} = I\{y$ 在 $x$ 左子树的右脊上$\}$；(f) $X_{ik} = 1$ 当且仅当 $y.priority > x.priority$、$y.key < x.key$，且对所有键介于二者之间的 $z$ 有 $y.priority < z.priority$；(g) $\Pr\{X_{ik}=1\} = \frac{(k-i-1)!}{(k-i+1)!} = \frac{1}{(k-i+1)(k-i)}$；(h) $E[C] = \sum_{j=1}^{k-1}\frac{1}{j(j+1)} = 1 - \frac1k$；(i) 由对称性 $E[D] = 1 - \frac{1}{n-k+1}$；(j) 插入期望旋转次数小于 2。

章末注记

平衡搜索树思想源自 Adel'son-Vel'skiĭ 与 Landis 1962 年的 AVL 树。Hopcroft 1970 年提出 2-3 树（通过操纵结点度数保持平衡），第 18 章的 B 树（Bayer 与 McCreight）是其推广。红黑树由 Bayer 以"对称二叉 B 树"之名发明，Guibas 与 Sedgewick 详细研究并引入红/黑着色约定。Andersson 给出更易编码的变体（Weiss 称为 AA 树：左孩子不能为红）。Treap 由 Seidel 与 Aragon 提出，是 LEDA 库字典的默认实现。其他平衡树：权平衡树、$k$-邻居树、替罪羊树（scapegoat tree）；最有趣的或许是 Sleator 与 Tarjan 的伸展树（splay tree），"自调整"，没有显式平衡条件，每次访问时做伸展操作（旋转），每个操作摊还代价 $O(\lg n)$。**跳表（skip list）**是平衡二叉树的替代：在链表上增加若干额外指针，每个字典操作期望 $O(\lg n)$。

第 13 章本章要点

五条红黑性质保证 $n$ 个内部结点的树高 $\le 2\lg(n+1)$（引理 13.1：子树至少 $2^{bh(x)}-1$ 个内部结点 + 至少一半结点为黑）。
旋转是 $O(1)$、保持 BST 性质的局部重构原语。
插入：新结点染红，FIXUP 按叔结点颜色分 3 种（再加对称 3 种）情况；$O(\lg n)$ 时间，至多 2 次旋转。
删除：跟踪被删/移动结点 $y$ 的原色和接替其位置的 $x$；$y$ 原为黑时用"额外的黑"概念，FIXUP 按兄弟 $w$ 及其孩子颜色分 4 种情况；$O(\lg n)$ 时间，至多 3 次旋转。
替代方案：AVL 树、treap、伸展树、跳表、B 树。

第 13 章与量化交易的关联

订单簿实现：C++ std::map/std::set、Java TreeMap 多数是红黑树实现，限价订单簿的价格档位（bid 侧降序、ask 侧升序）常直接用它们：插入/删除价位、取最优价、遍历前 $k$ 档都有最坏 $O(\lg n)$ 保证。最坏情况保证对低延迟系统重要；不过实盘高频系统也常因缓存局部性改用基于价格刻度（tick）的数组或 B 树变体。
有序时间序列索引：事件驱动回测中的事件队列/定时器、按时间戳有序存储的行情缓存，可以用平衡树支持任意时间点插入和范围查询。
持久化结构（思考题 13-1）：路径复制实现的持久平衡树，可以低成本保存组合/订单簿在每个时点的快照，用于回测中的"时点一致（point-in-time）"状态回放与审计，也是函数式语言中不可变映射的实现基础。
跳表（章末注记）是 Redis 有序集合的底层实现，常用于实时排行榜/截面排名。
与因子构造、风险模型、定价的数学内容无直接关联。

第 13 章推荐习题

13.1-5、13.1-6：最长/最短路径比与黑高对应的结点数界，理解平衡保证的来源。
13.2-4：任意两棵 BST 之间 $O(n)$ 次旋转可互相转换。
13.3-2 与 13.4-3：手工插入再删除一组键，熟悉各修复情况（实现前的必做练习）。
13.3-6：无父指针的插入（用栈），贴近工程实现。
思考题 13-1：持久化 BST，快照与回放思想。
思考题 13-4：treap 的期望旋转次数 $<2$，指示变量分析的范例。

第 14 章数据结构的扩张（Augmenting Data Structures）（PDF p.360–376）

工程中有时"教科书"数据结构（双向链表、散列表、二叉搜索树）就够用，但很多时候需要一点创造性。很少需要发明全新的结构，更常见的是**扩张（augment）**教科书结构：在其中存放额外信息，并为之编写新操作。难点在于额外信息必须能被原有操作正确维护。本章扩张红黑树得到两种结构：14.1 支持动态集合上一般的顺序统计操作（快速找第 $i$ 小元素或某元素的秩）；14.2 抽象出扩张的一般过程，并给出简化红黑树扩张的定理；14.3 用该定理设计维护区间（如时间区间）的动态集合，可快速找出与查询区间重叠的区间。

14.1 动态顺序统计（Dynamic order statistics）（PDF p.360–366）

第 9 章：$n$ 元素集合的第 $i$ 个顺序统计量（order statistic）是第 $i$ 小的元素，对无序集合可在 $O(n)$ 内求得。本节修改红黑树，使动态集合的任意顺序统计量以及元素的秩（rank）（在线性序中的位置）都能在 $O(\lg n)$ 内求出。

顺序统计树（order-statistic tree）：在红黑树每个结点 $x$ 上增加属性 $x.size$——以 $x$ 为根的子树中（内部）结点数（含 $x$ 本身）。定义哨兵 $T.nil.size = 0$，则

\[x.size = x.left.size + x.right.size + 1.\]

关键字不要求互异（图 14.1 中有两个 14、两个 21）；此时把元素的秩定义为它在中序遍历中被输出的位置，消除歧义（图 14.1 中黑结点里的 14 秩为 5，红结点里的 14 秩为 6）。

查找给定秩的元素 OS-SELECT(x, i)：返回以 $x$ 为根的子树中第 $i$ 小关键字所在结点；对整棵树调用 OS-SELECT(T.root, i)。

def OS_SELECT(x, i):
    r = x.left.size + 1            # x 在其子树中的秩
    if i == r:
        return x
    elif i < r:
        return OS_SELECT(x.left, i)
    else:
        return OS_SELECT(x.right, i - r)   # 右子树中第 i-r 小

$x.left.size$ 是子树中序遍历中排在 $x$ 之前的结点数，所以 $r = x.left.size + 1$ 是 $x$ 在子树中的秩。$i>r$ 时，子树中有 $r$ 个元素排在右子树之前，所以要找右子树中第 $i-r$ 小的元素。例：在图 14.1 中找第 17 小：根 26 左子树大小 12，秩 13，转到右子树找第 $17-13=4$ 小；结点 41 左子树大小 5，秩 6，转到左子树找第 4 小；结点 30 秩 2，转到右子树（根 38）找第 $4-2=2$ 小；38 左子树大小 1，所以 38 即第 2 小，返回键 38 的结点。每次递归下降一层，时间 $O(\lg n)$。

确定元素的秩 OS-RANK(T, x)：

def OS_RANK(T, x):
    r = x.left.size + 1
    y = x
    while y is not T.root:
        if y == y.p.right:                  # y 是右孩子：父结点及其左子树都在 x 之前
            r = r + y.p.left.size + 1
        y = y.p
    return r

循环不变式：每次 while 迭代开始时，$r$ 是 $x.key$ 在以 $y$ 为根的子树中的秩。

初始化：$r$ 是 $x$ 在自身子树中的秩，$y = x$。
保持：迭代末 $y \leftarrow y.p$。需要加上 $y$ 的兄弟子树中排在 $x$ 之前的结点数，以及若 $y.p$ 也在 $x$ 之前则加 1。若 $y$ 是左孩子，$y.p$ 及其右子树都不在 $x$ 之前，$r$ 不变；若 $y$ 是右孩子，$y.p$ 的左子树所有结点和 $y.p$ 本身都在 $x$ 之前，加 $y.p.left.size + 1$。
终止：$y = T.root$ 时，$r$ 就是 $x$ 在整棵树中的秩。

例：求图 14.1 中键 38 的秩，循环顶部 $(y.key, r)$ 依次为 (38, 2)、(30, 4)、(41, 4)、(26, 17)，返回 17。每次迭代 $O(1)$ 且 $y$ 上升一层，所以 $O(\lg n)$。

维护子树规模：

插入第一阶段（自根向下插入新结点）：对路径上每个结点 $x$ 执行 $x.size$ 加 1，新结点 size 为 1；路径长 $O(\lg n)$，额外代价 $O(\lg n)$。
插入第二阶段（向上重新着色和旋转）：结构变化只来自至多 2 次旋转；旋转是局部操作，只有旋转所绕的链所关联的两个结点 size 失效。在 LEFT-ROTATE(T, x) 末尾加两行：
```
y.size = x.size
x.size = x.left.size + x.right.size + 1
```
RIGHT-ROTATE 对称（图 14.2：左旋前 $x$ 的 size 为 19、$y$ 为 12，左旋后 $y$ 继承 19，$x$ 重算为 $6+4+1 = 11$）。所以插入总计 $O(\lg n)$。
删除第一阶段：从被移除或上移的结点 $y$ 的原位置向上到根，路径上每个结点 size 减 1，$O(\lg n)$；第二阶段至多 3 次旋转，同插入方式处理。
结论：含 size 维护的插入和删除都是 $O(\lg n)$。

习题 14.1 概括：14.1-1/14.1-2 在图 14.1 上模拟 OS-SELECT(T.root,10) 和 OS-RANK（键 35）；14.1-3 非递归 OS-SELECT；14.1-4 递归 OS-KEY-RANK(T, k)（给定关键字求秩，键互异）；14.1-5 $O(\lg n)$ 求 $x$ 的第 $i$ 个后继（先求秩 $r$，再 OS-SELECT($r+i$)）；14.1-6 若每个结点存其在自身子树中的秩，如何在插入删除（含旋转）时维护；14.1-7 用顺序统计树在 $O(n\lg n)$ 内统计数组的**逆序对（inversions）**数；14.1-8（星号）圆上 $n$ 条弦（无公共端点）的相交对数，$O(n\lg n)$（例：$n$ 条过圆心的直径，答案 $\binom n2$）。

14.2 如何扩张数据结构（How to augment a data structure）（PDF p.366–369）

扩张数据结构的四个步骤：

选择一个基础数据结构；
确定要在基础结构中维护的附加信息；
检验基础结构上的基本修改操作能否维护附加信息；
设计新操作。

与任何规范化设计方法一样，不应机械地按顺序执行；设计工作往往带有试错，各步骤并行推进（例如如果附加信息无法高效维护，确定附加信息和开发新操作就没意义）。但这四步为扩张提供了焦点，也是组织扩张结构文档的好方式。

以顺序统计树为例：

步骤 1：选红黑树，因为它高效支持全序上的其他操作（MIN、MAX、SUCCESSOR、PREDECESSOR）。
步骤 2：加 size 属性。附加信息通常让操作更高效——只用关键字也能实现 OS-SELECT/OS-RANK，但不能 $O(\lg n)$。有时附加信息是指针而非数据（习题 14.2-1）。
步骤 3：保证插入删除能在 $O(\lg n)$ 内维护 size。理想情况下只需更新少数元素。反例：若每个结点直接存它在整棵树中的秩，OS-SELECT 和 OS-RANK 很快，但插入一个新的最小元素会让每个结点的信息都改变；存子树规模则插入只改变 $O(\lg n)$ 个结点。
步骤 4：开发 OS-SELECT 和 OS-RANK。有时不是开发新操作，而是用附加信息加速已有操作（习题 14.2-1）。

定理 14.1（红黑树的扩张）：设 $f$ 是扩张 $n$ 结点红黑树 $T$ 的属性，且每个结点 $x$ 的 $f$ 值只依赖于结点 $x$、$x.left$、$x.right$ 中的信息（可包括 $x.left.f$ 和 $x.right.f$）。则可以在插入和删除过程中维护所有结点的 $f$ 值，而不影响这两个操作 $O(\lg n)$ 的渐近性能。

证明思路：结点 $x$ 的 $f$ 改变只会传播到 $x$ 的祖先：改 $x.f$ 可能需要更新 $x.p.f$，再可能更新 $x.p.p.f$……更新到 $T.root.f$ 后就结束。树高 $O(\lg n)$，所以改变一个结点的 $f$ 代价 $O(\lg n)$。

插入第一阶段：新结点 $x$ 的两个孩子都是哨兵，$x.f$ 可 $O(1)$ 算出，再向上传播，$O(\lg n)$。第二阶段只有旋转改变结构，每次旋转只改变两个结点，每次传播 $O(\lg n)$；至多 2 次旋转，总计 $O(\lg n)$。
删除第一阶段：被删结点移除；若它有两个孩子，后继移到它的位置。这些都是局部修改，传播至多 $O(\lg n)$。第二阶段至多 3 次旋转，各 $O(\lg n)$。总计 $O(\lg n)$。
许多情况下（如 size），旋转后的更新只需 $O(1)$ 而非 $O(\lg n)$（习题 14.2-3）。

习题 14.2 概括：14.2-1 加指针使顺序统计树的 MIN/MAX/SUCCESSOR/PREDECESSOR 最坏 $O(1)$（维护有序双向链表线索）；14.2-2 结点黑高可以作为属性维护（只依赖孩子），结点深度则不行（旋转会改变整棵子树的深度）；14.2-3（星号）若 $x.f = x_1.a \otimes x_2.a \otimes \cdots \otimes x_m.a$（$\otimes$ 为结合二元运算，$x_1..x_m$ 为子树中序序列），旋转后 $O(1)$ 更新 $f$，并据此说明 size；14.2-4（星号）RB-ENUMERATE(x, a, b) 在 $\Theta(m + \lg n)$ 内输出所有 $a \le k \le b$ 的键（$m$ 为输出个数），无需新属性。

14.3 区间树（Interval trees）（PDF p.369–376）

闭区间（closed interval） $[t_1, t_2]$（$t_1 \le t_2$）表示集合 $\{t\in\mathbb R : t_1 \le t \le t_2\}$；开区间和半开区间分别省略两端点或一端点。本节假设闭区间，推广到开/半开区间在概念上是直接的。区间适合表示占用一段连续时间的事件，例如查询时间区间数据库，找出给定区间内发生了哪些事件。

把区间表示为对象 $i$，$i.low = t_1$（低端点），$i.high = t_2$（高端点）。区间 $i$、$i'$ **重叠（overlap）**当且仅当 $i\cap i' \ne \emptyset$，即 $i.low \le i'.high$ 且 $i'.low \le i.high$。区间三分律（interval trichotomy）（图 14.3）：任意两个区间恰好满足以下之一：

(a) $i$ 与 $i'$ 重叠（有 4 种几何情形）；
(b) $i$ 在 $i'$ 左边：$i.high < i'.low$；
(c) $i$ 在 $i'$ 右边：$i'.high < i.low$。

**区间树（interval tree）**是维护动态元素集合的红黑树，每个元素 $x$ 含区间 $x.int$。支持：

INTERVAL-INSERT(T, x)：加入元素 $x$（其 int 属性已含区间）；
INTERVAL-DELETE(T, x)：删除 $x$；
INTERVAL-SEARCH(T, i)：返回指向某元素 $x$ 的指针，使 $x.int$ 与 $i$ 重叠；不存在则返回 $T.nil$。

按四步法设计：

步骤 1 基础结构：红黑树，结点 $x$ 含区间 $x.int$，关键字为低端点 $x.int.low$。中序遍历按低端点排序列出区间。
步骤 2 附加信息：每个结点存 $x.max$——以 $x$ 为根的子树中所有区间端点的最大值。
步骤 3 维护信息： $x.max = \max(x.int.high,\ x.left.max,\ x.right.max).$ 由定理 14.1，插入删除仍为 $O(\lg n)$；实际上旋转后可在 $O(1)$ 内更新 max（习题 14.2-3、14.3-1）。
步骤 4 新操作：

def INTERVAL_SEARCH(T, i):
    x = T.root
    while x is not T.nil and not overlap(i, x.int):
        if x.left is not T.nil and x.left.max >= i.low:
            x = x.left          # 左子树可能有重叠区间
        else:
            x = x.right
    return x
# 时间 O(lg n)：每次迭代 O(1)，只沿一条从根向下的路径

图 14.4 的区间树存 10 个区间：[0,3]、[5,8]、[6,10]、[8,9]、[15,23]、[16,21]、[17,19]、[19,20]、[25,30]、[26,26]；根为 [16,21]（max 30），左孩子 [8,9]（max 23），右孩子 [25,30]（max 30），等等。

成功搜索例：$i = [22,25]$。根 [16,21] 不重叠；$x.left.max = 23 \ge 22$，往左到 [8,9]，不重叠；$x.left.max = 10 < 22$，往右到 [15,23]，与 $i$ 重叠，返回。
不成功搜索例：$i = [11,14]$。根不重叠，左孩子 max 23 ≥ 11，往左到 [8,9]；不重叠，其左孩子 max 10 < 11，往右（左子树中确实没有与 $i$ 重叠的区间）；[15,23] 不重叠，左孩子为 $T.nil$，往右，循环结束，返回 $T.nil$。

定理 14.2：INTERVAL-SEARCH(T, i) 的任何执行，要么返回一个区间与 $i$ 重叠的结点，要么返回 $T.nil$ 且 $T$ 中没有区间与 $i$ 重叠。证明：循环因 $x = T.nil$ 或 $i$ 与 $x.int$ 重叠而终止，后者显然正确，只需讨论前者。循环不变式：若 $T$ 中有与 $i$ 重叠的区间，则以 $x$ 为根的子树中一定有这样的区间。

初始化：$x$ 为根，成立。
保持——执行第 5 行（往右）：由分支条件，$x.left = T.nil$（左子树显然无重叠区间），或 $x.left.max < i.low$。后者情况下对左子树任一区间 $i'$ 有 $i'.high \le x.left.max < i.low$，由三分律不重叠（图 14.5(a)）。所以往右保持不变式。
保持——执行第 4 行（往左）：证明逆否命题：若 $x.left$ 子树中没有与 $i$ 重叠的区间，则整棵树中都没有。由分支条件 $x.left.max \ge i.low$，且由 max 的定义，左子树中存在区间 $i'$ 使 $i'.high = x.left.max \ge i.low$（图 14.5(b)）。$i$ 与 $i'$ 不重叠且不是 $i'.high < i.low$，由三分律只能是 $i.high < i'.low$。区间树以低端点为键，由 BST 性质对右子树中任一区间 $i''$ 有 $i.high < i'.low \le i''.low$，所以 $i$ 与 $i''$ 也不重叠。因此无论左子树中是否有重叠区间，往左都保持不变式。
终止：若在 $x = T.nil$ 时终止，以 $x$ 为根的子树中没有重叠区间，由不变式的逆否命题，整棵树中也没有，返回 $T.nil$ 正确。

直观：在每个结点，若 $x.int$ 不与 $i$ 重叠，搜索总是朝"安全"方向前进——只要树中有重叠区间就一定能找到，因此只需检查一条从根出发的路径。

习题 14.3 概括：14.3-1 写在区间树上 $O(1)$ 更新 max 的 LEFT-ROTATE；14.3-2 改写 INTERVAL-SEARCH 使其适用于开区间；14.3-3 找与 $i$ 重叠且低端点最小的区间；14.3-4 在 $O(\min(n, k\lg n))$ 时间内列出所有与 $i$ 重叠的 $k$ 个区间（简单方法：多次查询并在查询间删除已找到的区间；稍复杂的方法不修改树）；14.3-5 INTERVAL-SEARCH-EXACTLY（找低高端点都相同的区间），所有操作 $O(\lg n)$；14.3-6 维护数集 $Q$ 支持 MIN-GAP（两最近数之差，例 $Q=\{1,5,9,15,18,22\}$ 时为 $18-15=3$），附加信息为子树的 min、max、min-gap；14.3-7（星号）VLSI 数据库中 $n$ 个轴平行矩形是否有两个重叠，$O(n\lg n)$，用"扫描线（sweep line）"+ 区间树，完全包含也要报告。

第 14 章思考题（PDF p.374–376）

14-1 最大重叠点（point of maximum overlap）：(a) 总存在一个最大重叠点是某线段的端点；(b) 设计结构支持 INTERVAL-INSERT、INTERVAL-DELETE、FIND-POM（返回最大重叠点）——提示：用红黑树存所有端点，左端点赋值 +1、右端点赋值 −1，每个结点扩张存子树值之和及子树内的最大前缀和（及其位置），即可维护最大重叠点。
14-2 Josephus 排列：$n$ 人围成一圈，给定正整数 $m \le n$，从指定的第一人开始每数到第 $m$ 人就移出，继续在剩下的圈中计数，直到全部移出，移出顺序定义 $(n,m)$-Josephus 排列。例：$(7,3)$-Josephus 排列为 ⟨3,6,2,7,5,1,4⟩。(a) $m$ 为常数时 $O(n)$ 输出（循环链表）；(b) $m$ 非常数时 $O(n\lg n)$（顺序统计树：每次删除秩为 $(r + m - 1) \bmod$ 剩余人数的元素）。

章末注记

Preparata 与 Shamos 介绍了文献中的多种区间树（引用 Edelsbrunner 1980、McCreight 1981 的工作），其中一种对 $n$ 个区间的静态数据库，能在 $O(k + \lg n)$ 时间内枚举与查询区间重叠的全部 $k$ 个区间。

第 14 章本章要点

扩张数据结构四步法：选基础结构、定附加信息、验证可维护、开发新操作。
定理 14.1：只依赖结点自身与两个孩子的属性，可在红黑树插入删除中维护而不改变 $O(\lg n)$。
顺序统计树：size 属性，OS-SELECT 与 OS-RANK 均 $O(\lg n)$；存"子树规模"而非"全局秩"是可维护性的关键。
区间树：以低端点为键、扩张子树最大端点 max，INTERVAL-SEARCH 只沿一条路径 $O(\lg n)$，正确性靠区间三分律。

第 14 章与量化交易的关联

滚动分位数与截面排名：顺序统计树可在 $O(\lg n)$ 内插入/删除样本并查询第 $k$ 小或某值的秩——这是滚动中位数、滚动分位数（如 VaR 的历史模拟分位数、滚动百分位因子）以及截面排名因子（rank/百分位标准化）增量计算的标准结构；对窗口长度 $w$，每步更新 $O(\lg w)$，优于每步重新排序的 $O(w\lg w)$。Python 中的 sortedcontainers.SortedList、C++ __gnu_pbds::tree（order statistics tree）就是这一思想的实现。
逆序对计数（习题 14.1-7）：$O(n\lg n)$ 计算 Kendall $\tau$ 秩相关的核心步骤，可用于因子 IC 的秩相关、排名稳定性度量。
区间树：处理时间区间数据，例如查询某时刻有效的订单（挂单的生效—撤销区间）、交易时段/停牌区间、事件窗口重叠检测；思考题 14-1 的最大重叠点对应"同时在途订单数/持仓数峰值"或某价格区间内委托量的峰值。
扩张方法论：订单簿价格档位树上扩张"子树累计挂单量"，即可 $O(\lg n)$ 回答"吃掉 $Q$ 股需要穿透到哪个价位"（类似 OS-SELECT 按累计量下降），对冲击成本估计和执行算法有直接用处。

第 14 章推荐习题

14.1-5、14.1-7：第 $i$ 个后继与逆序对计数，直接对应秩相关计算。
14.2-3：结合运算的子树汇总在旋转后 $O(1)$ 更新——一般化的"线段树式"扩张。
14.3-4、14.3-6：枚举所有重叠区间与 MIN-GAP，练习设计附加信息。
思考题 14-1：最大重叠点，前缀和扩张的典型。
思考题 14-2：Josephus 排列，顺序统计树的应用。

Part IV 高级设计和分析技术（Advanced Design and Analysis Techniques）（PDF p.377–379）

本部分介绍三种设计与分析高效算法的重要技术：动态规划（dynamic programming）（第 15 章）、贪心算法（greedy algorithms）（第 16 章）、摊还分析（amortized analysis）（第 17 章）。之前已介绍分治、随机化、解递归式等技术；本部分技术更精巧，并会在全书后续反复出现。

动态规划通常用于最优化问题（optimization problems）：做一系列选择以得到最优解，每次选择后常出现形式相同的子问题。当一个子问题可能由多组不同的部分选择产生时动态规划有效；关键技术是存储每个子问题的解以备再次出现。第 15 章说明这个简单想法有时能把指数时间算法变成多项式时间算法。
贪心算法也用于最优化问题，思想是每次做局部最优选择。简单例子是找零钱：要用最少的美国硬币凑出给定金额，反复选取不超过剩余金额的最大面值硬币。对许多问题，贪心法比动态规划快得多地得到最优解，但并不总能容易判断贪心是否有效；第 16 章介绍**拟阵（matroid）**理论，为证明贪心算法最优提供数学基础。
摊还分析用于分析执行一系列相似操作的算法：不是分别界定每个操作的实际代价，而是界定整个序列的实际总代价。好处是虽然有些操作代价高，但许多操作代价低，远低于最坏情况。摊还分析不仅是分析工具，也是一种算法设计思维方式，因为算法设计与运行时间分析往往紧密交织。第 17 章介绍三种摊还分析方法。

第 15 章动态规划（Dynamic Programming）（PDF p.380–434）

动态规划与分治法一样，通过组合子问题的解来求解原问题（"programming"指表格法，不是写代码）。分治法把问题划分为互不相交的子问题；而动态规划适用于子问题重叠的情形——子问题共享子子问题。此时分治法会反复求解公共子子问题，做多余的工作；动态规划对每个子子问题只求解一次，把答案存进表中，避免重复计算。

动态规划通常用于最优化问题：可能有多个可行解，每个解有一个值，要找值最优（最小或最大）的解。称这样的解为问题的一个最优解（an optimal solution），而不是唯一最优解，因为可能有多个解达到最优值。

设计动态规划算法的四个步骤：

刻画最优解的结构特征；
递归地定义最优解的值；
计算最优解的值，通常采用自底向上的方法；
利用计算出的信息构造一个最优解。

步骤 1–3 是基础；若只需要最优值而不需要解本身，可省略步骤 4。做步骤 4 时，有时在步骤 3 中维护一些额外信息以便构造最优解。本章各节：15.1 钢条切割，15.2 矩阵链乘法，15.3 动态规划的两个关键特征，15.4 最长公共子序列，15.5 最优二叉搜索树。

15.1 钢条切割（Rod cutting）（PDF p.380–391）

问题：Serling 公司购买长钢条，切成短钢条出售，切割本身没有成本。已知长度为 $i$ 英寸的钢条售价 $p_i$ 美元（长度都是整数英寸）。给定长度 $n$ 的钢条和价格表 $p_i$（$i = 1..n$），求切割方案使销售收益 $r_n$ 最大。若 $p_n$ 足够大，最优解可能是完全不切。

样例价格表（图 15.1）：

长度 $i$	1	2	3	4	5	6	7	8	9	10
价格 $p_i$	1	5	8	9	10	17	17	20	24	30

$n=4$ 时共 8 种切法（图 15.2），切成两段长 2 收益 $5+5=10$ 最优。长度 $n$ 的钢条有 $2^{n-1}$ 种切法（在距左端 $i = 1..n-1$ 英寸处各自独立地选择切或不切）。脚注：若要求按长度非降顺序切割，切法数是划分函数（partition function），约为 $e^{\pi\sqrt{2n/3}}/(4n\sqrt3)$，小于 $2^{n-1}$ 但仍远大于任何多项式。用加法记号表示切割方案，如 $7 = 2+2+3$。若最优解切成 $k$ 段 $n = i_1 + \dots + i_k$，则 $r_n = p_{i_1} + \dots + p_{i_k}$。

样例的最优收益：$r_1=1$（不切），$r_2=5$（不切），$r_3=8$（不切），$r_4=10$（2+2），$r_5=13$（2+3），$r_6=17$（不切），$r_7=18$（1+6 或 2+2+3），$r_8=22$（2+6），$r_9=25$（3+6），$r_{10}=30$（不切）。

递归结构：

r_n = \max(p_n,\ r_1 + r_{n-1},\ r_2 + r_{n-2},\ \dots,\ r_{n-1} + r_1). \tag{15.1}

$p_n$ 对应不切；其余 $n-1$ 项对应先切成长 $i$ 和 $n-i$ 两段，再对两段分别最优切割。由于事先不知道哪个 $i$ 最优，要考察所有 $i$。原问题的最优解由两个相关子问题的最优解组成，且子问题可以独立求解——称钢条切割问题具有最优子结构（optimal substructure）。

更简单的递归结构：把切割方案看作"从左端切下长度为 $i$ 的第一段，再对剩余长度 $n-i$ 的部分继续切割"（第一段不再切）。不切对应第一段长度 $i = n$、收益 $p_n$、剩余长度 0 收益 $r_0 = 0$：

r_n = \max_{1\le i\le n}(p_i + r_{n-i}). \tag{15.2}

这样最优解只包含一个相关子问题（剩余部分）的解。

朴素自顶向下递归：

def CUT_ROD(p, n):
    if n == 0:
        return 0
    q = -inf
    for i in range(1, n + 1):
        q = max(q, p[i] + CUT_ROD(p, n - i))
    return q

由式 15.2 对 $n$ 归纳可知正确。但 $n$ 稍大就极慢：$n=40$ 时至少几分钟，很可能超过一小时；$n$ 每增加 1，时间约翻倍。原因是它反复用相同参数递归调用自己，重复求解相同子问题（图 15.3：$n=4$ 的递归树，CUT-ROD(p,n) 对每个 $j = 0..n-1$ 调用 CUT-ROD(p,j)）。设 $T(n)$ 为第二个参数为 $n$ 时 CUT-ROD 的调用总次数（递归树中以 $n$ 为根的子树结点数，含根）：

T(0) = 1,\quad T(n) = 1 + \sum_{j=0}^{n-1}T(j), \tag{15.3}

解得 $T(n) = 2^n$（式 15.4，习题 15.1-1），指数时间。事后看不奇怪：它显式考察了所有 $2^{n-1}$ 种切法，递归树有 $2^{n-1}$ 个叶，根到叶路径上的标号给出从右端量起的切割点。

用动态规划求解：既然朴素递归因重复求解子问题而低效，就让每个子问题只求解一次并保存其解，再次需要时直接查表。动态规划是**时空权衡（time-memory trade-off）**的例子：用额外内存节省计算时间，可能把指数时间变为多项式时间。当不同子问题的数目是输入规模的多项式、且每个子问题能在多项式时间内求解时，动态规划为多项式时间。两种等价实现方法：

带备忘的自顶向下法（top-down with memoization）：按自然的递归形式编写，但保存每个子问题的结果（通常在数组或散列表中）。过程先检查是否已解过该子问题，若是直接返回保存值，否则按常规计算。称该递归过程被**备忘（memoized）**了（脚注：memoization 源自 memo，不是 memorization 的拼写错误）。
自底向上法（bottom-up method）：依赖子问题"规模"的自然概念，使任一子问题只依赖"更小"的子问题。把子问题按规模排序，从小到大依次求解；求解某子问题时，它依赖的所有更小子问题都已解出并保存。

两种方法渐近时间相同（除非自顶向下法实际上不需要递归考察所有子问题）；自底向上法没有过程调用开销，常数因子通常更好。

def MEMOIZED_CUT_ROD(p, n):
    r = [-inf] * (n + 1)        # -inf 表示"未知"（已知收益总是非负）
    return MEMOIZED_CUT_ROD_AUX(p, n, r)

def MEMOIZED_CUT_ROD_AUX(p, n, r):
    if r[n] >= 0:
        return r[n]             # 已算过，直接返回
    if n == 0:
        q = 0
    else:
        q = -inf
        for i in range(1, n + 1):
            q = max(q, p[i] + MEMOIZED_CUT_ROD_AUX(p, n - i, r))
    r[n] = q
    return q

def BOTTOM_UP_CUT_ROD(p, n):
    r = [0] * (n + 1)           # r[0] = 0
    for j in range(1, n + 1):   # 按规模递增求解子问题
        q = -inf
        for i in range(1, j + 1):
            q = max(q, p[i] + r[j - i])   # 直接查表，不递归
        r[j] = q
    return r[n]

复杂度：BOTTOM-UP-CUT-ROD 双重循环，内循环迭代次数构成等差数列，时间 $\Theta(n^2)$，空间 $\Theta(n)$。MEMOIZED-CUT-ROD 也是 $\Theta(n^2)$：对已解子问题的递归调用立即返回，每个子问题（规模 $0..n$）只解一次，解规模 $n$ 的子问题 for 循环迭代 $n$ 次，总迭代数构成等差数列（这其实是 17.1 节的聚合分析）。

子问题图（subproblem graph）

思考动态规划问题时应弄清涉及哪些子问题及其依赖关系。子问题图是有向图，每个不同子问题一个顶点；若求子问题 $x$ 的最优解时需要直接考虑子问题 $y$ 的最优解，则有边 $(x, y)$（例如自顶向下递归过程求解 $x$ 时直接递归调用求解 $y$）。它可看作自顶向下递归树的"约简/压缩"版本：把同一子问题的所有结点合并为一个顶点，边都从父指向子（图 15.4：$n=4$ 的钢条切割子问题图，顶点 0–4，每个顶点 $x$ 指向所有更小的顶点）。

自底向上法按这样的顺序考虑顶点：求解 $x$ 之前先求解其所有邻接子问题 $y$，即子问题图的逆拓扑序（转置图的拓扑序，见 22.4 节）；任何子问题在其依赖的子问题都解完之前不被考虑。
带备忘的自顶向下法可看作对子问题图的深度优先搜索（22.3 节）。
子问题图 $G=(V,E)$ 的规模可帮助确定运行时间：每个子问题只解一次，求解某子问题的时间通常与对应顶点的出度成正比，子问题数等于顶点数，因此运行时间通常与顶点数和边数之和呈线性关系。

重构解

上述算法只返回最优值，不返回实际切割方案。扩展方法：对每个子问题不仅记录最优值，还记录导致最优值的选择。

def EXTENDED_BOTTOM_UP_CUT_ROD(p, n):
    r = [0] * (n + 1)
    s = [0] * (n + 1)            # s[j]：长度 j 的最优方案中第一段的长度
    for j in range(1, n + 1):
        q = -inf
        for i in range(1, j + 1):
            if q < p[i] + r[j - i]:
                q = p[i] + r[j - i]
                s[j] = i
        r[j] = q
    return r, s

def PRINT_CUT_ROD_SOLUTION(p, n):
    r, s = EXTENDED_BOTTOM_UP_CUT_ROD(p, n)
    while n > 0:
        print(s[n])
        n = n - s[n]

样例 $n=10$ 的结果：

$i$	0	1	2	3	4	5	6	7	8	9	10
$r[i]$	0	1	5	8	10	13	17	18	22	25	30
$s[i]$	0	1	2	3	2	2	6	1	2	3	10

PRINT-CUT-ROD-SOLUTION(p,10) 只输出 10；$n=7$ 时输出 1 和 6（对应 $r_7$ 的第一个最优分解）。

习题 15.1 概括：15.1-1 由式 15.3 与 $T(0)=1$ 推出 $T(n)=2^n$；15.1-2 举反例说明按"密度" $p_i/i$ 最大的贪心策略不总是最优（如 $p_1=1,p_2=5,p_3=8$，$n=4$：贪心先切密度最大的 3 得 $8+1=9 < 10$）；15.1-3 每次切割有固定成本 $c$ 时的动态规划（$r_n = \max(p_n, \max_{i<n}(p_i + r_{n-i} - c))$）；15.1-4 让 MEMOIZED-CUT-ROD 也返回方案；15.1-5 $O(n)$ 动态规划求第 $n$ 个 Fibonacci 数，画子问题图（$n+1$ 个顶点、约 $2n-2$ 条边）。

15.2 矩阵链乘法（Matrix-chain multiplication）（PDF p.391–399）

给定 $n$ 个矩阵的序列（链）$\langle A_1, A_2, \dots, A_n\rangle$，求乘积

A_1A_2\cdots A_n. \tag{15.5}

先加括号消除歧义，再用标准的两矩阵乘法作子程序。矩阵乘法满足结合律，所有加括号方式结果相同。完全括号化（fully parenthesized）：单个矩阵，或两个完全括号化乘积的乘积再加一层括号。例如 $\langle A_1,A_2,A_3,A_4\rangle$ 有 5 种完全括号化：$(A_1(A_2(A_3A_4)))$、$(A_1((A_2A_3)A_4))$、$((A_1A_2)(A_3A_4))$、$((A_1(A_2A_3))A_4)$、$(((A_1A_2)A_3)A_4)$。

两矩阵乘法代价：

def MATRIX_MULTIPLY(A, B):
    if A.columns != B.rows:
        raise Error("incompatible dimensions")
    C = new_matrix(A.rows, B.columns)
    for i in range(A.rows):
        for j in range(B.columns):
            C[i][j] = 0
            for k in range(A.columns):
                C[i][j] += A[i][k] * B[k][j]
    return C

只有相容（compatible）（$A$ 的列数等于 $B$ 的行数）的矩阵才能相乘。$A$ 为 $p\times q$、$B$ 为 $q\times r$ 时，$C$ 为 $p\times r$，时间主要由 $pqr$ 次标量乘法决定；以下用标量乘法次数衡量代价。

例：$\langle A_1,A_2,A_3\rangle$ 维数为 $10\times100$、$100\times5$、$5\times50$。按 $((A_1A_2)A_3)$：$10\cdot100\cdot5 = 5000$ 次得 $10\times5$ 矩阵，再 $10\cdot5\cdot50 = 2500$ 次，共 7500 次。按 $(A_1(A_2A_3))$：$100\cdot5\cdot50 = 25000$ 次得 $100\times50$ 矩阵，再 $10\cdot100\cdot50 = 50000$ 次，共 75000 次。前者快 10 倍。

矩阵链乘法问题：给定 $n$ 个矩阵的链，$A_i$ 维数为 $p_{i-1}\times p_i$，求使标量乘法次数最少的完全括号化方案。注意目标不是真正做乘法，只是确定代价最低的计算顺序；花在确定顺序上的时间通常能被后来实际相乘节省的时间（例如 7500 次而不是 75000 次）抵偿。

括号化方案数：设 $P(n)$ 为 $n$ 个矩阵链的括号化方案数。$n=1$ 时只有一种；$n\ge2$ 时完全括号化乘积是两个完全括号化子乘积的乘积，分割点可在第 $k$ 与第 $k+1$ 个矩阵之间（$k = 1..n-1$）：

P(n) = \begin{cases}1 & n = 1,\\ \sum_{k=1}^{n-1}P(k)P(n-k) & n\ge 2.\end{cases} \tag{15.6}

类似递归式的解是 Catalan 数，增长为 $\Omega(4^n/n^{3/2})$；更简单地可证 $P(n) = \Omega(2^n)$（习题 15.2-3）。方案数是 $n$ 的指数，穷举很差。

步骤 1：最优括号化的结构。记 $A_{i..j}$（$i\le j$）为乘积 $A_iA_{i+1}\cdots A_j$ 的结果矩阵。若 $i<j$，任何括号化方案都要在某个 $A_k$ 与 $A_{k+1}$（$i\le k<j$）之间分开：先算 $A_{i..k}$ 和 $A_{k+1..j}$，再相乘。代价 = 计算 $A_{i..k}$ 的代价 + 计算 $A_{k+1..j}$ 的代价 + 两者相乘的代价。 最优子结构：若 $A_i\cdots A_j$ 的最优括号化在 $A_k$ 与 $A_{k+1}$ 之间分开，则其中"前缀"子链 $A_i\cdots A_k$ 的括号化必须是该子链的最优括号化——否则用更优的方案替换，就得到代价更低的 $A_i\cdots A_j$ 方案，矛盾。后缀子链 $A_{k+1}\cdots A_j$ 同理。因此可以把问题划分为两个子问题，求子问题实例的最优解，再组合；必须考察所有可能的划分点，以确保找到最优者。

步骤 2：递归解。子问题：对 $1\le i\le j\le n$ 求 $A_i\cdots A_j$ 括号化的最小代价。令 $m[i,j]$ 为计算 $A_{i..j}$ 所需标量乘法次数的最小值，原问题答案为 $m[1,n]$。$i=j$ 时 $m[i,i] = 0$。$i<j$ 时，若在 $A_k$、$A_{k+1}$ 间分开，因为 $A_{i..k}A_{k+1..j}$ 需 $p_{i-1}p_kp_j$ 次标量乘法，$m[i,j] = m[i,k] + m[k+1,j] + p_{i-1}p_kp_j$。$k$ 未知，但只有 $j-i$ 种可能，全部检查：

m[i,j] = \begin{cases}0 & i = j,\\ \min_{i\le k<j}\{m[i,k] + m[k+1,j] + p_{i-1}p_kp_j\} & i<j.\end{cases} \tag{15.7}

定义 $s[i,j]$ 为 $A_i\cdots A_j$ 最优括号化的分割点 $k$，即满足 $m[i,j] = m[i,k] + m[k+1,j] + p_{i-1}p_kp_j$ 的 $k$。

步骤 3：计算最优代价。直接按式 15.7 递归是指数时间（见 15.3 节），不比暴力好。注意不同子问题相对较少：每对满足 $1\le i\le j\le n$ 的 $(i,j)$ 一个子问题，共 $\binom n2 + n = \Theta(n^2)$ 个。递归算法会在递归树的不同分支中多次遇到同一子问题——这种**重叠子问题（overlapping subproblems）**性质是动态规划适用的第二个标志（第一个是最优子结构）。

采用表格化、自底向上的方法。输入 $p = \langle p_0, p_1, \dots, p_n\rangle$（$p.length = n+1$），辅助表 $m[1..n, 1..n]$ 存代价，$s[1..n-1, 2..n]$ 记录取得最优代价的 $k$。由式 15.7，$j-i+1$ 个矩阵链的代价 $m[i,j]$ 只依赖更短链（$A_{i..k}$ 有 $k-i+1 < j-i+1$ 个、$A_{k+1..j}$ 有 $j-k < j-i+1$ 个矩阵）的代价，所以按链长递增的顺序填表，子问题规模定义为链长 $j-i+1$。

def MATRIX_CHAIN_ORDER(p):
    n = len(p) - 1
    m = [[0] * (n + 1) for _ in range(n + 1)]
    s = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        m[i][i] = 0                          # 链长 1
    for l in range(2, n + 1):                # l 是链长
        for i in range(1, n - l + 2):
            j = i + l - 1
            m[i][j] = inf
            for k in range(i, j):
                q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]
                if q < m[i][j]:
                    m[i][j] = q
                    s[i][j] = k
    return m, s

图 15.5 例：$n=6$，维数 $A_1: 30\times35$，$A_2: 35\times15$，$A_3: 15\times5$，$A_4: 5\times10$，$A_5: 10\times20$，$A_6: 20\times25$（即 $p = \langle30,35,15,5,10,20,25\rangle$）。表旋转使主对角线水平；$m$ 只用主对角线及上三角，$s$ 只用上三角。$m[i,j]$ 位于从 $A_i$ 向东北、从 $A_j$ 向西北两条线的交点；每一水平行是同一链长的条目，自下而上、每行从左到右计算，每个 $m[i,j]$ 用乘积 $p_{i-1}p_kp_j$ 及其西南、东南方向的所有条目。最少标量乘法次数 $m[1,6] = 15125$。例如

m[2,5] = \min\begin{cases}m[2,2] + m[3,5] + p_1p_2p_5 = 0 + 2500 + 35\cdot15\cdot20 = 13000,\\ m[2,3] + m[4,5] + p_1p_3p_5 = 2625 + 1000 + 35\cdot5\cdot20 = 7125,\\ m[2,4] + m[5,5] + p_1p_4p_5 = 4375 + 0 + 35\cdot10\cdot20 = 11375\end{cases} = 7125.

表中其他值：$m[1,2]=15750$，$m[2,3]=2625$，$m[3,4]=750$，$m[4,5]=1000$，$m[5,6]=5000$；$m[1,3]=7875$，$m[2,4]=4375$，$m[3,5]=2500$，$m[4,6]=3500$；$m[1,4]=9375$，$m[2,5]=7125$，$m[3,6]=5375$；$m[1,5]=11875$，$m[2,6]=10500$；$m[1,6]=15125$。

复杂度：三重嵌套循环，每个循环变量（$l, i, k$）至多取 $n-1$ 个值，时间 $O(n^3)$；习题 15.2-5 证明也是 $\Omega(n^3)$。空间 $\Theta(n^2)$。远优于枚举所有括号化方案的指数时间方法。

步骤 4：构造最优解。$s[i,j]$ 记录 $A_i\cdots A_j$ 最优括号化的分割点 $k$，所以计算 $A_{1..n}$ 的最后一次乘法是 $A_{1..s[1,n]}A_{s[1,n]+1..n}$；递归地，$s[1, s[1,n]]$ 决定计算 $A_{1..s[1,n]}$ 的最后一次乘法，$s[s[1,n]+1, n]$ 决定计算 $A_{s[1,n]+1..n}$ 的最后一次乘法。

def PRINT_OPTIMAL_PARENS(s, i, j):
    if i == j:
        print(f"A{i}", end="")
    else:
        print("(", end="")
        PRINT_OPTIMAL_PARENS(s, i, s[i][j])
        PRINT_OPTIMAL_PARENS(s, s[i][j] + 1, j)
        print(")", end="")

图 15.5 的例子输出 $((A_1(A_2A_3))((A_4A_5)A_6))$。

习题 15.2 概括：15.2-1 对维数序列 ⟨5,10,3,12,5,50,6⟩ 求最优括号化；15.2-2 递归 MATRIX-CHAIN-MULTIPLY(A,s,i,j) 实际执行最优乘法；15.2-3 用代入法证明式 15.6 的解为 $\Omega(2^n)$；15.2-4 描述长度 $n$ 的矩阵链子问题图的顶点数与边数（$\Theta(n^2)$ 个顶点、$\Theta(n^3)$ 条边）；15.2-5 设 $R(i,j)$ 为计算其他条目时引用 $m[i,j]$ 的次数，证明 $\sum_{i=1}^n\sum_{j=i}^n R(i,j) = (n^3-n)/3$；15.2-6 $n$ 元素表达式的完全括号化恰有 $n-1$ 对括号。

15.3 动态规划原理（Elements of dynamic programming）（PDF p.399–411）

从工程角度，什么时候该找动态规划解法？最优化问题适用动态规划的两个要素：最优子结构和重叠子问题。本节还更全面地讨论备忘如何在自顶向下递归中利用重叠子问题。

最优子结构

用动态规划求解最优化问题的第一步是刻画最优解的结构。如果问题的最优解包含其子问题的最优解，就称问题具有最优子结构。这是动态规划可能适用的好线索（也可能意味着贪心适用，见第 16 章）。动态规划用子问题的最优解构造原问题的最优解，所以必须确保考察的子问题范围包含了最优解中用到的那些子问题。

发掘最优子结构的通用模式：

证明问题的一个解要做一个选择（如钢条的第一次切割位置、矩阵链的分割下标），做出选择后留下一个或多个待解的子问题。
假定对给定问题，已经知道哪种选择会得到最优解——暂不关心如何得到这个选择，只假定它已给出。
给定该选择，确定会产生哪些子问题，以及如何最好地刻画子问题空间。
用**"剪切—粘贴"（cut-and-paste）技术**证明：最优解中用到的子问题解本身必须是最优的。假设某子问题的解不是最优的，"剪掉"它、"粘贴"该子问题的最优解，就得到原问题更好的解，与原解最优矛盾。若最优解产生多个子问题，它们通常相似，论证稍作修改即可适用于其他子问题。

刻画子问题空间的经验法则：尽量保持简单，必要时再扩展。钢条切割中子问题空间是"对每个长度 $i$ 最优切割长 $i$ 的钢条"，已经足够。反之，如果矩阵链乘法把子问题空间限制为形如 $A_1A_2\cdots A_j$ 的乘积，最优括号化要在某个 $1\le k<j$ 处分割，除非能保证 $k$ 总等于 $j-1$，否则会出现 $A_{k+1}\cdots A_j$ 形式的子问题，不属于 $A_1\cdots A_j$ 的形式。所以该问题必须允许子问题在"两端"都变化，即 $i$ 和 $j$ 都可变。

最优子结构在不同问题中的两点差异：

原问题的最优解用到多少个子问题；
确定最优解用哪些子问题时有多少种选择。钢条切割：最优解只用一个子问题（规模 $n-i$），但要考察 $n$ 种 $i$。矩阵链子链 $A_i\cdots A_j$：用两个子问题，有 $j-i$ 种选择。

运行时间非正式地取决于两个因素的乘积：子问题总数 × 每个子问题考察的选择数。钢条切割 $\Theta(n)$ 个子问题、每个至多 $n$ 种选择，$O(n^2)$；矩阵链乘法 $\Theta(n^2)$ 个子问题、每个至多 $n-1$ 种选择，$O(n^3)$（实际 $\Theta(n^3)$）。用子问题图也可做同样分析：每个顶点是一个子问题，子问题的选择是与之关联的边。钢条切割子问题图 $n$ 个顶点、每顶点至多 $n$ 条边，$O(n^2)$；矩阵链乘法 $\Theta(n^2)$ 个顶点、每顶点度至多 $n-1$，顶点和边共 $O(n^3)$。

动态规划常以自底向上方式利用最优子结构：先求子问题的最优解，再在子问题中做选择得到原问题最优解。原问题解的代价通常是子问题代价加上选择本身直接产生的代价——钢条切割中是式 15.2 的 $p_i$，矩阵链乘法中是 $p_{i-1}p_kp_j$。

与贪心算法的区别（第 16 章）：贪心算法适用的问题也有最优子结构；主要不同是贪心算法不先求出子问题的最优解再做"有依据的"选择，而是先做"贪心"选择——当时看来最好的选择——然后求解剩下的一个子问题，不必求解所有可能相关的更小子问题。令人惊讶的是，有时这种策略是对的。

微妙之处：最优子结构不总成立

给定有向图 $G=(V,E)$ 和顶点 $u, v$：

无权最短路径（unweighted shortest path）：找从 $u$ 到 $v$ 边数最少的路径（必是简单路径，因为去掉环能得到更少边的路径）。（脚注："无权"区别于第 24、25 章的带权最短路径；无权问题可用第 22 章的广度优先搜索求解。）
无权最长简单路径（unweighted longest simple path）：找从 $u$ 到 $v$ 边数最多的简单路径（必须要求简单，否则可以绕环任意多次）。

最短路径具有最优子结构：设 $u\ne v$，从 $u$ 到 $v$ 的任意路径 $p$ 必含某个中间顶点 $w$（$w$ 可能是 $u$ 或 $v$），可分解为 $u \overset{p_1}{\leadsto} w \overset{p_2}{\leadsto} v$，$p$ 的边数等于 $p_1$ 与 $p_2$ 边数之和。若 $p$ 是最短的，则 $p_1$ 必是 $u$ 到 $w$ 的最短路径（剪切—粘贴：若有更短的 $p_1'$，替换后得到比 $p$ 更短的路径，矛盾）；$p_2$ 同理。因此可考察所有中间顶点 $w$，求 $u\to w$ 与 $w\to v$ 的最短路径，选使总长最短的 $w$。25.2 节用这一观察的变体求带权有向图中所有顶点对的最短路径。

最长简单路径不具有最优子结构。图 15.6：顶点 $q, r, s, t$，路径 $q\to r\to t$ 是 $q$ 到 $t$ 的最长简单路径，但 $q\to r$ 不是 $q$ 到 $r$ 的最长简单路径（$q\to s\to t\to r$ 更长），$r\to t$ 也不是 $r$ 到 $t$ 的最长简单路径（$r\to q\to s\to t$ 更长）。而且把子问题的解拼起来甚至不一定合法：拼接 $q\to s\to t\to r$ 与 $r\to q\to s\to t$ 得到 $q\to s\to t\to r\to q\to s\to t$，不是简单路径。该问题似乎没有任何形式的最优子结构，至今没有高效的动态规划算法——实际上它是 NP 完全的（第 34 章），不太可能有多项式时间解法。

根本原因：子问题是否独立（independent）。两个问题都用两个子问题，但最长简单路径的子问题不独立，最短路径的子问题独立。独立指同一问题的一个子问题的解不影响另一个子问题的解。在图 15.6 中求 $q$ 到 $t$ 的最长简单路径，两个子问题是求 $q$ 到 $r$ 与 $r$ 到 $t$ 的最长简单路径；第一个子问题选了 $q\to s\to t\to r$，用掉了 $s$ 和 $t$，第二个子问题就不能再用它们（否则组合后不是简单路径），而第二个子问题必须用 $t$（$t$ 必须在路径上且不是拼接点 $r$），甚至要最优地求解必须同时用 $s$ 和 $t$。换言之，求解一个子问题时用掉的资源（顶点）在另一个子问题中不可用。

最短路径的子问题天然不共享资源：若 $w$ 在 $u$ 到 $v$ 的最短路径 $p$ 上，则可以把任意最短路径 $u\overset{p_1}{\leadsto}w$ 与任意最短路径 $w\overset{p_2}{\leadsto}v$ 拼接成 $u$ 到 $v$ 的最短路径，且除 $w$ 外没有顶点同时出现在 $p_1$、$p_2$ 中。证明：若某 $x\ne w$ 同时出现，把 $p_1$ 分解为 $u\overset{p_{ux}}{\leadsto}x\leadsto w$，$p_2$ 分解为 $w\leadsto x\overset{p_{xv}}{\leadsto}v$。由最优子结构，$p$ 的边数 $e$ 等于 $p_1$ 与 $p_2$ 边数之和；构造 $p' = u\overset{p_{ux}}{\leadsto}x\overset{p_{xv}}{\leadsto}v$，去掉了 $x$ 到 $w$、$w$ 到 $x$ 两段（各至少一条边），$p'$ 至多 $e-2$ 条边，与 $p$ 最短矛盾。

15.1、15.2 节的问题都具有独立子问题：矩阵链中子链 $A_i\cdots A_k$ 与 $A_{k+1}\cdots A_j$ 不相交，没有矩阵能同时在两者中；钢条切割的最优解（切下第一段后）只包含一个子问题的解，独立性不成问题。

重叠子问题

适用动态规划的第二个要素是：子问题空间要"足够小"，即递归算法会反复求解相同的子问题，而不是一直生成新的子问题。不同子问题总数通常是输入规模的多项式。递归算法反复求解相同问题时，称最优化问题具有重叠子问题。相反，适合分治法的问题在递归的每一步通常都生成全新的子问题。动态规划对每个子问题只求解一次，存入表中，需要时以常数时间查表。

脚注：动态规划既要求子问题"独立"又要求"重叠"，听起来矛盾，但这是两个不同的概念而非同一维度上的两点：同一问题的两个子问题若不共享资源则独立；两个子问题若实际上是作为不同问题的子问题出现的同一个子问题，则重叠。

钢条切割的朴素递归做指数次调用；动态规划把指数时间降到二次。矩阵链乘法中，MATRIX-CHAIN-ORDER 在计算较高行时反复查找较低行子问题的解，例如 $m[3,4]$ 被引用 4 次（计算 $m[2,4]$、$m[1,4]$、$m[3,5]$、$m[3,6]$ 时）。若每次都重新计算而不是查表，运行时间会急剧增加。考虑直接基于式 15.7 的低效递归过程：

def RECURSIVE_MATRIX_CHAIN(p, i, j):
    if i == j:
        return 0
    m[i][j] = inf
    for k in range(i, j):
        q = (RECURSIVE_MATRIX_CHAIN(p, i, k)
             + RECURSIVE_MATRIX_CHAIN(p, k + 1, j)
             + p[i - 1] * p[k] * p[j])
        if q < m[i][j]:
            m[i][j] = q
    return m[i][j]

图 15.7 是 RECURSIVE-MATRIX-CHAIN(p,1,4) 的递归树，每个结点标注参数 $i..j$，许多参数对出现多次（如 3..4、2..3 等）。

指数下界：设 $T(n)$ 为计算 $n$ 个矩阵链最优括号化的时间。第 1–2 行与第 6–7 行各至少单位时间，第 5 行乘法也是，得

T(1)\ge1,\qquad T(n)\ge 1 + \sum_{k=1}^{n-1}(T(k) + T(n-k) + 1)\quad (n>1).

每个 $T(i)$（$i = 1..n-1$）作为 $T(k)$ 和 $T(n-k)$ 各出现一次，把 $n-1$ 个 1 与前面的 1 合并：

T(n) \ge 2\sum_{i=1}^{n-1}T(i) + n. \tag{15.8}

用代入法证 $T(n) \ge 2^{n-1}$：基础 $T(1)\ge1 = 2^0$；归纳 $n\ge2$：

T(n) \ge 2\sum_{i=1}^{n-1}2^{i-1} + n = 2\sum_{i=0}^{n-2}2^i + n = 2(2^{n-1}-1) + n = 2^n - 2 + n \ge 2^{n-1}.

所以 RECURSIVE-MATRIX-CHAIN(p,1,n) 的工作量至少是 $n$ 的指数。自底向上动态规划更高效，因为矩阵链乘法只有 $\Theta(n^2)$ 个不同子问题，动态规划对每个只求解一次；而递归算法每当子问题在递归树中再次出现都要重新求解。只要自然递归解的递归树中反复出现相同子问题、且不同子问题总数少，动态规划就能提高效率，有时是急剧提高。

重构最优解

实践中通常把每个子问题所做的选择存在表中，就不必从存储的代价中重建这些信息。矩阵链乘法中，若只有 $m[i,j]$ 而没有 $s[i,j]$，确定 $A_i\cdots A_j$ 最优解用了哪些子问题需要在 $j-i$ 种可能中选择，$j-i$ 不是常数，重建每个选择要 $\Theta(j-i) = \omega(1)$ 时间；存了 $s[i,j]$ 就能 $O(1)$ 重建每个选择。

备忘（Memoization）

另一种动态规划方法：既有自底向上法的效率，又保持自顶向下策略——给自然但低效的递归算法加上备忘。与自底向上法一样维护一张子问题解的表，但填表的控制结构更像递归算法。每个表项初值为表示"尚未填入"的特殊值；递归中第一次遇到某子问题时计算其解并存表，以后再遇到时直接查表返回。（脚注：这要求预先知道所有可能的子问题参数并建立表位置与子问题的对应关系；更一般的做法是以子问题参数为关键字，用散列表做备忘。）

def MEMOIZED_MATRIX_CHAIN(p):
    n = len(p) - 1
    m = [[inf] * (n + 1) for _ in range(n + 1)]   # inf 表示尚未计算
    return LOOKUP_CHAIN(m, p, 1, n)

def LOOKUP_CHAIN(m, p, i, j):
    if m[i][j] < inf:
        return m[i][j]               # 已计算，直接返回
    if i == j:
        m[i][j] = 0
    else:
        for k in range(i, j):
            q = (LOOKUP_CHAIN(m, p, i, k)
                 + LOOKUP_CHAIN(m, p, k + 1, j)
                 + p[i - 1] * p[k] * p[j])
            if q < m[i][j]:
                m[i][j] = q
    return m[i][j]

LOOKUP-CHAIN(m,p,i,j) 总是返回 $m[i,j]$，但只在第一次以这组 $(i,j)$ 调用时计算。图 15.7 中阴影子树表示被查表取代的计算。

复杂度 $O(n^3)$：MEMOIZED-MATRIX-CHAIN 第 5 行执行 $\Theta(n^2)$ 次。LOOKUP-CHAIN 的调用分两类：(1) $m[i,j] = \infty$，执行第 3–9 行；(2) $m[i,j] < \infty$，直接在第 2 行返回。第一类共 $\Theta(n^2)$ 次，每个表项一次；第二类都是第一类调用发出的递归调用，每个第一类调用发出 $O(n)$ 个递归调用，所以第二类共 $O(n^3)$ 次，每次 $O(1)$；第一类每次 $O(n)$ 加递归调用的时间。总时间 $O(n^3)$。备忘把 $\Omega(2^n)$ 的算法变成 $O(n^3)$。空间 $\Theta(n^2)$。

总结与选择：矩阵链乘法可用自顶向下带备忘或自底向上的动态规划在 $O(n^3)$ 内求解，都利用了重叠子问题——总共只有 $\Theta(n^2)$ 个不同子问题，每个只求解一次；不备忘的自然递归是指数时间。实践中，若所有子问题都至少要解一次，自底向上算法通常比自顶向下备忘算法快一个常数因子（无递归开销、维护表的开销更小）；而且对某些问题可以利用表访问的规律进一步减少时间或空间。反之，若子问题空间中某些子问题根本不必求解，备忘方法只求解确实需要的子问题，更有优势。

习题 15.3 概括（PDF p.410–411）

15.3-1：枚举所有括号化方案并逐一计算，与运行 RECURSIVE-MATRIX-CHAIN 相比哪个更高效（后者：其调用次数 $O(n3^{n-1})$ 优于 Catalan 数级的 $\Omega(4^n/n^{3/2})$ 方案数乘以每方案 $O(n)$ 计算）。
15.3-2：画 16 元素归并排序的递归树，说明备忘为何无法加速好的分治算法（子问题不重叠）。
15.3-3：矩阵链乘法改为最大化标量乘法次数，是否仍有最优子结构（有）。
15.3-4：Capulet 教授提出在求解子问题前按最小化 $p_{i-1}p_kp_j$ 的贪心规则选分割点，构造反例说明得到次优解。
15.3-5：钢条切割中若每种长度 $i$ 的段数限制为 $l_i$，最优子结构不再成立（子问题之间共享"配额"资源，不独立）。
15.3-6：货币兑换：$n$ 种货币，从货币 1 换到货币 $n$，汇率 $r_{ij}$（$d$ 单位货币 $i$ 换得 $dr_{ij}$ 单位货币 $j$），做 $k$ 次兑换收佣金 $c_k$。证明 $c_k \equiv 0$ 时求最优兑换序列具有最优子结构；而 $c_k$ 任意时不一定具有最优子结构。

15.4 最长公共子序列（Longest common subsequence）（PDF p.411–418）

动机：生物学中比较两种生物的 DNA。DNA 链是由碱基（腺嘌呤 A、鸟嘌呤 G、胞嘧啶 C、胸腺嘧啶 T）组成的串，可表示为有限集 $\{A,C,G,T\}$ 上的字符串。例如 $S_1 = $ ACCGGTCGAGTGCGCGGAAGCCGGCCGAA，$S_2 = $ GTCGTTCGGAATGCCGTTGCTCTGTAAA。相似度有多种定义：一个是另一个的子串（第 32 章）；把一个变为另一个所需改动少（思考题 15-5 编辑距离）；或找第三条链 $S_3$，其碱基按相同顺序（不必连续）出现在 $S_1$ 和 $S_2$ 中，$S_3$ 越长越相似。例中最长的 $S_3$ 为 GTCGTCGGAAGCCGGCCGAA。

定义：给定序列 $X = \langle x_1,\dots,x_m\rangle$，序列 $Z = \langle z_1,\dots,z_k\rangle$ 是 $X$ 的子序列（subsequence），若存在 $X$ 的严格递增下标序列 $\langle i_1,\dots,i_k\rangle$ 使对所有 $j$ 有 $x_{i_j} = z_j$（即删去零个或多个元素）。例：$Z = \langle B,C,D,B\rangle$ 是 $X = \langle A,B,C,B,D,A,B\rangle$ 的子序列，下标序列 ⟨2,3,5,7⟩。$Z$ 同时是 $X$ 和 $Y$ 的子序列时称为公共子序列（common subsequence）。例：$X = \langle A,B,C,B,D,A,B\rangle$，$Y = \langle B,D,C,A,B,A\rangle$，⟨B,C,A⟩ 是公共子序列但不是最长公共子序列（LCS）；⟨B,C,B,A⟩ 和 ⟨B,D,A,B⟩ 都是 LCS（长度 4，不存在长度 ≥5 的公共子序列）。LCS 问题：给定 $X$、$Y$，求最长公共子序列。

步骤 1：刻画 LCS。暴力法枚举 $X$ 的所有 $2^m$ 个子序列（对应下标集合 $\{1..m\}$ 的子集）并检查是否为 $Y$ 的子序列，指数时间。定义 $X$ 的第 $i$ 个前缀（prefix） $X_i = \langle x_1,\dots,x_i\rangle$（$i = 0..m$），如 $X_4 = \langle A,B,C,B\rangle$，$X_0$ 为空序列。子问题自然对应两输入序列的前缀对。

定理 15.1（LCS 的最优子结构）：设 $X = \langle x_1..x_m\rangle$，$Y = \langle y_1..y_n\rangle$，$Z = \langle z_1..z_k\rangle$ 是 $X$ 和 $Y$ 的任意 LCS。

若 $x_m = y_n$，则 $z_k = x_m = y_n$，且 $Z_{k-1}$ 是 $X_{m-1}$ 和 $Y_{n-1}$ 的一个 LCS。
若 $x_m \ne y_n$，则 $z_k \ne x_m$ 意味着 $Z$ 是 $X_{m-1}$ 和 $Y$ 的一个 LCS。
若 $x_m \ne y_n$，则 $z_k \ne y_n$ 意味着 $Z$ 是 $X$ 和 $Y_{n-1}$ 的一个 LCS。

证明：(1) 若 $z_k \ne x_m$，把 $x_m = y_n$ 追加到 $Z$ 得长度 $k+1$ 的公共子序列，与 $Z$ 最长矛盾，故 $z_k = x_m = y_n$。前缀 $Z_{k-1}$ 是 $X_{m-1}$ 和 $Y_{n-1}$ 的长度 $k-1$ 的公共子序列；若有更长的公共子序列 $W$（长度 $>k-1$），追加 $x_m = y_n$ 得到 $X$、$Y$ 长度 $>k$ 的公共子序列，矛盾。(2) 若 $z_k \ne x_m$，$Z$ 是 $X_{m-1}$ 和 $Y$ 的公共子序列；若有更长的公共子序列 $W$，它也是 $X_m$ 和 $Y$ 的公共子序列，与 $Z$ 是 LCS 矛盾。(3) 与 (2) 对称。结论：两个序列的 LCS 包含两个序列前缀的 LCS，具有最优子结构。

步骤 2：递归解。若 $x_m = y_n$，求 $X_{m-1}$ 与 $Y_{n-1}$ 的 LCS，再追加 $x_m$；若 $x_m \ne y_n$，求解两个子问题——$X_{m-1}$ 与 $Y$ 的 LCS、$X$ 与 $Y_{n-1}$ 的 LCS——取较长者。这些情况穷尽所有可能。重叠子问题明显：求 $X$ 与 $Y_{n-1}$ 的 LCS 和求 $X_{m-1}$ 与 $Y$ 的 LCS 都包含子子问题"$X_{m-1}$ 与 $Y_{n-1}$ 的 LCS"。令 $c[i,j]$ 为 $X_i$ 与 $Y_j$ 的 LCS 长度：

c[i,j] = \begin{cases}0 & i = 0 \text{ 或 } j = 0,\\ c[i-1,j-1] + 1 & i,j>0 \text{ 且 } x_i = y_j,\\ \max(c[i,j-1],\ c[i-1,j]) & i,j>0 \text{ 且 } x_i \ne y_j.\end{cases} \tag{15.9}

注意：问题中的条件限制了可考虑的子问题——$x_i = y_j$ 时只考虑 $X_{i-1}$ 与 $Y_{j-1}$；否则考虑另两个。钢条切割和矩阵链乘法中没有因问题条件排除子问题；编辑距离（思考题 15-5）也有这一特点。

步骤 3：计算 LCS 长度。按式 15.9 直接递归是指数时间，但只有 $\Theta(mn)$ 个不同子问题，可自底向上计算。LCS-LENGTH 把 $c[i,j]$ 存在表 $c[0..m, 0..n]$ 中，按**行主序（row-major order）**计算（先从左到右填第一行，再第二行……），同时维护表 $b[1..m, 1..n]$，$b[i,j]$ 指向计算 $c[i,j]$ 时所选的最优子问题解对应的表项。

def LCS_LENGTH(X, Y):
    m, n = len(X), len(Y)
    c = [[0] * (n + 1) for _ in range(m + 1)]     # c[i][0] = c[0][j] = 0
    b = [[None] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i] == Y[j]:
                c[i][j] = c[i - 1][j - 1] + 1
                b[i][j] = "↖"                     # 对角：x_i 属于 LCS
            elif c[i - 1][j] >= c[i][j - 1]:
                c[i][j] = c[i - 1][j]
                b[i][j] = "↑"
            else:
                c[i][j] = c[i][j - 1]
                b[i][j] = "←"
    return c, b
# 时间 Θ(mn)（每个表项 Θ(1)），空间 Θ(mn)

图 15.8：对 $X = \langle A,B,C,B,D,A,B\rangle$、$Y = \langle B,D,C,A,B,A\rangle$，右下角 $c[7,6] = 4$ 是 LCS ⟨B,C,B,A⟩ 的长度。对 $i,j>0$，$c[i,j]$ 只依赖于 $x_i = y_j$ 是否成立以及 $c[i-1,j]$、$c[i,j-1]$、$c[i-1,j-1]$，它们都在 $c[i,j]$ 之前算出。

步骤 4：构造 LCS。从 $b[m,n]$ 开始沿箭头回溯；遇到"↖"表示 $x_i = y_j$ 是 LCS 的元素。这样得到的元素是逆序的，用递归按正序输出：

def PRINT_LCS(b, X, i, j):          # 初始调用 PRINT_LCS(b, X, m, n)
    if i == 0 or j == 0:
        return
    if b[i][j] == "↖":
        PRINT_LCS(b, X, i - 1, j - 1)
        print(X[i], end="")
    elif b[i][j] == "↑":
        PRINT_LCS(b, X, i - 1, j)
    else:
        PRINT_LCS(b, X, i, j - 1)
# 时间 O(m + n)：每次递归至少使 i 或 j 减 1

图 15.8 的 $b$ 表输出 BCBA。

改进代码：算法开发出来后常能改进时间或空间；有的改动只简化代码、改善常数，有的能带来渐近节省。

可以完全去掉 $b$ 表：每个 $c[i,j]$ 只依赖 $c[i-1,j-1]$、$c[i-1,j]$、$c[i,j-1]$ 三项，给定 $c[i,j]$ 可在 $O(1)$ 内判断用的是哪一项，从而 $O(m+n)$ 重构 LCS（习题 15.4-2）。这节省了 $\Theta(mn)$ 空间，但辅助空间渐近上没有减少，因为 $c$ 表仍需 $\Theta(mn)$。
若只需 LCS 的长度，可降低渐近空间：计算时只需 $c$ 的两行（当前行和上一行）；实际上只需略多于一行的空间（习题 15.4-4）。但若要重构 LCS 元素，小表不保存足够信息，无法在 $O(m+n)$ 内回溯。

习题 15.4 概括：15.4-1 求 ⟨1,0,0,1,0,1,0,1⟩ 与 ⟨0,1,0,1,1,0,1,1,0⟩ 的 LCS；15.4-2 不用 $b$ 表 $O(m+n)$ 重构 LCS；15.4-3 $O(mn)$ 的备忘版 LCS-LENGTH；15.4-4 只用 $2\min(m,n)$ 个表项加 $O(1)$ 额外空间求 LCS 长度，再改进到 $\min(m,n)$ 个表项加 $O(1)$；15.4-5 $O(n^2)$ 求 $n$ 个数的最长单调递增子序列（LIS）；15.4-6（星号）$O(n\lg n)$ 求 LIS（提示：长度为 $i$ 的候选子序列末元素至少与长度 $i-1$ 的候选末元素一样大；维护各长度候选的最小末元素并二分查找）。

15.5 最优二叉搜索树（Optimal binary search trees）（PDF p.418–425）

动机：设计英译法程序，对文本中每个英语单词的每次出现查找其法语对应词。可以建一棵以 $n$ 个英语单词为关键字、法语译文为卫星数据的二叉搜索树。用红黑树可保证每次 $O(\lg n)$，但单词出现频率不同：常用词（如 the）可能离根很远，罕用词（如 machicolation）可能靠近根，拖慢翻译——因为搜索某关键字访问的结点数等于该结点深度加 1。希望频繁出现的词靠近根（脚注：若文本主题是城堡建筑，可能希望 machicolation 靠近根；该词法语为 mâchicoulis）。另外有些词没有法语译文，根本不在树中。已知每个词的出现频率，如何组织 BST 使所有搜索访问的结点总数最少？这就是**最优二叉搜索树（optimal binary search tree）**问题。

形式化：给定 $n$ 个互异的有序关键字 $K = \langle k_1,\dots,k_n\rangle$（$k_1 < k_2 < \dots < k_n$），搜索 $k_i$ 的概率为 $p_i$。有些搜索的值不在 $K$ 中，所以还有 $n+1$ 个伪关键字（dummy keys） $d_0, d_1, \dots, d_n$：$d_0$ 表示所有小于 $k_1$ 的值，$d_n$ 表示所有大于 $k_n$ 的值，$d_i$（$1\le i\le n-1$）表示 $k_i$ 与 $k_{i+1}$ 之间的所有值；搜索对应 $d_i$ 的概率为 $q_i$。每个 $k_i$ 是内部结点，每个 $d_i$ 是叶。每次搜索要么成功（找到某 $k_i$），要么失败（找到某 $d_i$）：

\sum_{i=1}^n p_i + \sum_{i=0}^n q_i = 1. \tag{15.10}

设搜索的实际代价为检查的结点数，即所找到结点在 $T$ 中的深度加 1。$T$ 中一次搜索的期望代价：

E[\text{search cost in } T] = \sum_{i=1}^n(\text{depth}_T(k_i)+1)p_i + \sum_{i=0}^n(\text{depth}_T(d_i)+1)q_i = 1 + \sum_{i=1}^n\text{depth}_T(k_i)\,p_i + \sum_{i=0}^n\text{depth}_T(d_i)\,q_i. \tag{15.11}

图 15.9 例（$n=5$）：

$i$	0	1	2	3	4	5
$p_i$		0.15	0.10	0.05	0.10	0.20
$q_i$	0.05	0.10	0.05	0.05	0.05	0.10

树 (a)（根 $k_2$，左 $k_1$，右 $k_4$，$k_4$ 的孩子 $k_3$、$k_5$）逐结点计算：$k_1$ 深度 1 贡献 0.30；$k_2$ 深度 0 贡献 0.10；$k_3$ 深度 2 贡献 0.15；$k_4$ 深度 1 贡献 0.20；$k_5$ 深度 2 贡献 0.60；$d_0$ 深度 2 贡献 0.15；$d_1$ 深度 2 贡献 0.30；$d_2$–$d_4$ 深度 3 各贡献 0.20；$d_5$ 深度 3 贡献 0.40；总计 2.80。树 (b)（根 $k_2$，右孩子 $k_5$，$k_5$ 左孩子 $k_4$，$k_4$ 左孩子 $k_3$）期望代价 2.75，是最优的。要点：最优 BST 不一定是整体高度最小的树；也不能总是把概率最大的关键字放在根——$k_5$ 概率最大，但最优树的根是 $k_2$（以 $k_5$ 为根的 BST 最低期望代价为 2.85）。

穷举不可行：任意 $n$ 结点二叉树都可用 $k_1..k_n$ 标号成 BST 再加伪关键字为叶，由思考题 12-4，$n$ 结点二叉树有 $\Omega(4^n/n^{3/2})$ 棵，指数级。

步骤 1：最优 BST 的结构。BST 的任一子树必包含连续区间的关键字 $k_i..k_j$（$1\le i\le j\le n$），且其叶为伪关键字 $d_{i-1}..d_j$。最优子结构：若最优 BST $T$ 有包含 $k_i..k_j$ 的子树 $T'$，则 $T'$ 对于关键字 $k_i..k_j$、伪关键字 $d_{i-1}..d_j$ 的子问题也必须最优（剪切—粘贴：若有期望代价更低的 $T''$，替换后得到比 $T$ 更低期望代价的树，矛盾）。构造：给定 $k_i..k_j$，其中某个 $k_r$（$i\le r\le j$）是最优子树的根，左子树含 $k_i..k_{r-1}$（及 $d_{i-1}..d_{r-1}$），右子树含 $k_{r+1}..k_j$（及 $d_r..d_j$）。只要考察所有候选根 $k_r$ 并求出左右两侧的最优 BST，就能保证找到最优 BST。 空子树约定：若选 $k_i$ 为根，左子树"包含 $k_i..k_{i-1}$"，理解为不含实际关键字但包含唯一伪关键字 $d_{i-1}$；对称地选 $k_j$ 为根时，右子树不含实际关键字但含伪关键字 $d_j$。

步骤 2：递归解。子问题域：对 $i\ge1$、$j\le n$、$j\ge i-1$，求包含 $k_i..k_j$ 的最优 BST（$j = i-1$ 时只有伪关键字 $d_{i-1}$）。令 $e[i,j]$ 为其期望搜索代价，最终求 $e[1,n]$。

$j = i-1$：$e[i,i-1] = q_{i-1}$。
$j\ge i$：选根 $k_r$，左子树为 $k_i..k_{r-1}$ 的最优 BST，右子树为 $k_{r+1}..k_j$ 的最优 BST。一棵子树成为某结点的子树时，其中每个结点深度加 1，由式 15.11 期望代价增加子树中所有概率之和。记 $w(i,j) = \sum_{l=i}^j p_l + \sum_{l=i-1}^j q_l. \tag{15.12}$ 若 $k_r$ 为根，$e[i,j] = p_r + (e[i,r-1] + w(i,r-1)) + (e[r+1,j] + w(r+1,j))$，而 $w(i,j) = w(i,r-1) + p_r + w(r+1,j)$，所以 $e[i,j] = e[i,r-1] + e[r+1,j] + w(i,j). \tag{15.13}$ 选使期望代价最低的根： $e[i,j] = \begin{cases}q_{i-1} & j = i-1,\\ \min_{i\le r\le j}\{e[i,r-1] + e[r+1,j] + w(i,j)\} & i\le j.\end{cases} \tag{15.14}$ 定义 $root[i,j]$（$1\le i\le j\le n$）为包含 $k_i..k_j$ 的最优 BST 的根 $k_r$ 的下标 $r$（由 root 表构造最优树留作习题 15.5-1）。

步骤 3：计算。与矩阵链乘法类似，子问题都是连续的下标子区间；直接递归同样低效。用表 $e[1..n+1, 0..n]$：第一维到 $n+1$，因为只含伪关键字 $d_n$ 的子树需要 $e[n+1,n]$；第二维从 0 开始，因为只含 $d_0$ 的子树需要 $e[1,0]$；只用 $j\ge i-1$ 的表项。$root[i,j]$ 只用 $1\le i\le j\le n$ 的表项。为提高效率，不每次从头算 $w(i,j)$（需 $\Theta(j-i)$ 次加法），而是存表 $w[1..n+1, 0..n]$：$w[i,i-1] = q_{i-1}$，$j\ge i$ 时

w[i,j] = w[i,j-1] + p_j + q_j, \tag{15.15}

每个 $\Theta(1)$，共 $\Theta(n^2)$ 个。

def OPTIMAL_BST(p, q, n):
    e = [[0] * (n + 1) for _ in range(n + 2)]     # e[1..n+1][0..n]
    w = [[0] * (n + 1) for _ in range(n + 2)]
    root = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 2):
        e[i][i - 1] = q[i - 1]
        w[i][i - 1] = q[i - 1]
    for l in range(1, n + 1):                     # 子树含 l 个关键字
        for i in range(1, n - l + 2):
            j = i + l - 1
            e[i][j] = inf
            w[i][j] = w[i][j - 1] + p[j] + q[j]
            for r in range(i, j + 1):             # 尝试每个候选根
                t = e[i][r - 1] + e[r + 1][j] + w[i][j]
                if t < e[i][j]:
                    e[i][j] = t
                    root[i][j] = r
    return e, root
# 时间 Θ(n^3)，空间 Θ(n^2)

第一次迭代 $l=1$ 计算 $e[i,i]$、$w[i,i]$，$l=2$ 计算 $e[i,i+1]$、$w[i,i+1]$，依此类推；最内层循环尝试每个候选根 $r$，找到更好的根时把 $r$ 存入 $root[i,j]$。图 15.10 给出对图 15.9 分布计算出的表（旋转使对角线水平）：$e[1,5] = 2.75$，$w[1,5] = 1.00$；root 表中 $root[1,5] = 2$、$root[2,5] = 5$（等）。 复杂度：三重循环，每个循环变量至多取 $n$ 个值，$O(n^3)$；与 MATRIX-CHAIN-ORDER 循环界最多差 1，所以也是 $\Omega(n^3)$，即 $\Theta(n^3)$。

习题 15.5 概括：15.5-1 写 CONSTRUCT-OPTIMAL-BST(root) 输出最优树结构，对图 15.10 应输出：$k_2$ 为根；$k_1$ 是 $k_2$ 左孩子；$d_0$、$d_1$ 是 $k_1$ 左右孩子；$k_5$ 是 $k_2$ 右孩子；$k_4$ 是 $k_5$ 左孩子；$k_3$ 是 $k_4$ 左孩子；$d_2$、$d_3$ 是 $k_3$ 左右孩子；$d_4$ 是 $k_4$ 右孩子；$d_5$ 是 $k_5$ 右孩子。15.5-2 对 $n=7$ 的给定概率（$p = 0.04,0.06,0.08,0.02,0.10,0.12,0.14$；$q = 0.06,0.06,0.06,0.06,0.05,0.05,0.05,0.05$）求最优 BST 代价与结构；15.5-3 若不维护 $w$ 表而每次按式 15.12 直接计算，渐近时间不变（仍 $\Theta(n^3)$，因为最内层循环本来就是 $\Theta(j-i)$）；15.5-4（星号）Knuth 证明总存在最优子树的根满足 $root[i,j-1] \le root[i,j] \le root[i+1,j]$，据此把 OPTIMAL-BST 改进到 $\Theta(n^2)$（Knuth 优化，单调性使最内层循环总量摊还为 $O(n)$ 每条对角线）。

第 15 章思考题（PDF p.425–433）

15-1 有向无环图中的最长简单路径：带实数边权的 DAG $G=(V,E)$ 与两个顶点 $s$、$t$，给出求 $s$ 到 $t$ 的最长带权简单路径的动态规划方法，描述子问题图并分析效率（按拓扑序 DP，$O(V+E)$；DAG 中无环，故无最长简单路径的"资源冲突"问题）。
15-2 最长回文子序列：**回文（palindrome）**是正读反读都相同的非空串（如所有长度 1 的串、civic、racecar、aibohphobia）。求给定串中最长的回文子序列，例如 character 返回 carac。（区间 DP，$O(n^2)$；或求串与其逆串的 LCS。）
15-3 双调欧几里得旅行商问题（bitonic euclidean TSP）：平面上 $n$ 个点，求连接所有点的最短闭合回路。一般问题是 NP 难的。Bentley 建议只考虑双调回路（bitonic tour）：从最左点出发严格向右到最右点，再严格向左回到起点。图 15.11：7 个点的最短回路长约 24.89（非双调），最短双调回路长约 25.58。要求 $O(n^2)$ 算法（假设点的 $x$ 坐标互异、实数运算单位时间；提示：从左到右扫描，维护回路两部分的最优可能）。
15-4 整齐打印（printing neatly）：等宽字体，$n$ 个单词长度 $l_1..l_n$（字符数），每行最多 $M$ 个字符。某行放单词 $i..j$、词间一个空格时，行末多余空格数为 $M - j + i - \sum_{k=i}^j l_k$（必须非负）。目标：最小化除最后一行外各行行末多余空格数的立方和。给出 DP 算法并分析时间空间（$O(nM)$ 或 $O(n^2)$）。
15-5 编辑距离（edit distance）：把源串 $x[1..m]$ 变为目标串 $y[1..n]$，用数组 $z$ 存中间结果，维护 $x$ 中下标 $i$ 和 $z$ 中下标 $j$（初始 $i=j=1$），结束时必须 $i = m+1$（检查过 $x$ 的每个字符）且 $z[j] = y[j]$。六种操作：复制（copy） $z[j] = x[i]$，$i,j$ 各加 1；替换（replace） $z[j] = c$，$i,j$ 各加 1；删除（delete） $i$ 加 1；插入（insert） $z[j] = c$，$j$ 加 1；交换（twiddle） $z[j] = x[i+1]$、$z[j+1] = x[i]$，$i,j$ 各加 2；删尾（kill） $i = m+1$，必须是最后一个操作。例：algorithm → altruistic 的一种操作序列为 copy、copy、replace by t、delete、copy、insert u、insert i、insert s、twiddle、insert c、kill，代价 $3\cdot\text{cost(copy)} + \text{cost(replace)} + \text{cost(delete)} + 4\cdot\text{cost(insert)} + \text{cost(twiddle)} + \text{cost(kill)}$。每种操作代价为已知常数，并假设 copy 与 replace 的代价各自小于 delete 与 insert 代价之和。(a) 编辑距离是把 $x$ 变为 $y$ 的最便宜操作序列的代价，给出 DP 算法求编辑距离并输出最优操作序列，分析时间和空间（$\Theta(mn)$）。(b) DNA 序列比对（alignment）：在两序列任意位置（含两端）插入空格，使得到的 $x'$、$y'$ 等长且没有同一位置都是空格；每位置得分：相同且非空格 +1，不同且非空格 −1，任一为空格 −2；比对得分为各位置之和。例：$x = $ GATCGGCAT，$y = $ CAATGTGAATC 的一种比对得分 $6\cdot1 - 2\cdot1 - 4\cdot2 = -4$。说明如何用 copy、replace、delete、insert、twiddle、kill 的子集（及相应代价）把最优比对问题表述为编辑距离问题（copy 代价 −1，replace +1，delete/insert +2，不用 twiddle 和 kill）。
15-6 公司聚会：公司层级结构是以总裁为根的树（左孩子右兄弟表示），每个员工有"欢乐度"实数评分；总裁不希望员工与其直接上司同时出席。求宾客名单使欢乐度总和最大，分析时间（树形 DP，每个结点算"来/不来"两个值，$O(n)$）。
15-7 Viterbi 算法：语音识别中的有向图 $G=(V,E)$，每条边 $(u,v)$ 标有来自有限集 $\Sigma$ 的声音 $\sigma(u,v)$，从特定顶点 $v_0$ 出发的每条路径对应模型可能产生的一个声音序列，路径标签为各边标签的串联。(a) 给定声音序列 $s = \langle\sigma_1..\sigma_k\rangle$，返回从 $v_0$ 出发、标签为 $s$ 的路径，若不存在返回 NO-SUCH-PATH，分析时间（$O(k(V+E))$）。(b) 每条边有非负概率 $p(u,v)$（从 $u$ 出发的边概率和为 1），路径概率为各边概率之积（可看作从 $v_0$ 出发的随机游走沿该路径走的概率）；扩展 (a) 使返回的是标签为 $s$ 的最可能路径，分析时间。（这就是隐马尔可夫模型的 Viterbi 解码。）
15-8 基于接缝裁剪（seam carving）的图像压缩：$m\times n$ 像素数组，每行删一个像素使图像窄一列，要求相邻两行删除的像素在同一列或相邻列，形成一条从顶行到底行的"接缝"。(a) 证明 $n>1$ 时可能的接缝数至少是 $m$ 的指数；(b) 每个像素有破坏度 $d[i,j]$（越低越与邻居相似），接缝破坏度为其像素破坏度之和，求破坏度最低的接缝并分析效率（$O(mn)$ DP：$D[i,j] = d[i,j] + \min(D[i-1,j-1], D[i-1,j], D[i-1,j+1])$）。
15-9 拆分字符串：拆分 $n$ 个字符的串需复制，代价 $n$。例：20 字符串在第 2、8、10 个字符后拆分：从左到右代价 $20+18+12 = 50$；从右到左 $20+10+8 = 38$；先在 8 处（20），再左段在 2 处（8），再右段在 10 处（12），共 40。给定拆分点数组 $L[1..m]$，求最低代价拆分顺序及其代价（区间 DP，类似矩阵链，$O(m^3)$）。
15-10 投资策略规划：获得 10000 美元签约奖金，目标是 10 年后收益最大。有 $n$ 种投资，第 $j$ 年投资 $i$ 的回报率 $r_{ij}$（投入 $d$ 美元年末得 $dr_{ij}$），未来 10 年所有回报率已知。每年末决策一次：资金不变动需付费 $f_1$，转移资金需付费 $f_2$（$f_2 > f_1$）。(a) 证明存在每年把全部资金投入单一投资的最优策略（最优只看 10 年后金额，不考虑风险等其他目标）；(b) 证明具有最优子结构；(c) 设计算法并给出运行时间（$O(n^2 \cdot 10)$ 级 DP，状态为"第 $j$ 年持有投资 $i$"）；(d) 若规定任何时刻单一投资不得超过 15000 美元，证明不再具有最优子结构。
15-11 库存规划：Rinky Dink 公司生产冰场修面机，未来 $n$ 个月每月需求 $d_i$ 已知，总需求 $D = \sum d_i$。全职员工每月最多生产 $m$ 台；超出部分雇兼职，每台额外成本 $c$。月末持有 $j$ 台未售机器的库存成本为 $h(j)$（$h(j)\ge0$，且非减）。给出满足全部需求、成本最小的生产计划，时间为 $n$ 与 $D$ 的多项式（状态：月份 × 月末库存量，$O(nD^2)$）。
15-12 签约自由球员：棒球队经理，预算 $X$ 美元；考虑 $N$ 个位置，每个位置有 $P$ 个自由球员可选，每个位置至多签一人（不签则沿用现有球员）。用 VORP（value over replacement player，"超越替补球员价值"，一种棒球统计学 sabermetrics 指标）衡量价值，VORP 高不一定更贵。每个球员已知位置、签约费用（100000 美元的倍数）和 VORP。设计算法在总花费不超过 $X$ 的前提下最大化签约球员的 VORP 总和，输出总 VORP、总花费和签约名单，分析时间空间（分组背包 DP，$O(NPX/10^5)$）。

章末注记

R. Bellman 1955 年开始系统研究动态规划；这里和线性规划中的 "programming" 都指表格化求解方法；之前已有含动态规划成分的优化技术，但 Bellman 为该领域奠定了坚实数学基础。Galil 与 Park 按表大小与每个表项依赖的其他表项数分类：表大小 $O(n^t)$、每项依赖 $O(n^e)$ 个其他项的称为 $tD/eD$ 算法，例如矩阵链乘法是 2D/1D，LCS 是 2D/0D。Hu 与 Shing 给出矩阵链乘法的 $O(n\lg n)$ 算法。$O(mn)$ 的 LCS 算法似乎是"民间算法"；Knuth 问是否存在次二次算法，Masek 与 Paterson 给出 $O(mn/\lg n)$ 算法（$n\le m$ 且字符集有界）；输入序列中无重复元素时 Szymanski 给出 $O((n+m)\lg(n+m))$ 算法；许多结果可推广到编辑距离。Gilbert 与 Moore 关于变长二进制编码的早期论文涉及所有 $p_i = 0$ 时的最优 BST，给出 $O(n^3)$ 算法；Aho–Hopcroft–Ullman 给出 15.5 节的算法；习题 15.5-4 归功于 Knuth；Hu 与 Tucker 对所有 $p_i = 0$ 的情形给出 $O(n^2)$ 时间、$O(n)$ 空间算法，Knuth 后将时间降到 $O(n\lg n)$。思考题 15-8 归功于 Avidan 与 Shamir。

第 15 章本章要点

动态规划四步：刻画最优解结构、递归定义最优值、（通常自底向上）计算最优值、由记录的选择构造最优解。
两个要素：最优子结构（用剪切—粘贴证明；子问题须独立）与重叠子问题（不同子问题数为多项式）。最长简单路径是没有最优子结构的反例（子问题争用顶点资源）。
实现方式：带备忘的自顶向下 vs 自底向上，渐近相同；自底向上常数更小且便于优化空间，备忘只求解必要的子问题。
运行时间 ≈ 子问题数 × 每个子问题的选择数，也可由子问题图的顶点与边数估计。
典型问题与复杂度：钢条切割 $\Theta(n^2)$；矩阵链乘法 $\Theta(n^3)$ 时间、$\Theta(n^2)$ 空间；LCS $\Theta(mn)$（只求长度可降到 $O(\min(m,n))$ 空间）；最优 BST $\Theta(n^3)$（Knuth 优化 $\Theta(n^2)$）。

第 15 章与量化交易的关联

最优执行与交易调度：在离散时间上拆单（Almgren–Chriss 类模型的离散化）、在给定冲击成本与风险惩罚下决定每期交易量，本质是"状态 = 剩余仓位 × 时间"的动态规划，结构与钢条切割/库存规划（思考题 15-11）相同；带固定交易成本的调仓（习题 15.1-3 的"每次切割固定成本"）对应含固定费用的再平衡决策。
带交易成本的多期组合/择时：思考题 15-10 的投资策略规划就是"不换仓付 $f_1$、换仓付 $f_2$"的多期切换问题，DP 状态为"第 $j$ 年持有资产 $i$"；它的 (d) 部分说明一旦加入持仓上限，最优子结构可能失效——提示实际组合优化中约束会破坏简单 DP，需要改用数学规划。习题 15.3-6 的货币兑换与三角套利检测（对数汇率上的最短/最长路径）直接相关。
隐马尔可夫模型与市场状态识别：思考题 15-7 的 Viterbi 算法是 HMM 状态解码的标准算法，用于牛熊/波动率体制（regime）识别；同类动态规划还用于变点检测（最优分段，与整齐打印 15-4 的分段代价结构相同）。
序列比对与模式匹配：LCS/编辑距离/动态时间规整（DTW，与编辑距离同构）用于价格形态相似度匹配、交易信号序列对齐；最长递增子序列（习题 15.4-5/6）可用于趋势持续性统计。
期权定价：二叉树/三叉树上美式期权的倒推定价是自底向上动态规划（每个结点取"持有价值"与"行权价值"的最大值），是本章思想在定价中最直接的应用。
计算优化：矩阵链乘法的括号化在风险模型中（如 $w^\top B F B^\top w$ 的计算顺序、因子协方差的低秩乘积）决定计算量——先算 $B^\top w$ 再乘比先算 $BFB^\top$ 便宜得多，这正是 15.2 节的思想；备忘化/缓存是因子计算框架的基本优化手段。

第 15 章推荐习题

15.1-3：带固定切割成本的钢条切割（对应带固定交易成本的决策）。
15.2-1 与 15.2-5：矩阵链手算与 $\Theta(n^3)$ 的精确计数。
15.3-5、15.3-6：最优子结构何时失效；15.3-6 的货币兑换与套利直接相关。
15.4-4、15.4-6：LCS 的空间优化与 $O(n\lg n)$ 的 LIS。
15.5-4：Knuth 优化（四边形不等式类技巧）。
思考题 15-5（编辑距离/序列比对）、15-7（Viterbi）、15-10（投资策略）、15-11（库存规划）：与量化建模最相关的四道。

第 16 章贪心算法（Greedy Algorithms）（PDF p.435–449；续见下一块）

求解最优化问题的算法通常经过一系列步骤，每步面临一组选择。对许多最优化问题，用动态规划确定最佳选择是"杀鸡用牛刀"，更简单高效的算法就够了。贪心算法（greedy algorithm）总是做出当前看来最好的选择，即做出局部最优选择，寄希望于它导致全局最优解。贪心算法不总能得到最优解，但对许多问题可以。阅读本章前应先读第 15 章，特别是 15.3 节。

本章安排：16.1 活动选择问题——先考虑动态规划解法，再证明总可以做贪心选择得到最优解；16.2 贪心方法的基本要素，给出证明贪心算法正确性的直接方法；16.3 贪心技术的重要应用——设计数据压缩（赫夫曼，Huffman）编码；16.4 称为**拟阵（matroid）**的组合结构的理论，对拟阵贪心算法总能得到最优解；16.5 用拟阵解决带截止时间和惩罚的单位时间任务调度问题。后面许多算法可看作贪心方法的应用：最小生成树（第 23 章，贪心的经典例子，可与本章一起读）、单源最短路径的 Dijkstra 算法（第 24 章）、Chvátal 的贪心集合覆盖启发式算法（第 35 章）。

16.1 活动选择问题（An activity-selection problem）（PDF p.436–443）

问题：若干竞争的活动需要独占使用某个公共资源，目标是选出最大的互相兼容的活动集合。设 $S = \{a_1, \dots, a_n\}$ 为 $n$ 个活动，资源（如一个阶梯教室）同一时刻只能供一个活动使用。活动 $a_i$ 有开始时间 $s_i$ 和结束时间 $f_i$，$0\le s_i < f_i < \infty$，若被选中则占用半开区间 $[s_i, f_i)$。若 $[s_i,f_i)$ 与 $[s_j,f_j)$ 不重叠，即 $s_i \ge f_j$ 或 $s_j \ge f_i$，则称 $a_i$ 与 $a_j$ 兼容（compatible）。活动选择问题：选出最大规模的互相兼容活动子集。假设活动已按结束时间单调递增排序：

f_1 \le f_2 \le f_3 \le \dots \le f_{n-1} \le f_n. \tag{16.1}

例：

$i$	1	2	3	4	5	6	7	8	9	10	11
$s_i$	1	3	0	5	3	5	6	8	8	2	12
$f_i$	4	5	6	7	9	9	10	11	12	14	16

$\{a_3, a_9, a_{11}\}$ 互相兼容但不是最大的；$\{a_1, a_4, a_8, a_{11}\}$ 是最大兼容子集之一，$\{a_2, a_4, a_9, a_{11}\}$ 也是。

本节步骤比通常开发贪心算法更繁琐，但能展示贪心与动态规划的关系：先考虑动态规划解法（要考虑多种选择），然后观察到只需考虑一种选择——贪心选择——且做出贪心选择后只剩一个子问题；据此得到递归贪心算法，再转为迭代算法。

活动选择问题的最优子结构

令 $S_{ij}$ 为在 $a_i$ 结束之后开始、在 $a_j$ 开始之前结束的活动集合。设 $A_{ij}$ 是 $S_{ij}$ 的一个最大兼容活动子集，包含某活动 $a_k$。包含 $a_k$ 后剩下两个子问题：$S_{ik}$（在 $a_i$ 结束后开始、$a_k$ 开始前结束）和 $S_{kj}$。令 $A_{ik} = A_{ij}\cap S_{ik}$，$A_{kj} = A_{ij}\cap S_{kj}$，则 $A_{ij} = A_{ik}\cup\{a_k\}\cup A_{kj}$，$|A_{ij}| = |A_{ik}| + |A_{kj}| + 1$。剪切—粘贴：若 $S_{kj}$ 中有更大的兼容集 $A'_{kj}$（$|A'_{kj}| > |A_{kj}|$），用它代替 $A_{kj}$ 就得到 $|A_{ik}| + |A'_{kj}| + 1 > |A_{ij}|$ 个兼容活动，矛盾；$S_{ik}$ 对称。于是可用动态规划，令 $c[i,j]$ 为 $S_{ij}$ 最优解的规模：

c[i,j] = \begin{cases}0 & S_{ij} = \emptyset,\\ \max_{a_k\in S_{ij}}\{c[i,k] + c[k,j] + 1\} & S_{ij}\ne\emptyset.\end{cases} \tag{16.2}

可以递归加备忘或自底向上填表，但这样会忽视该问题另一个可以大加利用的重要性质。

贪心选择

能否不先求解所有子问题就选出一个加入最优解的活动？直觉：应选一个让资源尽量多地留给其他活动的活动。最终选中的活动中必有一个最先结束，所以应选 $S$ 中最早结束的活动（若多个并列可任选），这能让资源尽可能多地留给后面的活动。由于活动已按结束时间排序，贪心选择就是 $a_1$。（"选最早结束的"不是唯一的贪心思路，习题 16.1-3 探讨其他选择。）

做出贪心选择后只剩一个子问题：找在 $a_1$ 结束后开始的活动。无需考虑在 $a_1$ 开始前结束的活动：因为 $s_1 < f_1$ 且 $f_1$ 是最早结束时间，没有活动的结束时间 $\le s_1$，所以与 $a_1$ 兼容的活动都必须在 $a_1$ 结束后开始。令 $S_k = \{a_i\in S : s_i \ge f_k\}$ 为在 $a_k$ 结束后开始的活动集合。选了 $a_1$ 后，$S_1$ 是唯一要解的子问题（脚注：有时把 $S_k$ 称为子问题而不仅是活动集合）。由最优子结构，若 $a_1$ 在最优解中，则原问题最优解由 $a_1$ 和子问题 $S_1$ 最优解中的所有活动组成。

定理 16.1：考虑任意非空子问题 $S_k$，令 $a_m$ 是 $S_k$ 中结束时间最早的活动，则 $a_m$ 在 $S_k$ 的某个最大兼容活动子集中。证明（交换论证）：令 $A_k$ 是 $S_k$ 的一个最大兼容活动子集，$a_j$ 是 $A_k$ 中结束最早的活动。若 $a_j = a_m$，得证。若 $a_j \ne a_m$，令 $A'_k = A_k - \{a_j\}\cup\{a_m\}$，即用 $a_m$ 替换 $a_j$。$A'_k$ 中活动不相交：$A_k$ 中活动不相交，$a_j$ 是 $A_k$ 中第一个结束的，且 $f_m \le f_j$。$|A'_k| = |A_k|$，所以 $A'_k$ 也是最大兼容子集且包含 $a_m$。

因此虽然可以用动态规划，但没有必要（况且还没检验它是否有重叠子问题）。可以反复选择最早结束的活动，只保留与之兼容的活动，重复直到没有活动剩下。由于总选最早结束的活动，选中活动的结束时间严格递增，只需按结束时间单调递增顺序把每个活动考察一次。贪心算法不必像基于表格的动态规划那样自底向上，而可以自顶向下：先做一个选择放入最优解，再求解剩下的子问题（与已选活动兼容的活动中再选择）。贪心算法通常都是这种自顶向下设计：先做选择再解子问题，而不是先解子问题再做选择。

递归贪心算法

输入为开始、结束时间数组 $s$、$f$（脚注：作为数组用方括号下标），定义子问题 $S_k$ 的下标 $k$，以及原问题规模 $n$；返回 $S_k$ 的最大兼容活动集。假设活动已按式 16.1 排序，否则可 $O(n\lg n)$ 排序（并列任意打破）。添加虚拟活动 $a_0$，$f_0 = 0$，使 $S_0 = S$。初始调用 RECURSIVE-ACTIVITY-SELECTOR(s, f, 0, n)。

def RECURSIVE_ACTIVITY_SELECTOR(s, f, k, n):
    m = k + 1
    while m <= n and s[m] < f[k]:      # 找 S_k 中第一个结束的活动
        m = m + 1
    if m <= n:
        return {a[m]} | RECURSIVE_ACTIVITY_SELECTOR(s, f, m, n)
    return set()

while 循环依次检查 $a_{k+1}, a_{k+2}, \dots, a_n$，直到找到第一个与 $a_k$ 兼容的活动 $a_m$（$s_m \ge f_k$），返回 $\{a_m\}$ 与递归调用返回的 $S_m$ 最大子集的并；若 $m>n$，说明 $S_k$ 中没有与 $a_k$ 兼容的活动，$S_k = \emptyset$，返回空集。时间：假设已按结束时间排序，RECURSIVE-ACTIVITY-SELECTOR(s,f,0,n) 为 $\Theta(n)$：在所有递归调用中，每个活动恰好在第 2 行 while 测试中被检查一次（活动 $a_i$ 在最后一次满足 $k<i$ 的调用中被检查）。 图 16.1：在上例 11 个活动上，调用依次选中 $a_1$（$m=1$）、$a_4$（$m=4$）、$a_8$（$m=8$）、$a_{11}$（$m=11$），最后的调用 (s,f,11,11) 返回空集；开始时间早于最近加入活动结束时间的活动被拒绝。结果 $\{a_1,a_4,a_8,a_{11}\}$。

迭代贪心算法

RECURSIVE-ACTIVITY-SELECTOR 几乎是"尾递归"的（以对自身的递归调用加一次并操作结束，见思考题 7-4），转换为迭代形式通常很直接（有些编译器能自动完成）。

def GREEDY_ACTIVITY_SELECTOR(s, f):
    n = len(s)
    A = {a[1]}
    k = 1                          # k 指向最近加入 A 的活动
    for m in range(2, n + 1):
        if s[m] >= f[k]:           # 与 A 中所有活动兼容
            A = A | {a[m]}
            k = m
    return A
# 已排序时 Θ(n)；若需排序则 O(n lg n)

由于按结束时间递增考察，$f_k$ 总是 $A$ 中所有活动的最大结束时间：

f_k = \max\{f_i : a_i\in A\}. \tag{16.3}

所以判断 $a_m$ 是否与 $A$ 中所有活动兼容，只需检查 $s_m \ge f_k$。返回的 $A$ 与 RECURSIVE-ACTIVITY-SELECTOR(s,f,0,n) 返回的集合完全相同。

习题 16.1 概括：16.1-1 基于式 16.2 写动态规划算法求 $c[i,j]$ 并输出最大兼容子集，与贪心比较运行时间（DP 为 $O(n^3)$）；16.1-2 改为每次选择与已选活动兼容的最晚开始的活动，说明这也是贪心并证明最优（对称）；16.1-3 举反例说明以下贪心不行：选持续时间最短的、选与其余活动重叠最少的、选开始最早的；16.1-4 用尽量少的教室安排所有活动（**区间图着色（interval-graph coloring）**问题：顶点为活动，边连接不兼容的活动，最少颜色数即所需最少教室数），给出高效贪心算法（按开始时间扫描，用优先队列复用最早空出的教室）；16.1-5 每个活动有价值 $v_i$，目标改为最大化所选兼容活动的总价值，给出多项式算法（加权区间调度，DP + 二分查找，$O(n\lg n)$）。

16.2 贪心策略的要素（Elements of the greedy strategy）（PDF p.444–449）

贪心算法通过做一系列选择求最优解，每个决策点做当时看来最佳的选择。这种启发式策略不总能得到最优解，但有时可以。

16.1 节开发贪心算法的过程比通常更繁琐：

确定问题的最优子结构；
设计递归解（活动选择问题中写出了式 16.2，但跳过了基于它的递归算法）；
证明做出贪心选择后只剩一个子问题；
证明贪心选择总是安全的（3、4 顺序可互换）；
设计实现贪心策略的递归算法；
把递归算法转为迭代算法。

这一过程详细展示了贪心算法背后的动态规划基础：先定义 $i$、$j$ 都变化的子问题 $S_{ij}$，再发现总做贪心选择时可以把子问题限制为 $S_k$ 的形式。也可以一开始就针对贪心选择设计最优子结构，使选择后只剩一个子问题——直接去掉第二个下标，定义 $S_k$ 形式的子问题，再证明贪心选择（$S_k$ 中最早结束的 $a_m$）与剩余兼容活动集 $S_m$ 的最优解合并，就得到 $S_k$ 的最优解。

更一般的贪心算法设计步骤：

把最优化问题转化为这样的形式：做出一个选择后只剩一个子问题需要求解。
证明原问题总存在一个包含贪心选择的最优解，即贪心选择总是安全的。
证明最优子结构：做出贪心选择后，剩下的子问题满足——其最优解与已做的贪心选择组合，即得原问题的最优解。

本章后面使用这一更直接的过程。不过每个贪心算法背后几乎总有一个更繁琐的动态规划解。

如何判断贪心算法能否解决某个最优化问题？没有万能方法，但贪心选择性质与最优子结构是两个关键要素；能证明问题具有这两个性质，就基本可以开发贪心算法。

贪心选择性质（greedy-choice property）

可以通过做局部最优（贪心）选择来构造全局最优解。也就是说，在考虑做哪个选择时，只选在当前问题中看来最优的，不考虑子问题的解。这是贪心与动态规划的不同之处：动态规划每步也做选择，但选择通常依赖子问题的解，因此通常自底向上求解，从小子问题到大子问题（也可自顶向下加备忘，但即使代码自顶向下，仍需先解子问题再做选择）。贪心算法做出当前最佳选择然后求解剩下的子问题；其选择可以依赖于之前的选择，但不能依赖于将来的选择或子问题的解。动态规划先求解子问题再做第一次选择；贪心算法在求解任何子问题之前做第一次选择。动态规划自底向上，贪心通常自顶向下，一次又一次做贪心选择，把问题实例逐步化简为更小的实例。

必须证明每步的贪心选择能得到全局最优解。通常如定理 16.1 那样：考察某子问题的一个全局最优解，说明如何修改它，用贪心选择替换另一个选择，得到一个相似但更小的子问题。

贪心选择通常比考虑更广泛的选择集合更高效。例如活动选择问题中，若活动已按结束时间排序，每个活动只需考察一次。通过预处理输入或使用合适的数据结构（通常是优先队列），常能快速做出贪心选择，从而得到高效算法。

最优子结构

问题的最优解包含其子问题的最优解。这是判断能否用动态规划和贪心的关键要素。在 16.1 节中，若子问题 $S_{ij}$ 的最优解包含 $a_k$，它必然包含 $S_{ik}$ 和 $S_{kj}$ 的最优解，据此得到式 16.2。用于贪心算法时通常更直接：可以假定是通过在原问题中做出贪心选择而得到子问题的，只需论证子问题的最优解与已做的贪心选择组合起来就是原问题的最优解。这一方案隐含地对子问题做归纳，证明每步做贪心选择会得到最优解。

贪心 vs 动态规划：两种背包问题

由于两者都利用最优子结构，容易在贪心足够时用动态规划，或者在需要动态规划时误以为贪心可行。

0-1 背包问题（0-1 knapsack problem）：小偷在商店发现 $n$ 件商品，第 $i$ 件价值 $v_i$ 美元、重 $w_i$ 磅（$v_i$、$w_i$ 为整数），背包最多装 $W$ 磅（整数），要拿走价值尽量高的商品。每件商品要么全拿要么不拿，不能拿一部分或多次拿（像金锭）。
分数背包问题（fractional knapsack problem）：设定相同，但可以拿商品的一部分（像金粉）。

两者都有最优子结构：0-1 问题中，若从重量至多 $W$ 的最有价值装载中拿走商品 $j$，剩下的必须是从除 $j$ 以外 $n-1$ 件商品中选取、重量至多 $W - w_j$ 的最有价值装载；分数问题中，若从最优装载中拿走商品 $j$ 的重量 $w$，剩下的必须是从 $n-1$ 件原商品加上 $w_j - w$ 磅商品 $j$ 中选取、重量至多 $W-w$ 的最有价值装载。

分数背包可贪心：计算每件商品每磅价值 $v_i/w_i$，先尽量多拿每磅价值最高的，拿完还能装就拿次高的，直到达到 $W$。按每磅价值排序后，贪心算法 $O(n\lg n)$。贪心选择性质的证明留作习题 16.2-1。

0-1 背包不能贪心（图 16.2）：背包容量 50 磅；商品 1 重 10 磅价值 60 美元（6 美元/磅），商品 2 重 20 磅价值 100 美元（5 美元/磅），商品 3 重 30 磅价值 120 美元（4 美元/磅）。贪心先拿商品 1，但最优解拿商品 2 和 3（220 美元）；含商品 1 的两种方案 $60+100 = 160$、$60+120 = 180$ 都次优。分数问题中贪心先拿商品 1，再拿商品 2，再拿 20 磅商品 3（价值 80），共 240 美元，是最优的。0-1 问题中拿商品 1 不行的原因：小偷无法把背包装满，空余空间降低了装载的有效每磅价值。在 0-1 问题中决定是否装入某商品时，必须比较包含该商品的子问题的解与不包含该商品的子问题的解，才能做出选择——这样表述的问题会产生许多重叠子问题，这正是动态规划的标志；事实上可以用动态规划求解 0-1 背包（习题 16.2-2，$O(nW)$）。

习题 16.2 概括：16.2-1 证明分数背包具有贪心选择性质；16.2-2 $O(nW)$ 的 0-1 背包动态规划；16.2-3 若按重量递增排序的顺序与按价值递减排序的顺序相同，给出高效最优算法（按重量从轻到重贪心装）；16.2-4 Gekko 教授沿 U.S. 2 号公路滑轮滑横穿北达科他州，带 2 升水能滑 $m$ 英里，地图标出所有补水点及间距，求最少补水次数并证明最优（贪心：在水用完前尽量走到最远的补水点），给出运行时间 $O(n)$；16.2-5 给定实轴上点集 $\{x_1..x_n\}$，求覆盖所有点的最少单位长度闭区间集合（排序后从最左未覆盖点开始放区间）；16.2-6（星号）$O(n)$ 求解分数背包（用线性时间选择找带权中位数）；16.2-7 两个各含 $n$ 个正整数的集合 $A$、$B$ 任意重排后得到收益 $\prod_{i=1}^n a_i^{b_i}$，求最大化收益的算法并证明（两者同序排序，排序不等式）。

16.3 赫夫曼编码（Huffman codes）（PDF p.449；续见下一块）

赫夫曼编码能非常有效地压缩数据，视数据特征通常可节省 20% 到 90% 的空间。把数据看作字符序列，赫夫曼贪心算法利用每个字符出现频率的表，构造用二进制串表示每个字符的最优方式。例：一个 100000 字符的数据文件，只出现 6 种不同字符，频率见图 16.3（字符 a 出现 45000 次）。要设计二进制字符编码（binary character code）（简称编码）……（本块在此结束，16.3 节正文续见下一块。）

第 16 章（本块已覆盖部分）小结

贪心算法每步做局部最优选择；正确性依赖贪心选择性质（用交换论证证明存在包含贪心选择的最优解）与最优子结构。
活动选择：按结束时间排序后选最早结束且兼容的活动，$\Theta(n)$（排序 $O(n\lg n)$）。
贪心与动态规划的界线：分数背包可贪心 $O(n\lg n)$，0-1 背包需动态规划 $O(nW)$（伪多项式）。
本章要点、与量化交易的关联、推荐习题的完整版本应在下一块（16.3 节之后）给出；就已覆盖部分而言：活动选择/区间调度对应交易时段与资源（如单一通道、风控额度）的分配；分数背包对应在资金约束下按"单位资金预期收益"排序配置可分割头寸，而 0-1 背包对应不可分割的离散决策（如整手、项目或策略的取舍），在头寸规模受最小交易单位限制时贪心可能失效；习题 16.2-7 的排序不等式在因子权重与信号强度配对时有直接对应。推荐习题：16.1-3（贪心反例）、16.1-4（区间图着色）、16.1-5（加权区间调度）、16.2-2（0-1 背包 DP）、16.2-4（加油/补水站贪心）、16.2-7（排序不等式）。

操作	类型	含义
`SEARCH(S, k)`	查询	返回指向 \(x.key = k\) 的元素的指针 \(x\)，若不存在返回 NIL
`INSERT(S, x)`	修改	把 \(x\) 指向的元素加入 \(S\)（假定 \(x\) 中集合实现需要的属性已初始化）
`DELETE(S, x)`	修改	给定指向元素 \(x\) 的指针（不是关键字值），从 \(S\) 中删除 \(x\)
`MINIMUM(S)` / `MAXIMUM(S)`	查询	在全序集上返回关键字最小/最大元素的指针
`SUCCESSOR(S, x)`	查询	返回下一个更大元素的指针；\(x\) 为最大元素时返回 NIL
`PREDECESSOR(S, x)`	查询	返回下一个更小元素的指针；\(x\) 为最小元素时返回 NIL

\(i\)	0	1	2	3	4	5	6	7	8	9	10
\(r[i]\)	0	1	5	8	10	13	17	18	22	25	30
\(s[i]\)	0	1	2	3	2	2	6	1	2	3	10

\(i\)	1	2	3	4	5	6	7	8	9	10	11
\(s_i\)	1	3	0	5	3	5	6	8	8	2	12
\(f_i\)	4	5	6	7	9	9	10	11	12	14	16

Part III 数据结构（Data Structures）（PDF p.249–252）

导言：动态集合

动态集合上的典型操作

Part III 概览

第 10 章 基本数据结构（Elementary Data Structures）（PDF p.253–273）

10.1 栈和队列（Stacks and queues）（PDF p.253–257）

栈的数组实现

队列的数组实现（循环数组）

习题 10.1 概括

10.2 链表（Linked lists）（PDF p.257–262）

搜索、插入、删除

哨兵（sentinel）

习题 10.2 概括

10.3 指针和对象的实现（Implementing pointers and objects）（PDF p.262–266）

多数组表示（multiple-array representation）

单数组表示（single-array representation）

对象的分配与释放（Allocating and freeing objects）

习题 10.3 概括

10.4 有根树的表示（Representing rooted trees）（PDF p.267–270）

习题 10.4 概括

第 10 章思考题（PDF p.270–273）

章末注记（Chapter notes）

第 10 章本章要点

第 10 章与量化交易的关联

第 10 章推荐习题

第 11 章 散列表（Hash Tables）（PDF p.274–306）

11.1 直接寻址表（Direct-address tables）（PDF p.275–276）

11.2 散列表（Hash tables）（PDF p.277–282）

链接法（chaining）

链接法的分析

11.3 散列函数（Hash functions）（PDF p.283–290）

什么是好的散列函数

11.3.1 除法散列

11.3.2 乘法散列

11.3.3 全域散列（Universal hashing，星号节）

11.4 开放寻址法（Open addressing）（PDF p.290–298）

线性探查（linear probing）

二次探查（quadratic probing）

双重散列（double hashing）

开放寻址的分析

11.5 完全散列（Perfect hashing，星号节）（PDF p.298–303）

第 11 章思考题（PDF p.303–305）

章末注记

第 11 章本章要点

第 11 章与量化交易的关联

第 11 章推荐习题

第 12 章 二叉搜索树（Binary Search Trees）（PDF p.307–328）

12.1 什么是二叉搜索树（PDF p.307–310）

12.2 查询二叉搜索树（PDF p.310–315）

12.3 插入和删除（PDF p.315–320）

12.4 随机构造的二叉搜索树（Randomly built BST，星号节）（PDF p.320–324）

第 12 章思考题（PDF p.324–328）

章末注记

第 12 章本章要点

第 12 章与量化交易的关联

第 12 章推荐习题

第 13 章 红黑树（Red-Black Trees）（PDF p.329–359）

13.1 红黑树的性质（Properties of red-black trees）（PDF p.329–333）

13.2 旋转（Rotations）（PDF p.333–335）

13.3 插入（Insertion）（PDF p.336–343）

13.4 删除（Deletion）（PDF p.344–351）

第 13 章思考题（PDF p.352–358）

章末注记

第 13 章本章要点

第 13 章与量化交易的关联

第 13 章推荐习题

第 14 章 数据结构的扩张（Augmenting Data Structures）（PDF p.360–376）

14.1 动态顺序统计（Dynamic order statistics）（PDF p.360–366）

14.2 如何扩张数据结构（How to augment a data structure）（PDF p.366–369）

14.3 区间树（Interval trees）（PDF p.369–376）

第 14 章思考题（PDF p.374–376）

章末注记

第 14 章本章要点

第 14 章与量化交易的关联

第 14 章推荐习题

Part IV 高级设计和分析技术（Advanced Design and Analysis Techniques）（PDF p.377–379）

第 15 章 动态规划（Dynamic Programming）（PDF p.380–434）

15.1 钢条切割（Rod cutting）（PDF p.380–391）

子问题图（subproblem graph）

重构解

第 10 章基本数据结构（Elementary Data Structures）（PDF p.253–273）

第 11 章散列表（Hash Tables）（PDF p.274–306）

第 12 章二叉搜索树（Binary Search Trees）（PDF p.307–328）

第 13 章红黑树（Red-Black Trees）（PDF p.329–359）

第 14 章数据结构的扩张（Augmenting Data Structures）（PDF p.360–376）

第 15 章动态规划（Dynamic Programming）（PDF p.380–434）

第 16 章贪心算法（Greedy Algorithms）（PDF p.435–449；续见下一块）