What Is a Trie?•Searching a Trie•Keys with Different Length•Height of a Trie•Space Required and Alternative Node Structures•Inserting into a Trie•Removing an Element•Prefix Search and Applications•Compressed Tries•Patricia•Acknowledgments•References
30Suffix Trees and Suffix Arrays Srinivas Aluru
Basic Definitions and Properties•Linear Time Construction Algorithms•Applications•Lowest Common Ancestors•Advanced Applications•Acknowledgments•References
31String Searching Andrzej Ehrenfeucht and Ross M. McConnell
Introduction•Preliminaries•The DAWG•The Compact DAWG•The Position Heap•References
32Binary Decision Diagrams Shin-ichi Minato
Introduction•Basic Concepts•Data Structure•Construction of BDDs from Boolean Expressions•Variable Ordering for BDDs•Zero-Suppressed BDDs•Related Research Activities•Acknowledgments•References
33Persistent Data Structures Haim Kaplan
Introduction•Algorithmic Applications of Persistent Data Structures•General Techniques for Making Data Structures Persistent•Making Specific Data Structures More Efficient•Concluding Remarks and Open Questions•Acknowledgments•References
34Data Structures for Sets Rajeev Raman
Introduction•Simple Randomized Set Representations•Equality Testing•Extremal Sets and Subset Testing•The Disjoint Set Union-Find Problem•Partition Maintenance Algorithms•Conclusions•References
35Cache-Oblivious Data Structures Lars Arge, Gerth Stølting Brodal and Rolf Fagerberg
The Cache-Oblivious Model•Fundamental Primitives•Dynamic B-Trees•Priority Queues•2d Orthogonal Range Searching•Acknowledgments•References
36Dynamic Trees Camil Demetrescu, Irene Finocchi and Giuseppe F. Italiano
Introduction•Linking and Cutting Trees•Topology Trees•Top Trees•ET Trees•Reachability Trees•Conclusions•Acknowledgments•References
37Dynamic Graphs Camil Demetrescu, Irene Finocchi and Giuseppe F. Italiano
Introduction•Techniques for Undirected Graphs•Techniques for Directed Graphs•Connectivity•Minimum Spanning Tree•Transitive Closure•All-Pairs Shortest Paths•Conclusions•Acknowledgments•References
38Succinct Representation of Data Structures J. Ian Munro and S. Srinivasa Rao
Introduction•Bitvector•Succinct Dictionaries•Tree Representations•Graph Representations•Succinct Structures for Indexing•Permutations and Functions•Partial Sums•ArraysConclusions•References
39Randomized Graph Data-Structures for Approximate Shortest Paths Surender Baswana and Sandeep Sen
Introduction•A Randomized Data-Structure for Static APASP: Approximate Distance Oracles•A Randomized Data-Structure for Decremental APASP•Further Reading and Bibliography•Acknowledgments•References
40Searching and Priority Queues in o(log n) Time Arne Andersson
Introduction•Model of Computation•Overview•Achieving Sub-Logarithmic Time per Element by Simple Means•Deterministic Algorithms and Linear Space•From Amortized Update Cost to Worst-Case•Sorting and Priority Queues•References