Peter Brass — Advanced Data Structures — Cambridge University Press, 2008, 492 pp. ISBN 978-0521-88037-4
The first part of the book concentrates on search trees and variants, whether balanced trees, interval trees, or heaps. Chapters are dedicated to connected components and like algorithms, one to algorithms for strings, and one for hash tables. Follows appendices on computation, cache oblivious algorithms, etc.
The book is of higher level than most books on the subject. While he does not dwelve endlessly through proofs and demonstrations; he does present them and offer plenty of references so that the reader can pursue a particular interest if he needs or wants to.
What’s original about this book, respective to other introductory texts on data structures that I know, is the tone of the narrative. Brass uses a relaxed style that assumes he’s writing for smart readers; he so subtly brings us to conclusions that we are tricked into thinking we thought about them ourselves. I find this most refreshing.
There’s code in the book—and quite a lot—but the code corresponds to relatively naïve implementation examples; clearly not ready for production-level code. However, these implementations are well thought out as they will help the reader fill any gaps in his understanding of the matter at hand without having to fight implementation details.