01 / 导读
导读
引用
Morin, P. (2013). Open Data Structures: An Introduction. AU Press. Free official edition: https://opendatastructures.org/
章节概要
第1章：引言
开篇一章先解释效率为何重要：通过粗略估算说明，在一百万个未排序元素中进行一百万次查找会耗费过长时间；随后定义贯穿全书的接口：Queue、Stack 与 Deque、List、USet（无序集合）和 SSet（有序集合）。本章复习所需的数学知识（对数、阶乘、渐近记号，以及涉及期望和指示变量的随机化），确定 w 位字 RAM 计算模型，并用"分期还房贷与一次性买房""购买火灾保险"的类比区分最坏情况、均摊和期望运行时间。它还说明书中的 Java 代码经过简化（没有 public、private 等关键字），并给出全书所有数据结构的汇总表。
第2章：基于数组的列表
本章在底层数组之上实现 List 和 Queue。先讲 ArrayStack 及其扩容与缩容的均摊分析，再给出使用批量数组复制的优化版本、循环的 ArrayQueue、两端都能快速操作的 ArrayDeque，以及由两个栈构成、在一侧不足时重新平衡的 DualArrayDeque。最后介绍 RootishArrayStack：它把元素存放在大小递增的块中，只浪费约 √n 的空间，并讨论了如何计算平方根。
第3章：链表
链表以放弃常数时间按下标访问为代价，换来在已知结点旁常数时间的插入和删除。本章实现单链表（用于栈和队列操作）、带哑结点的双链表，以及 SEList——一种在每个结点中存放小块元素的节省空间的列表，并对块的分散与聚集进行均摊分析。
第4章：跳表
跳表利用随机抛硬币构建多层链表。本章实现每次操作期望时间为 O(log n) 的 SSet，以及支持按下标访问的 SkiplistList，然后分析期望的查找路径长度和空间。
第5章：哈希表
第一部分实现采用乘法哈希的拉链法哈希表，以及线性探测哈希表，分析线性探测并介绍表格哈希。第二部分说明如何为基本类型、复合对象、数组和字符串构造哈希码。作者提到，代码中的"随机"常数是用大气噪声生成的。
第6章：二叉树
在定义二叉树术语之后，本章编写递归和非递归的遍历方法，以及一个不平衡的 BinarySearchTree，包括查找、插入和删除。章末讨论预告了后续几章获得 O(log n) 性能的三种途径：随机化、均摊和最坏情况下的平衡。
第7章：随机二叉搜索树
本章先证明由随机排列构建的二叉搜索树期望查找路径长度为对数级，再利用这一结论设计 Treap（树堆），通过赋予随机优先级使树在插入和删除后仍保持随机形态。
第8章：替罪羊树
替罪羊树通过偶尔把整棵子树重建为完全平衡的子树来保持平衡。本章实现重建操作，并证明更新操作的均摊代价为 O(log n)，而查找由于高度受限，在最坏情况下也是 O(log n)。
第9章：红黑树
这是技术性最强的一章。它先介绍 2-4 树，再把红黑树实现为对 2-4 树的模拟（采用左倾变体），并逐一分析插入和删除的各种情况。本章解释了红黑树为何被 Java 集合框架等库采用：高度为对数级、最坏情况下 O(log n) 的更新，以及均摊常数次的旋转。
第10章：堆
本章开发两种优先队列：BinaryHeap，用 Eytzinger 布局把完全二叉树存放在数组中；以及 MeldableHeap，一种随机化的堆，其合并操作还支持把两个堆融合在一起。
第11章：排序算法
本章介绍归并排序、快速排序和堆排序，证明基于比较的排序的下界，然后介绍适用于整数的计数排序和基数排序，并把快速排序与随机搜索树、堆排序与 BinaryHeap 联系起来。
第12章：图
用邻接矩阵和邻接表两种方式表示图并比较其代价，随后介绍广度优先搜索和深度优先搜索，包括非递归的深度优先搜索。
第13章：整数数据结构
本章回到 w 位整数键的 SSet 问题，依次构建 BinaryTrie（操作时间 O(w)）、借助哈希在 O(log w) 时间内查找的 XFastTrie，以及把 XFastTrie 中的样本与普通 SSet 结合、使所有操作期望时间为 O(log w) 的 YFastTrie。
第14章：外存查找
最后一章放弃"所有数据都能装入内存"的假设。它以实测的内存、固态硬盘和机械硬盘访问时间来说明外存模型的动机，引入块存储，并实现 B 树的查找、插入、删除，以及对分裂与合并的均摊分析。
核心概念
第1章：引言
- 接口与实现：接口（List、USet、SSet）规定有哪些操作；数据结构是实现这些操作的一种方式。
- 均摊时间与期望时间：均摊界对一系列操作的代价取平均，期望界则对数据结构自身的随机选择取平均。
- 字 RAM 模型：对 w 位字的基本操作耗时为常数、且 w 至少为 log n 的计算模型。
第2–3章：基于数组的列表与链表
- 可变大小的底层数组：数组容量加倍和减半，使末端添加和删除的均摊代价保持为常数。
- 循环数组：下标对数组长度取模，使队列或双端队列可以在任一端增长。
- 节省空间的结构：RootishArrayStack 和 SEList 把浪费的空间降到约 √n 或 n 的一小部分。
第4章：跳表
- 随机层级：每个元素以二分之一的概率被提升到上一层链表，从而使期望查找路径为对数长度。
第5章：哈希表
- 拉链法：数组的每个槽位存放一个列表，其中是哈希到该位置的元素。
- 线性探测：元素直接存放在数组中，冲突时向后扫描到下一个空槽位。
- 哈希码：把任意对象转换为整数的函数，其组合方式保证相等的对象得到相等的哈希码。
第6–9章：二叉搜索树
- 二叉搜索树性质：每个结点的值大于其左子树中的值、小于其右子树中的值。
- Treap：同时也是关于随机优先级的堆的搜索树，从而保持随机的形态。
- 部分重建：把不平衡的子树从头重建，这是替罪羊树背后的思想。
- 作为 2-4 树的红黑树：给结点着色，使二叉树编码一棵 2-4 树，从而保证高度至多为 2 log n。
第10–11章：堆与排序
- 隐式二叉树：把完全二叉树存放在数组中，父结点与子结点的位置可通过算术计算得到。
- 比较下界：任何基于比较的排序在最坏和平均情况下都需要大约 n log n 次比较。
第12–14章：图、整数与外存
- 邻接表：为每个顶点保存其出邻居列表的图表示方式。
- 二进制键上的字典树：从根到叶的路径拼出整数键各个二进制位的树。
- B 树：结点大小与磁盘块相匹配的平衡搜索树，使读取块的次数最少。
评析
优点
- 接口、实现与证明并重。 每种数据结构都对照一小组接口之一引入，给出完整实现，并以明确的定理加以分析；大多数小节以一段简短的运行时间总结结束。1.7 节的汇总表让读者可以一眼比较全部结构。
- 覆盖面超出一般的入门课程。 除了列表、哈希表、搜索树和堆之外，本书还讲解跳表、Treap、替罪羊树、可合并堆、X-fast 与 Y-fast 字典树以及 B 树，从而展示了达到同样界限的几种途径（随机化、均摊、最坏情况平衡）。
- 对三种性能保证的细致处理。 最坏情况、均摊和期望时间的区别在第1章通过具体类比建立起来，并贯穿全书，帮助学生理解诸如红黑树尽管复杂却仍被各种库采用的原因。
- 开放且可改编。 前言说明本书像开源项目一样运作：LaTeX 和 Java 源文件以知识共享署名许可发布在 GitHub 上，并提供 Java、C++ 和伪代码三个版本。每章的讨论部分都提供历史背景和参考文献。
局限
- 对入门课程而言数学要求较高。 证明从较早阶段（第4章起）就用到概率、指示变量和均摊论证，第9章红黑树删除的讨论篇幅很长。没有学过离散数学的学生可能会感到吃力。
- 代码经过简化而非地道写法。 Java 示例有意省略访问修饰符和类层次结构；读者需要查看配套源代码才能获得完整实现，而且本书不讲如何使用库中的集合类。
- 图和算法部分较为简略。 第12章只讲表示方式以及广度优先和深度优先搜索；最短路径、最小生成树等图算法都未涉及，AVL 树等平衡树也只在讨论部分提到。
- 版本细节有些过时。 所读版本（0.1G）出自 2010 年代初，有些例子（如 32 位 JVM 的字长和磁盘访问时间）反映的是那个时期的情况。书中没有提供练习答案。
在课程中的定位
在本课程的数据结构书目中，Morin 的书介于浅显易懂的图解类书籍（Bhargava 的 Grokking Algorithms 和 Wengrow 的 A Common-Sense Guide to Data Structures and Algorithms）与专门教材（Okasaki 的 Purely Functional Data Structures 和 Brass 的 Advanced Data Structures）之间。不熟悉形式化分析的学生可以先读一本入门书——这类书通常被认为以很少的数学建立直觉——然后再转向 Morin，学习证明和完整实现。
Goodrich、Tamassia 和 Goldwasser 的 Data Structures and Algorithms in Java 与本书内容相近；它通常被认为是覆盖面更广的传统教材，在 Java 编程和算法方面内容更多。因此可以把它作为主教材、以 Morin 作为免费且更偏分析的辅助读物，反之亦可。读完 Morin 之后，对更高级的搜索结构感兴趣的学生可以继续读 Brass，想了解同样的思想在纯函数式环境中如何呈现的学生可以读 Okasaki。
如何使用本书
本书适合已修完一门程序设计课程并学过一些离散数学的计算机专业二年级学生；第1章复习了后文用到的概率和渐近记号。熟悉 Java 会有帮助但并非必需，因为代码采用简化风格，懂任何类 C 语言的人都能读懂。
一学期的课程可以以下列内容为核心：第1章、第2章（至少 ArrayStack、ArrayDeque 和 DualArrayDeque）、第3章（单链表和双链表）、第5章、第6章、作为平衡方法的第7章或第8章、第10章和第11章。第4章的跳表是学习随机化分析的良好起点。第9章可以只读到与 2-4 树的对应关系，完整的删除情况作为选读。第12–14章适合较长的课程或自学。
每章末都有练习（全书共 150 多道），请做其中一部分；许多练习要求实现或修改某种结构，而可下载的源代码便于把自己的版本与书中的实现对照测试。各章的讨论部分介绍了每种思想的历史，并给出延伸阅读的线索。
版本与来源
本导读依据 Open Data Structures (in Java) 第 0.1G 版，阅读的是作者官方网站 https://opendatastructures.org/ 提供的免费 PDF（ods-java.pdf）；印刷版由 AU Press 于 2013 年出版。内容取材于致谢、前言"Why This Book?"、完整目录、第1章全文（1.1–1.8 节），以及第2–14章的章节引言、每个小节标题、小结与运行时间表，和各章的"Discussion and Exercises"部分。