clrs-algorithms

CLRS 数据结构与算法参考

基于《算法导论》（CLRS）的综合数据结构与算法参考。本技能提供与编程语言无关的指导和伪代码示例，可转换为任何编程语言。

本技能的触发条件

在以下情况下，本技能会自动触发：

• 询问或需要实现某种数据结构
• 需要为某个问题选择数据结构
• 讨论时间／空间复杂度的权衡
• 需要算法实现（排序、搜索、图算法）
• 提及特定结构：B 树、堆、哈希表、图等

数据结构快速参考

线性结构

结构	访问	搜索	插入	删除	适用场景
数组	O(1)	O(n)	O(n)	O(n)	大小已知，需要按索引访问
动态数组	O(1)	O(n)	O(1)*	O(n)	大小未知，频繁追加
链表	O(n)	O(n)	O(1)	O(1)	频繁插入／删除
栈	O(1)	O(n)	O(1)	O(1)	需要后进先出（LIFO）
队列	O(1)	O(n)	O(1)	O(1)	需要先进先出（FIFO）
双端队列	O(1)	O(n)	O(1)	O(1)	需要访问两端

树

结构	搜索	插入	删除	适用场景
二叉搜索树	O(log n)*	O(log n)*	O(log n)*	有序数据，频繁搜索
AVL 树	O(log n)	O(log n)	O(log n)	需要保证平衡
红黑树	O(log n)	O(log n)	O(log n)	频繁插入／删除
B 树	O(log n)	O(log n)	O(log n)	基于磁盘的存储
字典树	O(m)	O(m)	O(m)	字符串／前缀操作
堆	O(1)/O(n)	O(log n)	O(log n)	需要优先队列
伸展树	O(log n)*	O(log n)*	O(log n)*	自调整，具有时间局部性
树堆	O(log n)*	O(log n)*	O(log n)*	随机平衡、分割／合并
区间树	O(log n)	O(log n)	O(log n)	区间重叠查询
顺序统计树	O(log n)	O(log n)	O(log n)	秩／选择查询
K-D 树	O(log n)*	O(log n)*	O(log n)*	多维空间数据

基于哈希的结构

结构	搜索	插入	删除	适用场景
哈希表	O(1)*	O(1)*	O(1)*	快速键值查找
哈希集合	O(1)*	O(1)*	O(1)*	唯一性成员测试
布隆过滤器	O(k)	O(k)	不适用	概率性成员测试

图

结构	空间	添加边	查询边	适用场景
邻接表	O(V+E)	O(1)	O(degree)	稀疏图
邻接矩阵	O(V²)	O(1)	O(1)	稠密图

图算法

算法	时间	适用场景
网络流	O(VE²)	最大流、二分图匹配、最小割
强连通分量	O(V+E)	查找 SCC、2-SAT、依赖关系分析

字符串

结构	构建	搜索	适用场景
后缀数组	O(n log n)	O(m log n)	节省空间的字符串匹配
后缀树	O(n)	O(m)	快速模式匹配、LCS
字符串算法	O(m)	O(n)	KMP、Rabin-Karp、Boyer-Moore、Aho-Corasick

高级

结构	适用场景
跳表	概率平衡列表
不相交集	并查集操作
线段树	支持更新的区间查询
树状数组	支持更新的前缀和
斐波那契堆	Dijkstra、Prim，支持 O(1) decrease-key
二项堆	可合并的优先队列
van Emde Boas 树	整数键，操作复杂度为 O(log log u)

算法

算法	适用场景
排序算法	快速排序、归并排序、堆排序、基数排序等

* = 均摊或平均情况

决策指南

• 我应该使用哪种数据结构？ - 按使用场景提供的决策指南
• 复杂度速查表 - Big-O 快速参考

如何使用此参考资料

1. 选择数据结构：从决策指南开始
2. 学习数据结构：阅读完整文档和示例
3. 快速回顾：使用上方表格快速查阅
4. 实现：参考伪代码，并根据所用语言进行调整

语言转换说明

此参考资料中的伪代码使用以下约定：

• class 用于类型定义
• function 用于方法/函数
• -> 用于调用对象的方法
• // 用于注释
• 类型提示写作 name: Type

转换为你的语言：

• PHP：class、function、->、//，类型提示写在 docblock 或 PHP 8+ 中
• JavaScript/TypeScript：class、function/箭头函数、.、//、TS 类型
• Python：class、def、.、#、类型提示
• Java/C#：直接映射，并使用 new、泛型

---

基于 Cormen、Leiserson、Rivest 和 Stein 所著《算法导论》（CLRS）的概念，MIT Press。