Index of algorithms and data structures
The section titles in this book tell a story rather than name a structure. This is the way in by name: every algorithm and data structure that the book teaches, alphabetically, with the chapter and the section where it is.
0–9
- 2-3 tree: Search › Where LLRB actually comes from
- 2-SAT: Graph structure and decomposition › A rule per group
- 3-SAT and the Exponential Time Hypothesis: Graph structure and decomposition › Three statements per rule
A
- Adjacency matrix: Graph structure and decomposition › Taking whoever is ready
- Algorithm T (Tarjan and Zwick): Graph structure and decomposition › One walk finds every knot
- Andrew’s monotone chain: Geometry and high-dimensional search › The part of town she knows
- AVL tree: Search › What “balanced” is allowed to mean
B
- B*-tree: Search › The B-tree, part by part
- B+-tree: Search › Search, top-down insertion and node splitting
- B-tree: Search › Frankenstein
- B-tree deletion: Search › Top-down deletion
- Balance conditions: Search › What “balanced” is allowed to mean
- Best-first search: Geometry and high-dimensional search › The closest region first
- Binary fuse filter: Search › Bloom filters
- Binary search: Search › An orderly key ring
- Binary search tree: Search › Escaping the line
- Binary search tree deletion: Search › Deletion
- Block-cut forest: Graph structure and decomposition › Whose phone matters?
- Bloom filter: Search › Bloom filters
- Bridge: Graph structure and decomposition › Whose phone matters?
- Bubble sort: Contracts and cost models › Slow code or a hard problem?
- Building navigable graphs: Geometry and high-dimensional search › How many links does it take?
- Burrows–Wheeler transform: Strings › Useful mess?
- Bw-tree: Search › Taken further: removing the last lock
C
- Cache-oblivious algorithms: Contracts and cost models › Frontier map
- Cache-oblivious layout (van Emde Boas): Search › Appendix: cache-oblivious variant
- Certifying algorithm: Contracts and cost models › Reference algorithms and certificates
- Compaction: Search › Compaction
- Condensation: Graph structure and decomposition › Shrinking the knots
- Constrained decoding: Graph structure and decomposition › Words that can still be finished
- Convex hull: Geometry and high-dimensional search › The part of town she knows
- Copy-on-write (path copying): Search › Copy-on-write
- Cuckoo filter: Search › Bloom filters
- Curse of dimensionality: Geometry and high-dimensional search › A place like this one
- Cut vertex (articulation point): Graph structure and decomposition › Whose phone matters?
- Cycle detection: Graph structure and decomposition › Following the waits
D
- Decision-tree lower bound: Contracts and cost models › Every strategy is a tree
- Depth-first search: Graph structure and decomposition › Following the waits
- Distances and similarity: Geometry and high-dimensional search › What “near” is allowed to mean
E
- Exact indexes over training data: Strings › Did the AI copy this?
F
- Filtered and changing data: Geometry and high-dimensional search › “Open now”
- Flip colors: Search › Insertion: rotations and color flips
- Floor and ceiling: Search › Order queries
- FM-index and backward search: Strings › By heart
- Fractional cascading: Geometry and high-dimensional search › Faster strips
- Fully dynamic connectivity: Graph structure and decomposition › Falling out
G
- Galloping (exponential) search: Search › Galloping search
- Graph decomposition: Graph structure and decomposition › What is this all about?
- Graph index: Geometry and high-dimensional search › Ask the locals
- Graphs inside a quantum computer: Graph structure and decomposition › Circuits and errors
H
- Hardness of nearest-neighbor search: Geometry and high-dimensional search › Why exact is out of reach
- HNSW (hierarchical navigable small world): Search › Search without a map; Geometry and high-dimensional search › Highways
I
- Incremental cycle detection: Graph structure and decomposition › The chat keeps talking
- Insertion into a sorted array: Search › Insertion means shoving
- Invisible characters as an attack: Strings › Text that hides text
J
- Johnson–Lindenstrauss lemma: Geometry and high-dimensional search › Random directions
K
- k-d tree: Geometry and high-dimensional search › The nearest one, now
- k-edge-connected components and failure oracles: Graph structure and decomposition › Other ways to cut
- Kahn’s method (topological sort): Graph structure and decomposition › Taking whoever is ready
- Keep an invariant: Contracts and cost models › Three tools to reuse
- Kosaraju–Sharir algorithm: Graph structure and decomposition › Kosaraju and Sharir’s two walks
L
- Learned graph algorithms: Graph structure and decomposition › Can a machine just do it?
- Learned index: Search › Self-adjusting and learned structures
- Left-leaning red-black tree (LLRB): Search › Sticky red links
- Left-leaning red-black tree deletion: Search › Deletion
- Leveled compaction: Search › Compaction
- Limits of single-vector embeddings: Geometry and high-dimensional search › What one list of numbers can’t say
- Locality-sensitive hashing: Geometry and high-dimensional search › Near points share a code
- Locate, extract and document listing: Strings › Give me the whole line
- Log-structured merge-tree (LSM-tree): Search › I’ll pay it back later
- Longest-prefix match: Strings › Appendix: the router’s question
- Lower bounds for dynamic strong connectivity: Graph structure and decomposition › When arrows also leave
- Lower bounds for string problems: Strings › How sure is “impossible”?
- Lower bounds for union-find: Graph structure and decomposition › Nearly a constant is the floor
- LSH and graph search inside attention: Geometry and high-dimensional search › The chatbot’s memory is a nearest-neighbor search
M
- Merge sort: Contracts and cost models › Three tools to reuse
- Merkle tree: Search › Trees that can prove what they hold
- Minimizers: Strings › Placing a million reads
N
- Navigable small-world graph: Search › Search without a map
- Nearest-neighbor and range queries: Geometry and high-dimensional search › What is this all about?
O
- Optimal binary search tree: Search › The best possible tree, when you know what gets asked for
- Ordered dictionary (dynamic set): Search › What is this all about?
P
- p-stable LSH: Geometry and high-dimensional search › A grid on a line
- Parallel strong components and parallel depth-first search: Graph structure and decomposition › More hands
- Path compression: Graph structure and decomposition › Trees that stay shallow
- Percolation: Graph structure and decomposition › When everyone joins
- Predecessor lower bound: Search › What order costs, proved
- Predecessor search: Search › What order costs, proved
Q
- Quantization with error bounds: Geometry and high-dimensional search › Rotate, then round
R
- Range tree: Geometry and high-dimensional search › Everything between two streets
- Rank and select: Search › Order queries
- Red-black tree, as a set of promises: Contracts and cost models › Invariants
- Red-black tree, standard: Search › Appendix: how the standard red-black tree relates to the left-leaning
- Regular expressions: speed and proof: Strings › The search that takes a site down
- Repetitive collections and dynamic indexes: Strings › A thousand copies of almost the same book
- Rotation (rotate left, rotate right): Search › Insertion: rotations and color flips
- RUM conjecture: Search › Costs; Search › Cost trade-offs and the RUM conjecture
S
- Scanning and rolling fingerprints: Strings › Reading the whole book, every time
- Searching with borders: Knuth–Morris–Pratt and Aho–Corasick: Strings › When two numbers agree by accident
- Semantic search, in one paragraph: Strings › Finding what it means, not what it says
- Sequential search: Search › Checking one place at a time
- SimHash: Geometry and high-dimensional search › One random cut, one bit
- Skip list: Search › Self-adjusting and learned structures
- Sorted array: Search › An orderly key ring
- Sorting lower bound: Contracts and cost models › Why no sort can be faster
- Splay tree: Search › Self-adjusting and learned structures
- SSTable: Search › Writing
- Strongly connected components: Graph structure and decomposition › Nobody moves until somebody does
- Suffix array and LCP: Strings › It was somewhere in the middle
- Suffix structures in language model decoding: Strings › The model that searches its own past
T
- Tango tree: Search › Self-adjusting and learned structures
- Task graphs in AI systems: Graph structure and decomposition › Plans that machines draw
- Text indexes: count, locate, extract: Strings › What is this all about?
- Tokenization: Strings › How a language model reads
- Topological order: Graph structure and decomposition › Who can confirm first?
- Treap: Search › Self-adjusting and learned structures
- Trie and Patricia tree: Strings › I remember how it starts
U
- Union by rank: Graph structure and decomposition › Trees that stay shallow
- Union-find: Graph structure and decomposition › Have you two met?
V
- van Emde Boas layout: Search › Appendix: cache-oblivious variant
- Voronoi diagram: Geometry and high-dimensional search › A map of who is nearest
W
- Weighing puzzle (balance scale): Contracts and cost models › Nine balls and a balance scale
- Weight-balanced tree: Search › What “balanced” is allowed to mean
- Wheeler graphs: Strings › When there is no single text
- Where this may be going: Strings › Could the machine choose the pieces?; Geometry and high-dimensional search › Could the machine choose the neighbors?
- Write-ahead log: Search › Write-ahead log