Introduction•Hash Tables for Integer Keys•Random Probing•Historical Notes•Other Developments•Acknowledgments•References
10Bloom Filter and Its Variants Shigang Chen
Introduction•Bloom Filter•Counting Bloom Filter•Blocked Bloom Filter•Other Bloom Filter Variants•Summary•References
11Balanced Binary Search Trees Arne Andersson, Rolf Fagerberg and Kim S. Larsen
Introduction•Basic Definitions•Generic Discussion of Balancing•Classic Balancing Schemes•Rebalancing a Tree to Perfect Balance•Schemes with no Balance Information•Low Height Schemes•Relaxed Balance•References
12Finger Search Trees Gerth Stølting Brodal
Finger Searching•Dynamic Finger Search Trees•Level Linked (2,4)-Trees•Randomized Finger Search Trees•Applications•Acknowledgments•References
Introduction•Splay Trees•Analysis•Optimality of Splay Trees•Linking and Cutting Trees•Case Study: Application to Network Flows•Implementation without Linking and Cutting Trees•FIFO Dynamic Tree Implementation•Variants of Splay Trees and Top-Down Splaying•Acknowledgments•References
14Randomized Dictionary Structures C. Pandu Rangan
Introduction•Preliminaries•Skip Lists•Structural Properties of Skip Lists•Dictionary Operations•Analysis of Dictionary Operations•Randomized Binary Search Trees•Bibliographic Remarks•References
15Trees with Minimum Weighted Path Length Wojciech Rytter
Introduction•Huffman Trees•Height Limited Huffman Trees•Optimal Binary Search Trees•Optimal Alphabetic Tree Problem•Optimal Lopsided Trees•Parallel Algorithms•References
Introduction•The Disk-Based Environment•The B-tree•The B+-tree•Further Discussions• References