第 12 章二叉树 — 形状决定速度,平衡的两条路线¶

这一章讲什么: 二叉搜索树怎么实现集合,以及它最大的软肋——形状—— 怎么用两种哲学修复:AVL 的「显式规则 + 旋转」与随机化/伸展的「交给概率或访问模式」。它在全书链条里的位置:树家族的开篇;第 13 章推广到多叉,第 14 章特化成堆, 形状与平衡的话题会一路陪到底。

1. 顶层全景¶

  二叉搜索树性质:任一节点,左子树全部更小、右子树全部更大
      │
      ├─ find:add:顺着性质左走/右走,期望 O(log n)、最坏 O(n)(形状像链)
      ├─ remove 三档:叶子→摘掉;一子→子顶上;双子→右子树最小值顶替
      ├─ 遍历:前序(根左右)/ 中序(左根右 = 有序输出)/ 后序(左右根)
      │
      └─ 修复形状的两种哲学:
           保证平衡:AVL(高度差≤1,单/双旋转恢复;最坏也 O(log n),高≤1.44 log n)
                     BB[α](子树权重比 ≥α,0<α<0.5)
           概率/自调整:随机化 BST(新键以 1/size 概率提根,分裂/合并保随机形状)
                       伸展树(每次访问把节点旋到根;摊还 O(log n),最坏 O(n))

  图说:左边花钱买确定性,右边用随机/局部性换简单。选择取决于你要最坏保证还是平均快。

2. 主线例子:同一棵树上的四次操作¶

用原书图 12-10 的树(键:22 为根,左子 9→(4, 11→10),右子 56→(24→23)):

① find(12):22 大了走左;9 小了走右;11 小了走右;12 命中。路径 22→9→11→12,四次比较——树高即查找成本¹。

② add(34):同 find 的路径走到空——34>22 右,34<56 左,34>24 右,空, 挂为 24 的右孩子。新键永远加在「搜索失败的地方」²。

③ remove(10)(叶子):找到 10 是 11 的左孩子,直接摘掉,11 的左子变空³。

④ remove(9)(双子):9 有两棵子树。右子树最小值 = 一路向右子左走:11→10, 用 10 顶替 9 的位置,再从右子树删掉那个 10⁴。

然后看中序遍历(inorder)的输出:4, 9, 10, 11, 22, 23, 24, 56—— 升序,免费。书里点破:这跟快排同构(左半有序 + pivot + 右半有序)⁵。 BST 兼做排序器:全部插入 + 中序遍历 = O(n log n) 排序(注释里承认这不是它的主业)。

3. 核心原理¶

3.1 形状就是性能¶

n 个节点的树,形状从「完美二叉树」(高 log n)到「退化的链」(高 n)都有可能; 查找成本跟着高度走,平均 O(log n)、最坏 O(n)。随机顺序插入可得平均形状, 顺序插入则必然成链——这正是第 6 章快排死穴的树版⁶。修复只有两条路:随时强制形状(保证平衡),或者让形状在概率/使用中被拉好。

3.2 AVL:高度差这条铁律¶

AVL(1962,Adelson-Velsky 与 Landis)给每个节点立规矩: 左右子树高度差不超过 1。每个节点多记一个 height 字段; add/remove 之后回溯路径,发现差超过 1 就旋转。两种情形:

左左/右右(同侧失衡):一次单旋转解决;
左右/右左(异侧失衡):先对内侧子树转一次、再转外侧,共两次⁷。

旋转本身只换三根指针,且不破坏 BST 性质(中序序列不变)—— 它是纯形状手术。结果:树高 ≤ 1.44 log n,最坏情况也是 O(log n), 代价是 add/remove 代码量和记账(height 字段)⁸。书里还给了对称思路 BB[α]:不看高度看权重(子树大小+1), 两子树权重都 ≥ α·总权重(α≈0.29 常用),失衡时同样旋转恢复⁹。

