Rooted¶

Trees and graphs in C++23, from first principles to production.

Most data-structure courses teach you what a binary search tree is, then hand you a diagram and a proof. This one teaches you why the node is shaped that way, what it costs in a cache, how you know it is still correct after a deletion, and what it looks like when it rotates. You build one C++23 workbench, atlas, chapter by chapter, and every structure you meet becomes a drawer in it.

By the last chapter you will have:

a library of roughly twenty-five tree and graph structures, written from scratch — not wrapped around someone else's container;
the algorithms that top courses actually teach: traversals, balancing, priority queues, tries, B+ trees, range indexes, suffix structures, spatial indexes, BFS/DFS, topological order, union-find, MST, shortest paths, SCC, flow, matching, LCA, persistence, and dynamic connectivity;
a test suite that checks invariants and compares behavior against the standard library;
a benchmark suite that measures cost instead of asserting it;
a DOT/SVG visualization pipeline, with an interactive viewer in the final part;
seven optional studios: an expression language, a game world, an exchange, a search engine, a mission planner, a versioned filesystem, and a visualizer.

Start Chapter 1: The Workbench See the roadmap

The method¶

Every structure is examined through the same five questions:

Question	What it means
Contract	What operations exist, what do they mean, what can fail?
Invariant	What one sentence makes every operation correct, and why does it survive?
Representation	How does it sit in memory: ownership, layout, indices, cache lines?
Cost	Time, space, cache, worst/amortized/expected — measured, not asserted.
Evidence	What tests, benchmarks, and pictures prove the first four?

That is the difference between a book that surveys algorithms and a book that teaches you to engineer them. The algorithm is the easy part once you can see the invariant and measure the cost.

The shape of the course¶

Seven parts, thirty-six chapters, written one at a time. Every chapter ends with a program that builds and runs.

Part	Chapters	Theme
I — Foundations	1–5	Contract, cost, traversal, memory, the search-tree contract
II — Balanced search trees	6–10	Height, color, augmentation, amortization, randomness
III — Trees as machines	11–18	Priority, coding, strings, storage, ranges, space
IV — Graphs: structure	19–22	Representation, exploration, connectivity, order
V — Graphs: optimization	23–27	Spanning, shortest paths, all-pairs, SCC, flow
VI — Advanced structures	28–31	Tree queries, dynamic graphs, persistence, succinct indexes
VII — Craft and capstone	32–36	Testing, performance, visualization, hard graphs, a capstone

The studios¶

The chapters build the library. The studios build something you can show someone, using the library. They are optional, two to four hours each, and they are where the domain scenarios live:

Calc — a small expression language with an AST, a constant folder, and an SVG tree view.
Exchange — a limit order book with a price ladder, matching, rank queries, and a depth chart.
Pack & Find — a mini search engine: Huffman-compressed dictionary, trie autocomplete, and a B+tree range index.
World — a 512×512 game world with 10,000 units, lazy quadtree terrain, union-find regions, and a naive-versus-indexed mass-update benchmark.
Mission — a space network planner with MST, A*, and max-flow.
Time — a versioned filesystem with persistent snapshots and LCA path queries.
See — an interactive step-through visualizer for every structure in the library.

The recommended first three are World, Exchange, and See.

Who this is for¶

You should be comfortable with C++ classes, std::vector, references, and basic templates. You do not need to have implemented a balanced tree before. You should be willing to type the code by hand: the complete listings are a safety net, not the primary path. The course assumes macOS and a current Homebrew LLVM, but the code is portable C++23.

If you are new to C++ itself, the first part will be steep. The book explains each new idiom where it earns its keep, but it does not teach the language from zero. A short C++ toolkit appendix is planned.

How to read it¶

One chapter per sitting. The chapters are designed for 60–120 minutes, including typing and the checkpoint.
Type the code. Read the compiler errors. The errors are part of the lesson.
Run the checkpoint before moving on. A chapter that does not build is not finished.
Do at least the comprehension exercise. The stretch exercise is for the chapter you cannot stop thinking about.
The atlas library is cumulative. If you skip a chapter, later chapters may not compile; the roadmap marks which chapters are core and which are optional depth.