Advanced Data Structures

Citation

Brass, P. (2008). Advanced Data Structures. Cambridge University Press.

Chapter Summary

The book has nine chapters of content, an appendix chapter, a reference list of more than 500 entries and author and subject indexes, in 474 pages. Cambridge describes it as a close look at the ideas, analysis and implementation of data structures as a specialised topic in applied algorithms, with numerous code examples in C.

Chapter 1: Elementary Structures

Stack, queue, double-ended queue, dynamical allocation of nodes and shadow copies of array-based structures. These are the most elementary topics in the book and prepare for the array-based and node-based implementations used later.

Chapter 2: Search Trees

Two models of search trees, general properties and transformations, the height of a search tree, and the basic find, insert and delete operations. It also covers returning from leaf to root, nonunique keys, interval queries, building optimal search trees, converting trees into lists and removing a tree.

Chapter 3: Balanced Search Trees

The longest chapter on a single family: height-balanced and weight-balanced trees, (a, b)- and B-trees, red-black trees and trees of almost optimal height, top-down rebalancing, trees with constant update time at a known location, finger trees and level linking, partial rebuilding with amortized analysis, splay trees, skip lists, and joining and splitting balanced trees.

Chapter 4: Tree Structures for Sets of Intervals

Interval trees, segment trees, trees for the union of intervals, for sums of weighted intervals and for interval-restricted maximum sum queries, then orthogonal range trees, higher-dimensional segment trees, other systems of building blocks, range counting and the semigroup model, and kd-trees.

Chapter 5: Heaps

Starts from balanced search trees used as heaps and array-based heaps, then heap-ordered and half-ordered trees, leftist, skew and binomial heaps, changing keys, Fibonacci heaps, heaps of optimal complexity, double-ended and multidimensional heaps, and heap-related structures with constant-time updates.

Chapter 6: Union-Find and Related Structures

Union-find for merging classes of a partition, union-find with copies and dynamic segment trees, list splitting, problems on root-directed trees and maintaining a linear order.

Chapter 7: Data Structure Transformations

General techniques for making structures dynamic and for making structures persistent.

Chapter 8: Data Structures for Strings

Tries and compressed tries, dictionaries allowing errors in queries, suffix trees and suffix arrays.

Chapter 9: Hash Tables

Basic hash tables and collision resolution, universal families of hash functions, perfect hash functions, hash trees, extendible hashing, and membership testers and Bloom filters.

Chapter 10: Appendix

The pointer machine and alternative computation models, external memory models and cache-oblivious algorithms, the naming of data structures, solving linear recurrences, and very slowly growing functions.

Key Concepts

Chapters 1–3: Elementary and balanced structures

• Shadow copies and node allocation: implementation techniques for the basic structures.
• Balance criteria: height-balanced, weight-balanced, (a, b) and red-black trees as different ways to keep a tree shallow.
• Amortized analysis, splay trees and skip lists: adaptive and randomized alternatives to explicit balancing.

Chapters 4–6: Intervals, heaps and union-find

• Segment trees, interval trees and range trees: structures for queries on intervals and multidimensional point sets.
• Heap variants: leftist, skew, binomial and Fibonacci heaps.
• Union-find: merging classes of a partition efficiently.

Chapters 7–9: Transformations, strings and hashing

• Dynamization and persistence: general transformations that add update ability or retain old versions.
• Tries, suffix trees and suffix arrays: structures for sets of strings.
• Universal and perfect hashing; Bloom filters: hash-based structures with guarantees or approximate membership.

Critical Analysis

Strengths

• Data structures as an algorithmic topic. Cambridge presents the book as the first to treat the subject as a crucial algorithmic topic rather than as trivial material for illustrating object-oriented programming.
• Breadth beyond the standard course. Interval and range structures, a long heap chapter, union-find variants, persistence and dynamization, string structures and several hashing schemes appear in one volume, with more than 500 references into the literature.
• Code and diagrams. A reviewer in Software Engineering Notes (Igor Gvero) describes the book as packed with illustrations, diagrams and code that aim to explain one of the harder subjects in computer science clearly; the publisher notes numerous code examples in C.
• Suitable as text and reference. A SIGACT News review judged it well suited as a main or supplemental text for a graduate data structures course and as a desk reference for implementers.

Limitations

• Uneven entry point. Chapter 1 is introductory, but from Chapter 2 on, the table of contents uses vocabulary (amortized analysis, optimal search trees, semigroup model, cache-oblivious algorithms) that presupposes an algorithms course.
• Imperative focus. The code examples are in C; structures designed for immutable data are outside the contents, so functional implementations need another book.
• A reference rather than a gentle sequence. Chapters 3 and 5 list a dozen or more variants each, so a reader may need to pick selected sections instead of reading straight through.

Where It Fits in the Course

Brass is the graduate-level, breadth-first text in this course. Wengrow's A Common-Sense Guide to Data Structures and Algorithms and Bhargava's Grokking Algorithms are gentle starting points for programmers without formal computer science background. Goodrich, Tamassia and Goldwasser's Data Structures and Algorithms in Java is a second-course textbook, and Morin's Open Data Structures presents each structure with a precise interface, an implementation and a proof of its running-time bounds; either is a sensible preparation for Brass.

Okasaki's Purely Functional Data Structures covers a different branch of the subject, persistent structures in functional languages with lazy evaluation, and pairs naturally with Brass's Chapter 7 on persistence.

How to Use This Book

The book is meant for readers who have already met stacks, queues, trees, hashing and asymptotic analysis, and who can read C code. It serves a graduate course, self-study for implementers, or a reference when a standard library structure is not enough.

A practical plan:

• Core: Chapters 2 and 3 (search trees and the main balanced-tree families), then Chapter 5 (heaps) and Chapter 9 (hash tables).
• Selected topics: Chapter 4 for geometry or database interests, Chapter 6 for graph algorithms that need union-find, and Chapter 8 for string processing.
• Techniques: Chapter 7 after the structures it transforms.
• Appendix: Read Section 10.1 on the pointer machine and other computation models before comparing bounds across chapters.

Implement at least one structure per chapter in C, since the book's presentation is built around implementation detail.