第 13 章树与森林 — 多叉、遍历与 B 树家族¶

这一章讲什么: 放开「二叉」限制后,树怎么表示、怎么遍历, 以及为了磁盘访问而设计的多路平衡树(B 树)和它的二叉化身(红黑树)。它在全书链条里的位置:第 12 章是「形状对抗」;本章转向「宽度换高度」—— 节点多装键、树变矮,访问次数变少;第 15 章的二项堆、斐波那契堆会直接复用「森林 + 左孩子右兄弟」表示。

1. 顶层全景¶

  一般树:节点可有任意多个孩子
      │
      ├─ 表示①:每节点挂一个 children 数组(类/DOM 风格,addChild/removeChild)
      ├─ 表示②:左孩子右兄弟——left 指第一个孩子,right 指下一个兄弟
      │          (二叉树算法原样复用!第 15 章二项/斐波那契 heaps 的底层)
      ├─ 森林:根的数组;或让所有根互为兄弟(一根指针摸到所有树)
      │
      ├─ 遍历:前序/后序(中序无对应);深搜=递归(或栈);广搜=队列(逐层)
      │
      └─ B 树(阶 m):多路有序;每节点 ≤m−1 键、m 个孩子;非根至少半满;叶同层
           查找:节点内定位 + 走对应指针(节点内二分可加速)
           插入:节点满则中键上提、分裂两半 —— 树长高只发生在根分裂
           删除:借(兄弟富余)或并(兄弟刚好半满),根空则缩矮
           红黑树 = 2-3 树的二叉表示(Sedgewick 左倾版):
             3-节点 = 黑父+左倾红子;红不连红;黑平衡(各路径黑数相同)

  图说:上半章是「表示与遍历」,下半章是「为磁盘而生的矮胖树」。

2. 主线例子:一棵一般树的两种长相与两次遍历¶

原书图 13-1 的树:根 A,孩子 B、C、D;B 有孩子 E、F;C 有孩子 G。

表示①(孩子数组):每个节点 {key, _children: []}; addChild(key, i) 在兄弟中第 i 位插新树(splice), removeChild(i) 摘第 i 棵——都是数组操作,O(兄弟数)¹。

表示②(左孩子右兄弟):A.left = B;B.right = C;C.right = D; B.left = E;E.right = F。六根指针画出一棵树,而算法全是第 12 章的二叉树算法—— 这是该表示的真正价值:一般树的问题二叉化²。

遍历对比:同一棵树,深度优先访问序 A B E F C G D(钻进一支再回头); 广度先进一个队列:出 A、入 B C D;出 B、入 E F;出 C、入 G……访问序 A B C D E F G——一层扫完再下一层³。书上给了一个漂亮的对称:深搜免递归用栈(习题 13.3:孩子逆序压栈, 左孩子先弹出),广搜天然用队列——「树的非递归遍历:深搜配栈、广搜配队列」⁴。

3. 核心原理¶

3.1 B 树的五条军规¶

B 树(1972,Bayer 与 McCreight;"B" 何意无定论⁵)阶 m 的定义:

每节点至多 m−1 个升序键、至多 m 个孩子;
除根外每节点至少 ⌈m/2⌉ 个孩子(至少半满);
根至少一个键;
所有叶同层;
键的左右分治:BST 性质推广——某键左侧子树全小于它、右侧全大于它⁶。

设计动机:节点对应一次磁盘块读取;阶数取大运算放大—— 「更大的 m = 更矮的树 = 更少的磁盘访问」。代价是节点内的键多了, 查找要在节点内做(线性定位起步,习题 13.7 提二分加速)⁷。

3.2 分裂与合并:不变式的维护术¶

插入:走到该去的叶节点,有空位直接放;满了就分裂——中键上提到父节点, 左右两半各成新节点;父节点因此多一个键,可能连锁分裂; 只有根分裂时树才长高一层(新根一个键,两旧根为孩子)⁸。

删除(下详版逻辑):非叶键用后继(右子树最左键)顶替,问题归结为叶删除; 叶删后若「太瘦」(< ⌈m/2⌉−1 键),先向兄弟借(兄弟富余:父键下沉、兄弟键上提),兄弟刚好半满则合并(父键下沉与兄弟并成一节点)—— 连锁向上;根空了树就缩矮。_tooBig/_tooSmall 两个预判函数让递归回程统一处理这两种修复⁹。性能:查找、增删全 O(log n)(准确说是 O(log_m n) 层 × 节点内成本)¹⁰。

3.3 红黑树 = 2-3 树的二进制¶

B 树好用但难实现。左倾红黑树(Sedgewick 版)给出等价表示: 把 2-3 树的每个 3-节点画成「黑父 + 红色左孩子」的二叉对。规则随之而来:红节点只在左(左倾)、红不连红、根黑、空树算黑; 等价的 B 树表述是「黑平衡」——根到叶的每条路径黑节点数相同¹¹。