3.3 随机化 BST:用分裂和合并代替旋转¶

另一种思路:不让树按插入顺序成形,而是让每个新键随机决定当不当根。 add 时,以 1/size 的概率把新键提为根(在当前子树范围内)—— 提根需要把原树按新键分裂成「小于」和「大于」两棵,各挂一侧; 概率测试逐层做,所以随机性渗透整棵树,不只是根¹⁰。 remove 遇双子时改用 _join(左, 右):按两子树的 size 比例随机选根 (6 和 4 就以 6:4 选),递归合并——无需找后继、无需旋转¹¹。效果:树的分布等价于「随机顺序插入」的 BST,期望 O(log n); 最坏仍 O(n)(随机数可能全程作对),但没有 AVL 的记账, size 字段顺便支持按秩查找¹²。

3.4 伸展树:访问即重构¶

伸展(splay)树干脆不追求「随时平衡」,它的规矩只有一条: 每次访问(find/add/remove)都把目标节点用旋转提到根。三种旋法(名字古色古香): - zig/zag(节点是根的左/右孩子):一次单旋转; - zig-zig/zag-zag(同侧两代):先旋父、再旋自己——注意顺序,直接旋两次会留下糟糕结构(书里有 1-2-3-4-5 链的反面教材); - zig-zag/zag-zig(异侧):两次旋转把节点顶上去¹³。

为什么有用:热点键被访问后离根近,下次更快(编译器符号表是书里的例子); 且 k 次操作总成本 O(k log n)——摊还 O(log n), 虽然单次可能 O(n)(实时系统因此不敢用)¹⁴。 add 更妙:先把树按新键 splay(结果根是最接近的键),新键直接当根、原树按大小关系拆成两棵子树¹⁵。

4. 作者的判断与证据¶

「形状决定性能」由性能表贯穿:普通 BST 平均/最坏两栏并列(AVL 两栏相同, 随机化两栏不同,伸展只报摊还)——这张对比表就是本章的论点⁶。
旋转方向的命名混乱被主动提示(注:各资料左右叫法相反), 并给出记忆法:「看老根往哪边去」⁷——对自学者极友好的细节。
三种结构的适用口径都给了:AVL「要绝对保证时用」;随机化「无记账、顺带按秩」;伸展「热点访问模式、不怕单次抖动」——选型判断明确¹⁴。
证明一如既往地略去:AVL 高度界 1.44 log n、随机化的期望对数、伸展的摊还界,全部「可证(证略)」⁸。

判断(我们的,不是书里的): 本章三族结构其实是同一枚硬币的三面—— 都在回答「插入顺序不可信,如何让树的形状像随机插入」: AVL 用规则模拟随机性(强制形状接近完美),随机化 BST 直接采样随机性, 伸展树利用访问序列的局部性来逼近随机性。把它们读成「对抗插入顺序的三种策略」,比记三套代码更有迁移价值。 如果错,会错在: 这个统一视角是我们的重构;AVL 的动机(发明于 1962 年) 并不是「模拟随机」而是「保证查找」——统一视角是事后归因, 作为记忆法优秀,作为历史解读失真。

5. 边界与局限¶

红黑树在本章缺席:只在 AVL 一节末尾预告「下一章从多叉树角度讲」;
2-3-4 树、B 树与红黑树的等价关系要等第 13 章。
删除的「双子用后继顶替」不是唯一解:注里指向随机化的 _join 与第 14 章 treap 的第三种删法⁴。
摊还分析只给结论(伸展 O(k log n)),想看势能法证明得去别处。
树的序列化/反序列化、持久化 BST(第 18 章只讲部分)没展开。

6. 可带走的¶

