--- frontmattername: clrs-algorithms
description: "Data structures and algorithms reference based on CLRS. Use this skill when implementing, discussing, or choosing data structures or algorithms. Auto-activates for algorithm selection, complexity analysis, and performance optimization. Comprehensive coverage of fundamental and advanced data structures with pseudocode examples."
CLRS Data Structures & Algorithms Reference
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.
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.
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 |
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 |
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 |
Graphs
Graph Algorithms
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 |
Advanced
Algorithms
* = amortized or average case
Decision Guides
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:
- •
class for type definitions
- •
function for methods/functions
- •
-> 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, function/arrow, ., //, TS types
- •Python:
class, def, ., #, type hints
- •Java/C#: Direct mapping with
new, generics
Based on concepts from "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein (CLRS), MIT Press.