Handbook of Data Structures and Applications

Dinesh P. Mehta has been on the faculty of the Colorado School of Mines since 2000, where he is currently professor in the Department of Computer Science. He earned degrees (all in computer science) from the Indian Institute of Technology Bombay, the University of Minnesota, and the University of Florida. Before joining Mines in 2000, he was on the faculty of the University of Tennessee Space Institute, where he received the Vice President’s Award for Teaching Excellence in 1997. He was a visiting professor at Intel’s Strategic CAD Labs for several months in 1996 and 1997 and at the Tata Research Development and Design Center (in Pune, India) in 2007. He has also received graduate teaching awards at Mines in 2007, 2008, and 2009. He was assistant department head from 2004 to 2008 and interim department head from 2008 to 2010 in the former Department of Mathematical and Computer Sciences and served as president of the Mines Faculty Senate in 2016–2017. Dr. Mehta is the coauthor of the book, Fundamentals of Data Structures in C++ and coeditor of the Handbook of Algorithms for VLSI Physical Design Automation. He serves as associate director of the ORwE (Operations Research with Engineering) PhD program at Mines and is currently an associate editor of ACM Computing Surveys. His current research interests are in cheminformatics, computational materials, and big graph analytics. Sartaj Sahni is a distinguished professor of computer and information sciences and engineering at the University of Florida. He is also a member of the European Academy of Sciences, a Fellow of IEEE, ACM, AAAS, and Minnesota Supercomputer Institute, and a distinguished alumnus of the Indian Institute of Technology, Kanpur. Dr. Sahni is the recipient of the 1997 IEEE Computer Society Taylor L. Booth Education Award, the 2003 IEEE Computer Society W. Wallace McDowell Award, and the 2003ACMKarl Karlstrom Outstanding Educator Award. Dr. Sahni earned his BTech (electrical engineering) degree from the Indian Institute of Technology, Kanpur, and MS and PhD in computer science from Cornell University. Dr. Sahni has published over 400 research papers and written 15 books. His research publications are on the design and analysis of efficient algorithms, parallel computing, interconnection networks, design automation, and medical algorithms. Dr. Sahni is the editor-in-chief of the ACM Computing Surveys, a managing editor of the International Journal of Foundations of Computer Science, and a member of the editorial boards of 17 other journals. He is a past coeditor-in-chief of the Journal of Parallel and Distributed Computing. He has served as program committee chair, general chair, and a keynote speaker at many conferences. Dr. Sahni has served on several NSF (National Science Foundation) and NIH (National Institutes of Health) panels and he has been involved as an external evaluator of several computer science and engineering departments.

Part 1: Introduction 1. Analysis of Algorithms 2. Basic Structures 3. Trees 4. Graphs Part 2: Priority Queues 5. Leftist Trees 6. Skew Heaps 7. Binomial, Fibonacci,and Pairing Heaps 8. Double-Ended Priority Queues Part 3: Dictionary Structures 9. Hash Tables 10. Bloom Filter and Its Variants 11. Balanced Binary Search Trees 12. Finger Search Trees 13. Splay Trees 14. Randomized Dictionary Structures 15. Trees with Minimum Weighted Path Length 16. B Trees Part 4: Multidimensional/Spatial Structures 17. Multidimensional Spatial Data Structs 18. Planar Straight Line Graphs 19. Interval, Segment, Range, and Priority Search Trees 20. Quadtrees and Octrees 21. Binary Space Partitioning Trees 22. R-trees 23. Multidimensional and Spatial Structures 24. Kinetic Data Structures 25. Online Dictionary Structures 26. Cuttings 27. Approximate Geometric Query Structures 28. Geometric and Spatial Data Structures in External Memory Part 5: Miscellaneous 29. Tries 30. Suffix Trees and Suffix Arrays 31. String Search 32. Binary Decision Diagrams 33. Persistent Data Structures 34. Data Structures for Sets 35. Cache-Oblivious Data Structures 36. Dynamic Trees 37. Dynamic Graphs 38. Succinct Representation of Data Structures 39. Randomized Graph Data-Structures for Approximate Shortest Paths 40.Searching and Priority Queues in o(log n) Time Part 6: Data Structures in Langs & Libraries 41. Functional Data Structures 42. LEDA, a Platform for Combinatorial and Geometric Computing 43. Data Structures in C++44. Data Strauctures in JDSL 45. Data Structure Visualization 46. Drawing Trees 47. Drawing Graphs 48. Concurrent Data Structures Part 7: Applications 49. IP Router Tables 50. Multi-Dimensional Packet Classification 51. Data Structures in Web Information Retrieval 52. The Web as a Dynamic Graph 53. Layout Data Structures (Dinesh P. Mehta) 54. Floorplan Representation in VLSI 55. Computer Graphics 56. Geographic Information Systems 57. Collision Detection 58. Image Data Structures 59. Computational Biology 60. Data Structures for Cheminformatics 61. Elimination Structures in Scientific 62. Data Structures for Databases 63. Data Structures for Big Data Stores 64. Data Mining 65. Computational Geometry: Fundamental Structures 66. Computational Geometry: Proximity and Location 67. Computational Geometry: Generalized (or Colored) Intersection Searching