高级数据结构与算法

这是一本补充数据结构 手册和算法 手册的书籍，并假定这些手册作为先决条件。

在线书籍写作有两个相互冲突的目标

• 作为对基础材料的介绍
• 成为包含对切线材料的讨论的完整参考作品

我们决定两者都做。数据结构 文本和算法 文本仅关注基础知识。本手册（高级数据结构与算法）是参考材料的地方。其想法是，学生在一年或更短的时间内可以涵盖这些基础知识，然后继续学习本书中的高级主题。

可能的话题

• 并行编程（部分；对分治的阐述，或用于流式算法的管道解耦）
• 内存管理和垃圾回收（整章）
• NP 完全性（整章）
• 主定理的证明（部分）
• 四叉树和 八叉树 以及 R 树（章）
• Trie 数据结构
• B 树（章）（我们不是已经介绍过这个主题了吗？请参阅 数据结构/树#B 树 和 算法实现/树/B+ 树 ？）
• （伪）随机数生成器（请参阅 统计/数值方法/随机数生成 等）
• 自省排序（部分；一种混合排序算法）
• 闭包（ 什么是闭包？ ）
• 延续（ 延续 ）
• 缓存感知和缓存无关算法
• 近似
• 最大流
• 素数测试（请参阅 算法实现/数学/素数测试，算法实现/数学/素数生成，一些基本且低效的素数生成算法，密码学/数学背景#素数测试，离散数学/数论#素数测试，密码学/RSA#密钥生成 等）

虽然这里还没有内容，但请随时开始编写部分！因为本书更像是一本参考书，所以章节之间可以更加独立。此外，您可以假设读者已经了解基本的数据结构和算法。

FFT 乘法*

如算法手册中所述，通过将一个整数分成两部分并将其视为一个多项式，我们能够推导出一个比小学乘法更好的算法。如果我们将整数分成三部分，则效率将进一步提高。然而，我们不需要止步于此：我们可以通过将一个n 位二进制数分成一个n 次多项式来推广多项式乘法和插值的技巧，从而将该数字分解成其各个数字（这也是我们能够将此类数字分割的最远程度）。

我们注意到，在点 1、-1 和 0 处对多项式表示进行求值使得表达式变得容易，但是如果我们要使用n 次多项式，我们该如何获得足够的点来使用呢？诀窍是使用复数对多项式进行求值，特别地，使用“单位根”：即所有距离原点为 1 的复数。

Trie 数据结构

Trie，也称为数字树，有时也称为基数树或前缀树（因为它们可以按前缀进行搜索），是一种有序的树形数据结构，通常用于存储关联数组，其中键通常是字符串。与 二叉搜索树 不同，树中的任何节点都没有存储完整的键。

树列表

w:Rope (计算机科学)

在处理列表时，我们通常有两种选择：要么我们获得 $O(1)$ 索引访问，但 $O(N)$ 插入，使用向量，或者 $O(N)$ 索引和 $O(1)$ 插入，使用链表。如果我们能够找到一些中间地带，比如所有操作的运行时间为 $O(\log N)$（摊销）那该有多好。好吧，Soren Sandmann 已经实现了 GSequence，它使用伸展树来实现这一点。[TODO: 该结构还没有广泛接受的名称。如果有人能想到更好的名称，请建议。]

我认为 B 树算法在最坏情况下提供 O(ln(N)) 插入、删除和按名称访问。GSequence 在某些方面是否更好？我听说一些操作系统将文件和目录存储在磁盘上，作为 B 树。--DavidCary 23:39, 21 July 2005 (UTC)

有很多平衡树可以提供 O(ln N) 的性能。这里的意思只是围绕树包装一个列表接口。你也可以说你使用的是树，因为列表接口只是为了实现方便。

有各种堆数据结构可以提供 O(log(N)) 插入、删除和按名称访问。

我相信这些被称为随机访问列表。此外，也可以实现 O(1) 插入和 O(log N) 索引；例如，Okasaki 的倾斜二项式随机访问列表。如果有兴趣，我可以上传一个 Common Lisp 中的演示质量实现。