Handbook of Data Structures and Applications, 2nd Edition

III

Dictionary Structures

9Hash Tables Pat Morin

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 ...