01 / 导读
导读
引用
Brass, P. (2008). Advanced Data Structures. Cambridge University Press.
章节概要
全书474页，包含九章正文、一章附录、500多条参考文献以及作者索引和主题索引。Cambridge称其细致考察数据结构这一应用算法专题中的思想、分析与实现，并包含大量C语言代码示例。
第1章：Elementary Structures
栈、队列、双端队列、节点的动态分配，以及基于数组的结构的影子副本。这是书中最基础的内容，为后文使用的基于数组和基于节点的实现做准备。
第2章：Search Trees
两种搜索树模型、一般性质与变换、搜索树的高度，以及基本的查找、插入和删除操作。还包括从叶回到根、非唯一键、区间查询、构造最优搜索树、把树转换为列表以及删除整棵树。
第3章：Balanced Search Trees
单一家族中最长的一章：高度平衡树与权重平衡树、(a, b)树与B树、红黑树及近似最优高度的树、自顶向下再平衡、在已知位置常数时间更新的树、指状树与层链接、部分重建与摊还分析、伸展树、跳表，以及平衡树的合并与分裂。
第4章：Tree Structures for Sets of Intervals
区间树、线段树，用于区间并集、加权区间求和及区间受限最大和查询的树，然后是正交范围树、高维线段树、其他构件体系、范围计数与半群模型，以及kd树。
第5章：Heaps
从用作堆的平衡搜索树和基于数组的堆开始，然后是堆序树与半序树，左偏堆、斜堆、二项堆，键的修改，斐波那契堆，最优复杂度的堆，双端堆与多维堆，以及常数时间更新的堆相关结构。
第6章：Union-Find and Related Structures
用于合并划分中各类的并查集、带副本的并查集与动态线段树、列表分裂、有根有向树上的问题，以及维护线性序。
第7章：Data Structure Transformations
使结构动态化和持久化的通用技术。
第8章：Data Structures for Strings
字典树与压缩字典树、允许查询出错的字典、后缀树与后缀数组。
第9章：Hash Tables
基本哈希表与冲突解决、全域哈希函数族、完美哈希函数、哈希树、可扩展哈希，以及成员测试器和布隆过滤器。
第10章：Appendix
指针机与其他计算模型、外存模型与缓存无关算法、数据结构的命名、线性递推的求解，以及增长极慢的函数。
核心概念
第1–3章：基本结构与平衡结构
- 影子副本与节点分配：基本结构的实现技术。
- 平衡准则：高度平衡、权重平衡、(a, b)树与红黑树，是让树保持较浅的不同方式。
- 摊还分析、伸展树与跳表：替代显式平衡的自适应与随机化方法。
第4–6章：区间、堆与并查集
- 线段树、区间树与范围树：用于区间及多维点集查询的结构。
- 堆的变种：左偏堆、斜堆、二项堆与斐波那契堆。
- 并查集：高效合并划分中的各类。
第7–9章：变换、字符串与哈希
- 动态化与持久化：赋予结构更新能力或保留旧版本的通用变换。
- 字典树、后缀树与后缀数组：针对字符串集合的结构。
- 全域哈希与完美哈希；布隆过滤器：带保证或近似成员判断的哈希类结构。
评析
优点
- 把数据结构当作算法课题。 Cambridge称本书是第一本把这一主题当作重要的算法课题、而不是用来演示面向对象编程的琐碎材料的书。
- 广度超出标准课程。 区间与范围结构、篇幅很长的堆一章、并查集的各种变体、持久化与动态化、字符串结构以及多种哈希方案汇集在一册之中，500多条参考文献则指向文献来源。
- 代码与图示。 Software Engineering Notes上的书评者Igor Gvero称，本书满是插图、图表和代码，力求把计算机科学中最难的主题之一讲清楚；出版社则指出书中有大量C语言代码示例。
- 既可作教材也可作参考书。 SIGACT News的书评认为，它适合作为研究生数据结构课程的主教材或辅助教材，也是实现者案头的参考书。
局限
- 入口不均衡。 第1章是入门性的，但从第2章起，目录中出现摊还分析、最优搜索树、半群模型、缓存无关算法等以算法课为前提的术语。
- 偏重命令式。 代码示例用C写成，面向不可变数据的结构不在目录之内，因此函数式实现需要另找书籍。
- 更像参考书而非平缓的序列。 第3章和第5章各列出十几种变体，读者可能需要挑选章节阅读，而不是从头读到尾。
在课程中的定位
在本课程中，Brass是研究生水平、以广度见长的教材。Wengrow的A Common-Sense Guide to Data Structures and Algorithms与Bhargava的Grokking Algorithms是没有正式计算机科学背景的程序员的平缓起点。Goodrich、Tamassia与Goldwasser的Data Structures and Algorithms in Java是第二门课的教材，Morin的Open Data Structures为每种结构给出精确的接口、实现及运行时间上界的证明；二者都是读Brass之前合适的准备。
Okasaki的Purely Functional Data Structures涉及另一个分支，即带惰性求值的函数式语言中的持久化结构，与Brass关于持久化的第7章相得益彰。
如何使用本书
本书适合已经接触过栈、队列、树、哈希和渐近分析，并能阅读C代码的读者。可用于研究生课程、实现者的自学，或在标准库结构不够用时作为参考。
实用的阅读方案：
- 核心： 第2、3章（搜索树和主要的平衡树家族），然后是第5章（堆）和第9章（哈希表）。
- 选读专题： 对几何或数据库感兴趣读第4章，需要并查集的图算法读第6章，字符串处理读第8章。
- 技术： 第7章宜在读过被其变换的结构之后再读。
- 附录： 在跨章比较复杂度上界之前，先读讨论指针机和其他计算模型的10.1节。
书中的叙述围绕实现细节展开，所以每章至少用C实现一种结构。
