Handbook of Data Structures and Applications

✍ Scribed by Mehta, Dinesh P(Editor)

• Publisher: CRC Press
• Year: 2004
• Tongue: English
• Leaves: 1387
• Series: Chapman & Hall/Crc Computer and Information Science Series
• Category: Library

✦ Synopsis

Although there are many advanced and specialized texts and handbooks on algorithms, until now there was no book that focused exclusively on the wide variety of data structures that have been reported in the literature. The Handbook of Data Structures and Applications responds to the needs of students, professionals, and researchers who need a mainstream reference on data structures by providing a comprehensive survey of data structures of various types.

Divided into seven parts, the text begins with a review of introductory material, followed by a discussion of well-known classes of data structures, Priority Queues, Dictionary Structures, and Multidimensional structures. The editors next analyze miscellaneous data structures, which are well-known structures that elude easy classification. The book then addresses mechanisms and tools that were developed to facilitate the use of data structures in real programs. It concludes with an examination of the applications of data structures.

The Handbook is invaluable in suggesting new ideas for research in data structures, and for revealing application contexts in which they can be deployed. Practitioners devising algorithms will gain insight into organizing data, allowing them to solve algorithmic problems more efficiently.

✦ Table of Contents

Cover......Page 1
Title......Page 4
Copyright......Page 5
Dedication......Page 6
Preface......Page 8
About the Editors......Page 10
Contributors......Page 12
Contents......Page 16
Part I: Fundamentals......Page 20
Chapter 1: Analysis of Algorithms......Page 22
Chapter 2: Basic Structures......Page 48
Chapter 3 :Trees......Page 64
Chapter 4: Graphs......Page 82
Part II: Priority Queues......Page 108
Chapter 5: Leftist Trees......Page 110
Chapter 6: Skew Heaps......Page 120
Chapter 7: Binomial, Fibonacci, and Pairing Heaps......Page 130
Chapter 8: Double-Ended Priority Queues......Page 150
Part III: Dictionary Structures......Page 174
Chapter 9: Hash Tables......Page 176
Chapter 10: Balanced Binary Search Trees......Page 196
Chapter 11: Finger Search Trees......Page 224
Chapter 12: Splay Trees......Page 236
Chapter 13: Randomized Dictionary Structures......Page 260
Chapter 14: Trees with Minimum Weighted Path Length......Page 282
Chapter 15: B Trees......Page 306
Part IV: Multidimensional and Spatial Structures......Page 328
Chapter 16: Multidimensional Spatial Data Structures......Page 330
Chapter 17: Planar Straight Line Graphs......Page 360
Chapter 18: Interval, Segment, Range, and Priority Search Trees......Page 378
Chapter 19: Quadtrees and Octrees......Page 400
Chapter 20: Binary Space Partitioning Trees......Page 426
Chapter 21: R-trees......Page 446
Chapter 22: Managing Spatio-Temporal Data......Page 470
Chapter 23: Kinetic Data Structures......Page 490
Chapter 24: Online Dictionary Structures......Page 508
Chapter 25: Cuttings......Page 520
Chapter 26: Approximate Geometric Query Structures......Page 530
Chapter 27: Geometric and Spatial Data Structures in External Memory......Page 548
Part V: Miscellaneous Data Structures......Page 582
Chapter 28: Tries......Page 584
Chapter 29: Suffix Trees and Suffix Arrays......Page 604
Chapter 30: String Searching......Page 626
Chapter 31: Persistent Data Structures......Page 650
Chapter 32: PQ Trees, PC Trees, and Planar Graphs......Page 676
Chapter 33: Data Structures for Sets......Page 704
Chapter 34: Cache-Oblivious Data Structures......Page 726
Chapter 35: Dynamic Trees......Page 754
Chapter 36: Dynamic Graphs......Page 772
Chapter 37: Succinct Representation of Data Structures......Page 792
Chapter 38: Randomized Graph Data-Structures for Approximate Shortest Paths......Page 814
Chapter 39: Searching and Priority Queues in o(log n) Time......Page 834
Part VI: Data Structures in Languages and Libraries......Page 848
Chapter 40: Functional Data Structures......Page 850
Chapter 41: LEDA, a Platform for Combinatorial and Geometric Computing......Page 868
Chapter 42: Data Structures in C++......Page 886
Chapter 43: Data Structures in JDSL......Page 904
Chapter 44: Data Structure Visualization......Page 926
Chapter 45: Drawing Trees......Page 940
Chapter 46: Drawing Graphs......Page 960
Chapter 47: Concurrent Data Structures......Page 982
Part VII: Applications......Page 1012
Chapter 48: IP Router Tables......Page 1014
Chapter 49: Multi-Dimensional Packet Classification......Page 1038
Chapter 50: Data Structures in Web Information Retrieval......Page 1058
Chapter 51: The Web as a Dynamic Graph......Page 1066
Chapter 52: Layout Data Structures......Page 1082
Chapter 53: Floorplan Representation in VLSI......Page 1102
Chapter 54: Computer Graphics......Page 1132
Chapter 55: Geographic Information Systems......Page 1150
Chapter 56: Collision Detection......Page 1172
Chapter 57: Image Data Structures......Page 1192
Chapter 58: Computational Biology......Page 1210
Chapter 59: Elimination Structures in Scientific Computing......Page 1228
Chapter 60: Data Structures for Databases......Page 1258
Chapter 61: Data Mining......Page 1280
Chapter 62: Computational Geometry: Fundamental Structures......Page 1302
Chapter 63: Computational Geometry: Proximity and Location......Page 1322
Chapter 64: Computational Geometry: Generalized Intersection Searching......Page 1344
Index......Page 1362

✦ Subjects

Computer Science;Programming