BST 性质:左小右大;find/add 同路径,add 落在搜索失败处;期望 O(log n)、最坏 O(n)。
remove 三档:叶子摘、单子顶、双子用右子树最小值(=后继)顶替。
三种遍历:前序/中序/后序 = 根在访问序列的位置;中序 = 有序输出(快排同构)。
完美/满/完全三种形状:完美树高 log n,n 节点;完全树是堆的形状(第 14 章)。
AVL:高度差≤1 + height 记账;同侧单旋、异侧双旋;最坏 O(log n),高 ≤1.44 log n。
BB[α]:按子树权重(大小+1)比例 ≥α 约束平衡,α≈0.29。
随机化 BST:新键以 1/size 概率提根(分裂两棵挂两侧);删除双子用按 size 比例随机的 _join;顺带支持按秩。
伸展树:zig/zag、zig-zig(先父后己!)、zig-zag 三招把访问节点提到根;摊还 O(log n),热点场景最优;单次可能 O(n)。

7. 原文地图¶

主题	原书章	原文位置
二叉树/完美/完全定义	What Are Trees?	`text/37-fm-what-are-trees.txt:49`(搜「full」) · `text/37-fm-what-are-trees.txt:66`(搜「2h」)
BST 性质与 find 走查	What Are Trees?	`text/37-fm-what-are-trees.txt:184`(搜「smaller keys」) · `text/37-fm-what-are-trees.txt:226`(搜「12 < 22」)
add / remove 三档	What Are Trees?	`text/37-fm-what-are-trees.txt:276`(搜「newNode(keyToAdd)」) · `text/37-fm-what-are-trees.txt:346`(搜「minKey(tree.right)」)
遍历与中序=排序	What Are Trees?	`text/37-fm-what-are-trees.txt:419`(搜「Preorder」) · `text/37-fm-what-are-trees.txt:462`(搜「ascending order」)
性能与形状	What Are Trees?	`text/37-fm-what-are-trees.txt:528`(搜「linear structure」)
AVL 规则/旋转/双旋	Assured Balanced Binary Search Trees	`text/38-fm-assured-balanced-binary-search-trees.txt:23`(搜「differ at most by one」) · `text/38-fm-assured-balanced-binary-search-trees.txt:141`(搜「symmetrical」) · `text/38-fm-assured-balanced-binary-search-trees.txt:171`(搜「left-right」)
AVL 高度界与性能	Assured Balanced Binary Search Trees	`text/38-fm-assured-balanced-binary-search-trees.txt:322`(搜「1.44」)
BB[α] 权重约束	Assured Balanced Binary Search Trees	`text/38-fm-assured-balanced-binary-search-trees.txt:334`(搜「p + 1」)
随机化 BST 提根/分裂/合并	Probabilistic Balance Binary Search Trees	`text/39-fm-probabilistic-balance-binary-search-trees.txt:68`(搜「tree.size」) · `text/39-fm-probabilistic-balance-binary-search-trees.txt:171`(搜「_split」) · `text/39-fm-probabilistic-balance-binary-search-trees.txt:264`(搜「_join」)
伸展三招与摊还	Probabilistic Balance Binary Search Trees	`text/39-fm-probabilistic-balance-binary-search-trees.txt:416`(搜「zig」) · `text/39-fm-probabilistic-balance-binary-search-trees.txt:444`(搜「zig-zig」) · `text/39-fm-probabilistic-balance-binary-search-trees.txt:673`(搜「amortized」)

