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 the book teaches, alphabetically, with the chapter and the section where it is.
0–9
- 2-3 tree: Search › Where LLRB actually comes from
A
B
- B*-tree: Search › Search, insertion and node splitting
- B+-tree: Search › Search, insertion and node splitting
- B-tree: Search › Frankenstein
- B-tree deletion: Search › Top-down insert and delete
- Balance conditions: Search › What “balanced” is allowed to mean
- 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
- Bloom filter: Search › Bloom filters
- Bubble sort: Contracts and cost models › Slow code or a hard problem?
- 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 › Cache-oblivious variant
- Certifying algorithm: Contracts and cost models › Reference algorithms and certificates
- Compaction: Search › Compaction
- Copy-on-write (path copying): Search › Copy-on-write
- Cuckoo filter: Search › Bloom filters
D
- Decision-tree lower bound: Contracts and cost models › Every weighing, drawn out
F
- Flip colors: Search › Insertion: rotations and color flips
- Floor and ceiling: Search › Order queries
G
- Galloping (exponential) search: Search › Galloping search
H
- HNSW (hierarchical navigable small world): Search › Search without a map
I
- Insertion into a sorted array: Search › Insertion means shoving
L
- 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
- Log-structured merge-tree (LSM-tree): Search › I’ll pay it back later
- Loop invariant: Contracts and cost models › Three tools we reuse
M
- Merge sort: Contracts and cost models › Slow code or a hard problem?
- Merkle tree: Search › Trees that can prove what they hold
N
- Navigable small-world graph: Search › Search without a map
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
- Predecessor lower bound: Search › What order costs, proved
- Predecessor search: Search › What order costs, proved
R
- Rank and select: Search › Order queries
- Red-black tree, as a set of promises: Contracts and cost models › Structures as invariants
- Red-black tree, standard: Search › Appendix: how the standard red-black tree relates to the left-leaning
- Rotation (rotate left, rotate right): Search › Insertion: rotations and color flips
- RUM conjecture: Search › Costs; Search › Cost trade-offs and the RUM conjecture
S
- Sequential search: Search › Checking one place at a time
- 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
T
V
- van Emde Boas layout: Search › Cache-oblivious variant
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
- Write-ahead log: Search › Write-ahead log