Algorithms in C++, Parts 1–4 (Sedgewick, 3rd edition)
The original Addison-Wesley edition separates abstract operations from representations and develops linked structures, linear containers, trees, heaps, ordered symbol tables, balanced trees, skip lists, and radix string indexes. GTK pairs that durable organization with original data-structure papers and current language standards.
Robert Sedgewick's Algorithms in C++, Third Edition, Parts 1–4: Fundamentals, Data Structures, Sorting, Searching was published by Addison-Wesley Professional in 1998, with a 1999 copyright and ISBN 978-0-201-35088-3. The library record points to the publisher's original English edition; no translated copy is archived.
Durable contribution #
The book treats an abstract operation and its representation as separate decisions. A queue remains FIFO whether backed by a ring buffer or linked nodes; a priority queue is a contract before it is a heap; a symbol table must declare duplicate-key, absence, order, and iteration behavior before choosing a tree or table.
Its mechanism-first organization remains useful across several structures:
- linked-list updates are bounded rewrites of local links;
- tree rotations preserve inorder order while changing height;
- heap repair changes one root-to-leaf path;
- balanced trees trade additional invariants for logarithmic height;
- skip lists replace deterministic rebalancing with probabilistic levels;
- tries, PATRICIA, and ternary search tries compress different forms of prefix sparsity.
GTK does not use the edition as present-day C++ authority. Container contracts come from the current C++ working draft; balanced-tree, heap, skip-list, and trie mechanisms are supported by their original papers; Unicode sources control modern string-unit and normalization semantics.
Coverage boundary #
The retained GTK mapping covers abstract data types, linked structures, stacks and queues, tree representations and traversals, heaps and priority queues, ordered symbol tables and balanced trees, and trie-family string structures. Language-era allocation idioms, byte-equals-character assumptions, obsolete benchmark constants, and implementation advice that omits current ownership, invalidation, exception, or concurrency contracts are outside the source's evidentiary role.