出处:「What Are Trees?」第 226 段(text/37-fm-what-are-trees.txt:226,搜「12 < 22」)。原文走查:12<22 左,12>9 右,12>11 右,命中;find 代码见第 240 段(空→false,等→true,否则递归左右)。 ↩
出处:「What Are Trees?」第 262、274 段(text/37-fm-what-are-trees.txt:262,搜「added at the place」)。原文:新键「加在搜索本应找到它的位置」;代码:side = keyToAdd <= tree.key ? left : right 递归。 ↩
出处:「What Are Trees?」第 304–317 段(text/37-fm-what-are-trees.txt:304,搜「Removing a leaf」)。原文:删叶直接摘;单子用孩子顶替(24 删后 23 成为 56 的左孩子)。 ↩
出处:「What Are Trees?」第 321–352 段(text/37-fm-what-are-trees.txt:346,搜「minKey(tree.right)」)。原文:双子用右子树最小值(后继)顶替,再递归删那个后继;「这不是唯一的删法」见第 360 段注。 ↩↩
出处:「What Are Trees?」第 462 段(text/37-fm-what-are-trees.txt:462,搜「ascending order」)与第 470 段注(搜「quicksort」)。原文:inOrder 按键升序列出;注:「这与第 6 章快排类似——左半有序、pivot、右半有序」。 ↩
出处:「What Are Trees?」第 528–539 段(text/37-fm-what-are-trees.txt:528,搜「linear structure」)。原文:最坏形状「本质上等于链表,O(n)」;随机顺序插入可证多数树较矮,平均 O(log n);性能表见第 544 段。 ↩↩
出处:「Assured Balanced Binary Search Trees」第 23、141–179 段(text/38-fm-assured-balanced-binary-search-trees.txt:23,搜「differ at most by one」;:149,搜「right rotation」;:171,搜「left-right」)。原文:规则、方向记忆法(老根去哪)、单旋与双旋两情形;命名混乱的警告见第 157 段注。 ↩↩
出处:「Assured Balanced Binary Search Trees」第 322 段(text/38-fm-assured-balanced-binary-search-trees.txt:322,搜「1.44」)。原文:「可证 AVL 树的高度以 1.44 log n 为界」;性能表(平均=最坏=O(log n))见第 242 段。 ↩↩
出处:「Assured Balanced Binary Search Trees」第 334–337 段(text/38-fm-assured-balanced-binary-search-trees.txt:334,搜「p + 1」)。原文:(p+1) ≥ α(n+1) 且 (q+1) ≥ α(n+1),0<α<0.5;示例 α=0.29289。 ↩
出处:「Probabilistic Balance Binary Search Trees」第 65–77 段(text/39-fm-probabilistic-balance-binary-search-trees.txt:68,搜「tree.size」)。原文:tree.size * Math.random() < 1 时分裂提根;「随机测试在每一层都做,随机性渗透整棵树」见第 81 段。 ↩
出处:「Probabilistic Balance Binary Search Trees」第 264–281 段(text/39-fm-probabilistic-balance-binary-search-trees.txt:264,搜「_join」)。原文:按 size 比例随机选根(totalSize * Math.random() < leftSize 取左),递归合并;走查(9 与 23 之间 6:4)见第 261 段。 ↩
出处:「Probabilistic Balance Binary Search Trees」第 291 段(text/39-fm-probabilistic-balance-binary-search-trees.txt:291,搜「logarithmic」)。原文:随机化使平均对数;「最坏仍线性——所有随机数都可能与你作对」;size 支持按秩见第 49 段注。 ↩
出处:「Probabilistic Balance Binary Search Trees」第 416–476 段(text/39-fm-probabilistic-balance-binary-search-trees.txt:416,搜「zig」;:444,搜「zig-zig」)。原文:zig/zag 单旋;zig-zig 先旋父再旋己,并给出「直接旋两次更糟」的 1-2-3-4-5 反面走查。 ↩
出处:「Probabilistic Balance Binary Search Trees」第 388、673 段(text/39-fm-probabilistic-balance-binary-search-trees.txt:388,搜「amortized」)。原文:「k 次连续操作 O(k log n)」;最坏线性故「实时上下文需要绝对时间保证时不适用」;编译器符号表热点例子见第 402 段。 ↩↩
出处:「Probabilistic Balance Binary Search Trees」第 563–575 段(text/39-fm-probabilistic-balance-binary-search-trees.txt:566,搜「_splay(tree, keyToAdd)」)。原文:add 先 splay 再让新键当根,原树按大小拆为两子树。 ↩

第 12 章 二叉树 — 形状决定速度,平衡的两条路线¶