Advanced Data Structures

Advanced Data Structures presents a comprehensive look at the ideas, analysis, and implementation details of data structures as a specialized topic in applied algorithms. Data structures are how data is stored within a computer, and how one can go about searching for data within. This text examines efficient ways to search and update sets of numbers, intervals, or strings by various data structures, such as search trees, structures for sets of intervals or piece-wise constant functions, orthogonal range search structures, heaps, union-find structures, dynamization and persistence of structures, structures for strings, and hash tables. This is the first volume to show data structures as a crucial algorithmic topic, rather than relegating them as trivial material used to illustrate object-oriented programming methodology, filling a void in the ever-increasing computer science market. Numerous code examples in C and more than 500 references make Advanced Data Structures an indispensable text. topic. Numerous code examples in C and more than 500 references make Advanced Data Structures an indispensable text.

User review
comprehensive and concise
Brass' book is the most comprehensive and up-to-date text about data structures I know. As a reference on data structures I consider it much better than, e.g.,the standard textbook on algorithms by Cormen et al., because it is much more concise and at the same time mathematically rigorous. The comparison of a previous reviewer with Knuth's classic `The Art of Computer Programming` is of course absurd. Knuth's books are indeed worth reading and have the unique merit of having laid the foundations for the whole area of algorithmics. But those books are 40 years old and do not cover any of the important developments in the area of data structures within the last decades. Brass' book does that including self-organizing data structures, data structures for geometric problems, and the recently, because of applications in computational genetics, very important area of data structures for strings, like suffix trees etc.

One has to get used to the C++ code, but on the other hand it can be considered as a documentation of all the implementation details which normally are not found in textbooks on data structures.

User review
A much-needed monograph
Although programming texts on the topic of data structures are somewhat ubiquitous, Peter Brass's `Advanced Data Structures` is the only recent monograph giving a comprehensive treatment of the topic's algorithmic considerations. The main focus is on fundamental pointer machine data structures: height- and weight-balanced search trees, interval trees, orthogonal range trees, but hashing and string-based data structures are also covered. I see this book as filling the same role for data structures that Motwani & Raghavan's does for randomized algorithms: as both an advanced text and standard reference for an important class of theoretical techniques.

All the data structures presented are analyzed in detail, and presented in a unified perspective. The exposition is clear and self-contained, which makes this book an excellent for an advanced undergraduate or graduate-level course. In addition, implementations in C are provided, with the code available from the author's site.

A special treat for the researcher is the extensive bibliography and detailed citations throughout the text, which make this book an extremely useful guide to the state-of-the art in data structures for the non-specialist.