插入因此变成翻译过的 B 树分裂:新节点先着红(不影响黑平衡), 回溯时用三种修复消掉违规—— (a) 2-节点加左红孩子:正好构成 3-节点,无事; (b) 右红孩子:左旋让它左倾; (c) 两个红连着(临时 4-节点):相当于 B 树节点溢出,颜色翻转把它「分裂」成两个 2-节点、红键上送,再递归向上处理¹²。搜索代码与 BST 一字不改。红黑树用在 Linux 内核的目录项、虚拟内存、调度器等处——「B 树的工程化身」¹³。

3.4 习题的三个巧思¶

树相等:不做递归比较,JSON.stringify 两棵树直接对拍¹⁴;
非递归深搜:栈 + 逆序压孩子(否则访问顺序不对,且 reverse() 会改原数组, 用解构复制)⁴;
B 树最低阶:阶 2 退化成「每个节点至多 1 键」,几乎无用,阶 3(2-3 树)才是有意义的起点¹⁵。

4. 作者的判断与证据¶

「宽度换高度」是 B 树的全部动机,书里直接绑定磁盘块: 大阶数 → 矮树 → 少访问;这是从「比较次数」到「I/O 次数」的度量转换⁶。
红黑树按「2-3 树等价物」教而非按经典五性质教——Sedgewick 路线, 实现更短,且「插入修复 = B 树分裂的着色翻译」这个解释贯穿全节¹²。
局限都说在明处:B 树各来源定义不一(本书给了明确口径); 红黑树「B 树出身带来的黑平衡性质」被点出但证明略去¹¹。

判断(我们的,不是书里的): 本章是把第 12 章「形状焦虑」换个维度解决:第 12 章在二叉范围内对抗失衡,本章用多叉让失衡在数学上更难发生(半满规则 + 叶同层 ⇒ 高度自动 O(log n), 无需 AVL 式记账)。红黑树则是工程上的折中宣言: 用「颜色 + 三条局部规则」模拟 B 树的全局不变式,换来短得多的代码 ——数据结构史上「表示法选择」决定实现复杂度的一课。 如果错,会错在: 「多叉让失衡更难发生」的表述对内存场景未必成立 (节点内线性扫描在缓存里反而是优势),该论证只对磁盘 I/O 严格成立—— 书里语境是磁盘,我们把它推广时要带上这个前提。

5. 边界与局限¶

红黑树的完整删除实现被略去大半:修复分四种情形讲了思路, 但代码量比插入大得多,本书没有逐行走查(第 12 章 AVL 同理)。
B+ 树(叶链表、顺序扫描友好)没出现——数据库索引的实际主力, 读者需要时得另找材料(补充,不在书里)。
广度优先的加权/优先级版本(如 Dijkstra 的堆优化)要等第 14、17 章拼出来。
「左孩子右兄弟」只讲了表示,用它实现具体算法(如多叉树删除)留给读者迁移。

6. 可带走的¶

一般树两种表示:children 数组(DOM 风)与左孩子右兄弟(二叉算法复用)。
森林 = 根的数组,或根互为兄弟;循环双向兄弟链表在后面章节还有戏。
遍历:前序/后序保留;中序无对应;深搜配栈、广搜配队列(非递归要点:逆序压栈)。
B 树五规则:≤m−1 键、半满、叶同层;查找=节点内定位+下钻。
B 树插入靠分裂(中键上提、根分裂才长高);删除靠借与合并(根空才缩矮)。
左倾红黑树 = 2-3 树的二叉表示:红左倾、红不连红、黑平衡。
红黑插入:新节点先红,回溯修复三情形;搜索代码与 BST 相同。
工程事实:红黑树在 Linux 内核(目录项/虚存/调度)服役。

7. 原文地图¶

主题	原书章	原文位置
树/森林/果园定义	Defining Trees and Forests	`text/42-fm-defining-trees-and-forests.txt:29`(搜「multiary」) · `text/42-fm-defining-trees-and-forests.txt:35`(搜「orchard」)
children 数组表示	Defining Trees and Forests	`text/42-fm-defining-trees-and-forests.txt:62`(搜「class Tree」) · `text/42-fm-defining-trees-and-forests.txt:129`(搜「addChild」)
左孩子右兄弟	Defining Trees and Forests	`text/42-fm-defining-trees-and-forests.txt:183`(搜「first child」)
森林表示	Defining Trees and Forests	`text/42-fm-defining-trees-and-forests.txt:212`(搜「array of roots」)
遍历与广搜队列	Defining Trees and Forests	`text/42-fm-defining-trees-and-forests.txt:272`(搜「depthFirst」) · `text/42-fm-defining-trees-and-forests.txt:299`(搜「breadthFirst」)
B 树五规则与动机	Defining Trees and Forests	`text/42-fm-defining-trees-and-forests.txt:338`(搜「order m」) · `text/42-fm-defining-trees-and-forests.txt:363`(搜「shorter height」)
B 树查找/分裂/合并	Defining Trees and Forests	`text/42-fm-defining-trees-and-forests.txt:435`(搜「_findIndex」) · `text/42-fm-defining-trees-and-forests.txt:493`(搜「Adding a Key」) · `text/42-fm-defining-trees-and-forests.txt:584`(搜「Removing a Key」)
红黑树=2-3 表示/黑平衡	Defining Trees and Forests	`text/42-fm-defining-trees-and-forests.txt:863`(搜「left-leaning」) · `text/42-fm-defining-trees-and-forests.txt:893`(搜「left」) · `text/42-fm-defining-trees-and-forests.txt:921`(搜「black balance」)
红黑插入三情形	Defining Trees and Forests	`text/42-fm-defining-trees-and-forests.txt:996`(搜「case (a)」)
习题与答案	Chapter 13	`text/76-ch13-chapter-13.txt:34`(搜「reverse order」) · `text/76-ch13-chapter-13.txt:40`(搜「JSON.stringify」)

