clrs-algorithms
Compare original and translation side by side
🇺🇸
Original
English🇨🇳
Translation
ChineseCLRS Data Structures & Algorithms Reference
基于CLRS的数据结构与算法参考资料
A comprehensive reference for data structures and algorithms based on "Introduction to Algorithms" (CLRS). This skill provides language-agnostic guidance with pseudocode examples that can be translated to any programming language.
这是基于《算法导论》（CLRS）的全面数据结构与算法参考资料。本技能提供与语言无关的指导，附带可转换为任意编程语言的伪代码示例。
When This Skill Activates
本技能的激活场景
This skill automatically activates when you:
- Ask about or need to implement a data structure
- Need to choose between data structures for a problem
- Discuss time/space complexity trade-offs
- Need algorithm implementations (sorting, searching, graph algorithms)
- Mention specific structures: B-tree, heap, hash table, graph, etc.
当你进行以下操作时，本技能会自动激活：
- 询问或需要实现某一数据结构
- 需要为某个问题选择合适的数据结构
- 讨论时间/空间复杂度的权衡
- 需要算法实现（排序、查找、图算法等）
- 提及特定结构：B-tree、heap、hash table、graph等
Quick Data Structure Reference
快速数据结构参考
Linear Structures
线性结构
| Structure | Access | Search | Insert | Delete | Use When |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | Known size, index access |
| Dynamic Array | O(1) | O(n) | O(1)* | O(n) | Unknown size, frequent append |
| Linked List | O(n) | O(n) | O(1) | O(1) | Frequent insert/delete |
| Stack | O(1) | O(n) | O(1) | O(1) | LIFO needed |
| Queue | O(1) | O(n) | O(1) | O(1) | FIFO needed |
| Deque | O(1) | O(n) | O(1) | O(1) | Both ends access |
| 结构 | 访问时间 | 查找时间 | 插入时间 | 删除时间 | 适用场景 |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | 已知数据规模，需索引访问 |
| Dynamic Array | O(1) | O(n) | O(1)* | O(n) | 数据规模未知，需频繁追加元素 |
| Linked List | O(n) | O(n) | O(1) | O(1) | 需频繁插入/删除操作 |
| Stack | O(1) | O(n) | O(1) | O(1) | 需要后进先出（LIFO）操作 |
| Queue | O(1) | O(n) | O(1) | O(1) | 需要先进先出（FIFO）操作 |
| Deque | O(1) | O(n) | O(1) | O(1) | 需要访问两端元素 |
Trees
树结构
| Structure | Search | Insert | Delete | Use When |
|---|---|---|---|---|
| Binary Search Tree | O(log n)* | O(log n)* | O(log n)* | Ordered data, frequent search |
| AVL Tree | O(log n) | O(log n) | O(log n) | Guaranteed balance needed |
| Red-Black Tree | O(log n) | O(log n) | O(log n) | Frequent inserts/deletes |
| B-Tree | O(log n) | O(log n) | O(log n) | Disk-based storage |
| Trie | O(m) | O(m) | O(m) | String/prefix operations |
| Heap | O(1)/O(n) | O(log n) | O(log n) | Priority queue needed |
| Splay Tree | O(log n)* | O(log n)* | O(log n)* | Self-adjusting, temporal locality |
| Treap | O(log n)* | O(log n)* | O(log n)* | Randomized balance, split/merge |
| Interval Tree | O(log n) | O(log n) | O(log n) | Interval overlap queries |
| Order-Statistic Tree | O(log n) | O(log n) | O(log n) | Rank/select queries |
| K-D Tree | O(log n)* | O(log n)* | O(log n)* | Multi-dimensional spatial data |
| 结构 | 查找时间 | 插入时间 | 删除时间 | 适用场景 |
|---|---|---|---|---|
| Binary Search Tree | O(log n)* | O(log n)* | O(log n)* | 有序数据，需频繁查找 |
| AVL Tree | O(log n) | O(log n) | O(log n) | 需要保证树的平衡 |
| Red-Black Tree | O(log n) | O(log n) | O(log n) | 需频繁插入/删除操作 |
| B-Tree | O(log n) | O(log n) | O(log n) | 基于磁盘的存储场景 |
| Trie | O(m) | O(m) | O(m) | 字符串/前缀操作场景 |
| Heap | O(1)/O(n) | O(log n) | O(log n) | 需要优先队列 |
| Splay Tree | O(log n)* | O(log n)* | O(log n)* | 自调整结构，需时间局部性优化 |
| Treap | O(log n)* | O(log n)* | O(log n)* | 随机化平衡，需拆分/合并操作 |
| Interval Tree | O(log n) | O(log n) | O(log n) | 区间重叠查询场景 |
| Order-Statistic Tree | O(log n) | O(log n) | O(log n) | 排名/选择查询场景 |
| K-D Tree | O(log n)* | O(log n)* | O(log n)* | 多维空间数据场景 |
Hash-Based
哈希类结构
| Structure | Search | Insert | Delete | Use When |
|---|---|---|---|---|
| Hash Table | O(1)* | O(1)* | O(1)* | Fast key-value lookup |
| Hash Set | O(1)* | O(1)* | O(1)* | Unique membership testing |
| Bloom Filter | O(k) | O(k) | N/A | Probabilistic membership |
| 结构 | 查找时间 | 插入时间 | 删除时间 | 适用场景 |
|---|---|---|---|---|
| Hash Table | O(1)* | O(1)* | O(1)* | 快速键值对查找 |
| Hash Set | O(1)* | O(1)* | O(1)* | 唯一成员检测场景 |
| Bloom Filter | O(k) | O(k) | 不支持 | 概率型成员检测场景 |
Graphs
图结构
| Structure | Space | Add Edge | Query Edge | Use When |
|---|---|---|---|---|
| Adjacency List | O(V+E) | O(1) | O(degree) | Sparse graphs |
| Adjacency Matrix | O(V²) | O(1) | O(1) | Dense graphs |
| 结构 | 空间复杂度 | 添加边操作 | 查询边操作 | 适用场景 |
|---|---|---|---|---|
| Adjacency List | O(V+E) | O(1) | O(degree) | 稀疏图场景 |
| Adjacency Matrix | O(V²) | O(1) | O(1) | 稠密图场景 |
Graph Algorithms
图算法
| Algorithm | Time | Use When |
|---|---|---|
| Network Flow | O(VE²) | Max flow, bipartite matching, min cut |
| Strongly Connected Components | O(V+E) | Find SCCs, 2-SAT, dependency analysis |
| 算法 | 时间复杂度 | 适用场景 |
|---|---|---|
| Network Flow | O(VE²) | 最大流、二分图匹配、最小割问题 |
| Strongly Connected Components | O(V+E) | 查找强连通分量、2-SAT问题、依赖分析 |
Strings
字符串相关
| Structure | Build | Search | Use When |
|---|---|---|---|
| Suffix Array | O(n log n) | O(m log n) | Space-efficient string matching |
| Suffix Tree | O(n) | O(m) | Fast pattern matching, LCS |
| String Algorithms | O(m) | O(n) | KMP, Rabin-Karp, Boyer-Moore, Aho-Corasick |
| 结构 | 构建时间 | 查找时间 | 适用场景 |
|---|---|---|---|
| Suffix Array | O(n log n) | O(m log n) | 空间高效的字符串匹配 |
| Suffix Tree | O(n) | O(m) | 快速模式匹配、最长公共子序列（LCS） |
| String Algorithms | O(m) | O(n) | KMP、Rabin-Karp、Boyer-Moore、Aho-Corasick算法 |
Advanced
高级结构
| Structure | Use When |
|---|---|
| Skip List | Probabilistic balanced list |
| Disjoint Set | Union-find operations |
| Segment Tree | Range queries with updates |
| Fenwick Tree | Prefix sums with updates |
| Fibonacci Heap | Dijkstra, Prim with O(1) decrease-key |
| Binomial Heap | Mergeable priority queue |
| van Emde Boas Tree | Integer keys with O(log log u) operations |
| 结构 | 适用场景 |
|---|---|
| Skip List | 概率型平衡列表 |
| Disjoint Set | 并查集操作场景 |
| Segment Tree | 带更新的范围查询 |
| Fenwick Tree | 带更新的前缀和查询 |
| Fibonacci Heap | Dijkstra、Prim算法中需O(1)时间的decrease-key操作 |
| Binomial Heap | 可合并的优先队列 |
| van Emde Boas Tree | 整数键场景，需O(log log u)时间复杂度的操作 |
Algorithms
算法
| Algorithm | Use When |
|---|---|
| Sorting Algorithms | QuickSort, MergeSort, HeapSort, RadixSort, and more |
* = amortized or average case
| 算法 | 适用场景 |
|---|---|
| Sorting Algorithms | QuickSort、MergeSort、HeapSort、RadixSort等排序算法 |
* = 均摊或平均情况
Decision Guides
决策指南
- Which Data Structure Should I Use? - Decision guide by use case
- Complexity Cheat Sheet - Quick reference for Big-O
- Which Data Structure Should I Use? - 按使用场景划分的决策指南
- Complexity Cheat Sheet - Big-O复杂度速查表
How to Use This Reference
本参考资料的使用方法
- Choosing a structure: Start with the decision guides
- Learning a structure: Read the full documentation with examples
- Quick reminder: Use the tables above for at-a-glance reference
- Implementation: Follow the pseudocode, adapt to your language
- 选择结构：从决策指南开始
- 学习结构：阅读完整文档及示例
- 快速查阅：使用上方表格进行即时参考
- 实现开发：遵循伪代码，适配你的编程语言
Language Translation Notes
语言转换说明
The pseudocode in this reference uses these conventions:
- for type definitions
class - for methods/functions
function - for method calls on objects
-> - for comments
// - Type hints shown as
name: Type
Translate to your language:
- PHP: ,
class,function,->, type hints in docblocks or PHP 8+// - JavaScript/TypeScript: ,
class/arrow,function,., TS types// - Python: ,
class,def,., type hints# - Java/C#: Direct mapping with , generics
new
Based on concepts from "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein (CLRS), MIT Press.
本参考资料中的伪代码采用以下约定：
- 用于类型定义
class - 用于方法/函数定义
function - 用于对象的方法调用
-> - 用于注释
// - 类型提示格式为
name: Type
转换至各编程语言的说明：
- PHP：使用、
class、function、->，类型提示可放在文档块或使用PHP 8+的类型声明// - JavaScript/TypeScript：使用、
class/箭头函数、function、.，TypeScript可使用类型声明// - Python：使用、
class、def、.，支持类型提示# - Java/C#：直接映射，使用、泛型等特性
new
基于Cormen、Leiserson、Rivest和Stein所著《算法导论》（CLRS，MIT出版社）中的概念。