Reference

Use this page only when a concept page has failed you. The primary path is concept page -> practice -> quiz; reference is the rescue path.

Source Roles

• CLRS (primary): canonical proofs for red-black trees, union-find, amortized analysis, dynamic tables. Use when you need a theorem with a proof, not a recipe.
• Sedgewick: implementation-first companion. Useful when CLRS pseudocode is ambiguous and you want concrete pointer manipulations.
• Skiena: pragmatic decisions. Use to choose between competing structures for an engineering situation, or to quickly survey what exists.
• Competitive Programming (Halim & Halim): contest-shaped recipes for union-find, segment tree, Fenwick tree. Use when you need a working implementation fast.
• Grokking Algorithms: low-floor re-entry. Use on days your brain refuses to work; come back later for the formal text.
• Papers / lectures (external): only for topics the book stack genuinely lacks - Fibonacci heaps, skip lists, pairing heaps, persistence, succinct/cache-oblivious structures.

Read This Only If Stuck - by Cluster

Cluster 1 - Balanced BSTs

• Stuck on red-black rotations or fix-up cases:
  • CLRS 13.2 Rotations
  • CLRS 13.3 Insertion
  • CLRS 13.4 Deletion
  • Sedgewick balanced trees
• Stuck on skip lists:
  • See resources.md -> Pugh 1990 skip list paper.
• Stuck on AVL distinguishing from red-black:
  • Sedgewick balanced trees (2)

Cluster 2 - Union-Find

• Stuck on the naive bound or the operations:
  • CLRS 19.1 Disjoint-set operations
  • CLRS 19.2 Linked-list representation
• Stuck on the alpha(n) analysis:
  • CLRS 19.4 Analysis of union by rank with path compression
  • See resources.md -> Tarjan 1975 paper.
• Stuck on Kruskal:
  • CLRS 21.2 Kruskal and Prim
  • Competitive Programming 4.3 MST

Cluster 3 - Advanced Heaps

• Stuck on what a binomial heap looks like:
  • Sedgewick priority queues
  • See resources.md -> Vuillemin 1978 paper.
• Stuck on why Fibonacci heap is O(1) amortized for decrease-key:
  • See resources.md -> Fredman & Tarjan 1987, MIT OCW 6.046J.
• Stuck on pairing heap:
  • Skiena pairing heap
  • See resources.md -> Fredman, Sedgewick, Sleator, Tarjan 1986.

Cluster 4 - Amortized Analysis

• Stuck on "what does amortized actually promise?":
  • CLRS 16.1 Aggregate analysis
• Stuck on the accounting method:
  • CLRS 16.2 The accounting method
• Stuck on the potential method or the Fibonacci-heap style of argument:
  • CLRS 16.3 The potential method
• Stuck on dynamic tables:
  • CLRS 16.4 Dynamic tables

Cluster 5 - Randomized, Persistent, Succinct

• Stuck on Bloom filter sizing:
  • Grokking Algorithms Chapter 11
  • See resources.md -> Bloom 1970 and hur.st calculator.
• Stuck on segment trees (lazy propagation especially):
  • Competitive Programming 2.4.3 Segment tree
  • See resources.md -> CP-Algorithms segment tree page.
• Stuck on Fenwick trees:
  • Competitive Programming 2.4.4 Fenwick tree
  • See resources.md -> CP-Algorithms Fenwick tree page.
• Stuck on persistence:
  • See resources.md -> Okasaki book and Driscoll et al. 1989 paper.
• Stuck on succinct or cache-oblivious:
  • See resources.md -> Jacobson 1989 and Frigo et al. 1999.

Optional Deep Dive

Read only if the core material is locked.

• Dynamic connectivity with link/cut trees (beyond incremental): Tarjan, Data Structures and Network Algorithms.
• Splay trees as a self-adjusting alternative: Sleator and Tarjan, "Self-Adjusting Binary Search Trees", JACM 1985.
• Persistent red-black trees in Haskell: Okasaki, Purely Functional Data Structures, Chapters 3-4.
• Cache-oblivious B-trees: Bender, Demaine, Farach-Colton, "Cache-Oblivious B-Trees", FOCS 2000.
• Wavelet trees and rank/select: Navarro, Compact Data Structures, 2016.

Concept-to-Source Map

Concept	Primary source	Backup source
01 BST property	CLRS Ch. 12	Sedgewick 055-balanced-trees
02 Red-Black trees	CLRS 13.1-13.4	Sedgewick 055-balanced-trees
03 AVL trees	Sedgewick 056-balanced-trees	external (Knuth TAOCP vol 3)
04 Skip lists	Pugh 1990 (external)	Sedgewick 014-random-numbers
05 Union-Find (naive)	CLRS 19.1-19.2	Competitive Programming 029-2-4-2
06 Rank + path compression	CLRS 19.3-19.4	Tarjan 1975 (external)
07 Kruskal and dynamic connectivity	CLRS 21.2	Competitive Programming 069-4-3
08 Binomial heaps	external (Vuillemin 1978)	Sedgewick 039-priority-queues
09 Fibonacci heaps	external (Fredman-Tarjan 1987)	MIT OCW 6.046J
10 Pairing heaps	external (FSST 1986)	Skiena 286-pairing-heap
11 Why amortized	CLRS Chapter 16 intro	-
12 Aggregate method	CLRS 16.1 + 16.4	-
13 Accounting method	CLRS 16.2 + 16.4	-
14 Potential method	CLRS 16.3 + 16.4	-
15 Randomized DS	Sedgewick 014-random-numbers	Competitive Programming 024-2-3
16 Bloom filters	Grokking Algorithms Ch. 11	Bloom 1970 (external), hur.st calculator
17 Segment / Fenwick	Competitive Programming 030, 031	CP-Algorithms (external)
18 Persistent DS	external (Okasaki, DSST 1989)	-
19 Succinct / cache-oblivious	external (Jacobson 1989, FLPR 1999)	-

When You've Exhausted Everything

If after consulting the concept page, its "stuck" links, and the resources here you are still stuck, escalate in this order:

1. Revisit the prerequisite concept page within the same cluster.
2. Redo the retrieval prompts in the corresponding practice/ page from memory.
3. Pose the specific stuck-point as a single question to a study group or forum.
4. Only then try to skim a second external source; stop after 20 minutes and return to the book.