出处:「Defining Trees and Forests」第 62–171 段(text/42-fm-defining-trees-and-forests.txt:62,搜「class Tree」;:129,搜「addChild」)。原文:类风格表示,getter/setter 仿 DOM;addChild 用 splice 在兄弟间插位,removeChild 摘位。 ↩
出处:「Defining Trees and Forests」第 183–202 段(text/42-fm-defining-trees-and-forests.txt:183,搜「first child」)。原文:left 指第一个孩子、right 指下一个兄弟;「算法上与第 12 章二叉树无需任何不同」;「第 15 章二项堆及其变体会用到」见第 191 段注。 ↩
出处:「Defining Trees and Forests」第 272–310 段(text/42-fm-defining-trees-and-forests.txt:272,搜「depthFirst」;:299,搜「breadthFirst」)。原文:深搜递归访问根再逐子树;广搜用队列,出队访问、孩子全部入队,「永不先访比根更远的节点」。 ↩
出处:「Defining Trees and Forests」第 313 段(text/42-fm-defining-trees-and-forests.txt:313,搜「symmetry」)与「Chapter 13」第 19–35 段(text/76-ch13-chapter-13.txt:34,搜「reverse order」)。原文:「广搜不用递归要用队列,深搜不用递归要用栈」;答案:孩子逆序压栈,reverse() 会改数组要用解构复制。 ↩↩
出处:「Defining Trees and Forests」第 335 段(text/42-fm-defining-trees-and-forests.txt:335,搜「Bayer」)。原文注:1972 年 Bayer 与 McCreight 定义,B 含义无解释,「balanced/broad/bushy/Bayer」任选。 ↩
出处:「Defining Trees and Forests」第 338–363 段(text/42-fm-defining-trees-and-forests.txt:338,搜「order m」;:363,搜「shorter height」)。原文:五条性质;「更大的值更受欢迎,以换取更矮的树和更快的访问」。 ↩↩
出处:「Defining Trees and Forests」第 435–453 段(text/42-fm-defining-trees-and-forests.txt:435,搜「_findIndex」)。原文:节点内找第一个 ≥key 的键,等则命中,否则走对应指针;「节点内似乎倒退成线性搜索,改进见习题 13.7」。 ↩
出处:「Defining Trees and Forests」第 493–584 段(text/42-fm-defining-trees-and-forests.txt:493,搜「Adding a Key」)。原文:有空位直插;满则中键上提、节点分裂;_tooBig 预判见第 393 段。 ↩
出处:「Defining Trees and Forests」第 584–781 段(text/42-fm-defining-trees-and-forests.txt:584,搜「Removing a Key」)。原文:非叶用后继顶替;叶太瘦先借后并;_tooSmall 预警见第 396 段;性能表见第 781 段。 ↩
出处:「Defining Trees and Forests」第 781–841 段(text/42-fm-defining-trees-and-forests.txt:781,搜「Performance」)。原文:查找/增删均 O(log n)。 ↩
出处:「Defining Trees and Forests」第 863–924 段(text/42-fm-defining-trees-and-forests.txt:863,搜「left-leaning」;:893,搜「connected to another red」;:921,搜「black balance」)。原文:左倾红黑树是 2-3 树的二叉表示;红左倾、红不连红、根黑、空树黑;「从根到叶所有路径黑节点数相同——黑色平衡」。 ↩↩
出处:「Defining Trees and Forests」第 959–1009 段(text/42-fm-defining-trees-and-forests.txt:996,搜「case (a)」)。原文:新节点先红不影响黑平衡;(a) 2-节点加左红无事,(b) 右红左旋,(c) 临时 4-节点颜色翻转上送;搜索代码不变见第 913 段。 ↩↩
出处:「Defining Trees and Forests」第 863 段(text/42-fm-defining-trees-and-forests.txt:863,搜「Linux kernel」)。原文:「红黑树性能很好,用于 Linux 内核跟踪目录项、虚拟内存、调度等」。 ↩
出处:「Chapter 13」第 40 段(text/76-ch13-chapter-13.txt:40,搜「JSON.stringify」)。答案原文:树相等不用递归比较,JSON 序列化字符串对拍即可。 ↩
出处:「Chapter 13」第 108 段附近(题 13.8「Lowest Order」,text/76-ch13-chapter-13.txt:102,搜「Lowest Order」)。答案原文:阶 2 的 B 树每节点至多一个键,退化无意义;阶 3(2-3 树)为实用起点。 ↩

第 13 章 树与森林 — 多叉、遍历与 B 树家族¶