Handbook of Data Structures and Applications: (Chapman & Hall/CRC Computer and Information Science Series)

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:
Fundamentals Analysis of Algorithms Sartaj Sahni University of Florida, Gainesville, USA Basic Structures Dinesh P. Mehta Colorado School of Mines, Golden, Colorado, USA Trees Dinesh P. Mehta Graphs Narsingh Deo University of Central Florida, Orlando, USA Priority Queues Leftist Trees Sartaj Sahni Skew Heaps C. Pandu Rangan Indian Institute of Technology, Madras, Chennai Binomial, Fibonacci, and Pairing Heaps Michael L. Fredman Rutgers University, New Brunswick, New Jersey, USA Double-Ended Priority Queues Sartaj Sahni Dictionary Structures Hash Tables Pat Morin Carleton University, Ottawa, Ontario, Canada Balanced Binary Search Trees Arne Andersson, Uppsala University, Sweden Rolf Fagerberg and Kim S. Larsen, University of Southern Denmark, Odense Finger Search Trees Gerth Stølting Brodal University of Aarhus, Denmark Splay Trees Sanjeev Saxena Indian Institute of Technology, Kanpur Randomized Dictionary Structures C. Pandu Rangan Trees with Minimum Weighted Path Length Wojciech Rytter New Jersey Instituteof Technology, Newark, USA B. Trees Donghui Zhang Northeastern University, Boston, Massachusetts, USA Multidimensional and Spatial Structures Multidimensional Spatial Data Structures Hanan Samet University of Maryland, College Park, USA Planar Straight Line Graphs Siu-Wing Cheng The Hong Kong University of Science and Technology, Kowloon Interval, Segment, Range, and Priority Search Trees D. T. Lee Academia Sinica, Taipei, Taiwan Quadtrees and Octrees Srinivas Aluru Iowa State University, Ames, USA Binary Space Partitioning Trees Bruce F. Naylor University of Texas, Austin, USA R-Trees Scott Leutenegger and Mario A. Lopez University of Denver, Colorado, USA Managing Spatio-Temporal Data Sumeet Dua Louisiana Tech University, Ruston, USA S. S. Iyengar Louisiana State University, Baton Rouge, USA Kinetic Data Structures Leonidas Guibas Stanford University Palo Alto, California, USA Online Dictionary Structures Teofilo F. Gonzalez University of California, Santa Barbara, USA Cuttings Bernard Chazelle Princeton University, Princeton, New Jersey, USA Approximate Geometric Query Structures Christian A. Duncan University of Miami, Florida, USA Michael T. Goodrich University of California, Irvine, USA Geometric and Spatial Data Structures in External Memory Jeffrey Scott Vitter Purdue University West Lafayette, Indiana, USA Miscellaneous Data Structures Tries Sartaj Sahni Suffix Trees and Suffix Arrays Srinivas Aluru String Searching Andrzej Ehrenfeuch University of Colorado, Boulder, USA Ross M. McConnell Colorado State University, Fort Collins, USA Persistent Data Structures Haim Kaplan Tel Aviv University, Israel PC Trees Wen-Lian Hsu Academia Sinica, Taipei, Taiwan Ross M. McConnell Data Structures for Sets Rajeev Raman University of Leicester, UK Cache-Oblivious Data Structures Lars Arge Duke University, Durham, North Carolina, USA, Gerth Stølting Brodal University of Aarhus, Denmark Rolf Fagerberg Dynamic Trees Camil Demetrescu, Irene Finocchi, and Giuseppe F. Italiano Universitá di Roma, Italy Dynamic Graphs Camil Demetrescu, Irene Finocchi, and Giuseppe F. Italiano Succinct Representation of Data Structures J. Ian Munro and S. Srinivasa Rao University of Waterloo, Ontario, Canada Randomized Graph Data-Structures for Approximate Shortest Paths Surender Baswana and Sandeep Sen Indian Institute of Technology, Delhi, India Searching and Priority Queues in o(log n) Time Arne Andersson Data Structures in Languages and Libraries Functional Data Structures Chris Okasaki United States Military Academy, West Point, New York LEDA, a Platform for Combinatorial and Geometric Computing Stefan Naeher University of Trier, Germany Data Structures in C++ Mark Allen Weiss Florida International University, Miami, USA Data Structures in JDSL Michael T. Goodrich Roberto Tamassia, and Luca Vismara Brown University, Providence, Rhode Island, USA Data Structure Visualization John Stasko Georgia Institute of Technology, Atlanta, USA Drawing Trees Sebastian Leipert Center of Advanced European Studies and Research, Bonn, Germany Drawing Graphs Peter Eades and Seok-Hee Hong University of Sydney and NICTA, Australia Concurrent Data Structures Mark Moir and Nir Shavit Sun Microsystems Laboratories, Burlington, Massachusetts, USA Applications IP Router Tables Sartaj Sahni Kun Suk Kim and Haibin Lu University of Florida, Gainesville, USA Multi-Dimensional Packet Classification Pankaj Gupta Cypress Semiconductor, San Jose, California, USA Data Structures in Web Information Retrieval Monika Henzinger Google, Inc., Mountain View, California, USA The Web as a Dynamic Graph S.N.Maheshwari Indian Institute of Technology, Madras, Chennai Layout Data Structures Dinesh P. Mehta Floorplan Representation in VLSI Zhou Fen Fudan University, Shanghai, China Bo Yao, and Chung-Kuan Cheng University of California, San Diego Computer Graphics Dale McMullin and Alyn Rockwood Colorado School of Mines, Golden, USA Geographic Information Systems Bernhard Seeger University of Marburg, Germany Peter Widmayer ETH, Zurich, Switzerland Collision Detection Ming C. Lin and Dinesh Manocha University of North Carolina, Chapel Hill, USA Image Data Structures S. Sitharama Iyengar V. K. Vaishnavi Georgia State University, Atlanta, USA S. Gunasekaran Louisiana State University, Baton Rouge, USA Computational Biology Stefan Kurtz University of Hamburg, Germany Stefano Lonardi University of California, Riverside, USA Elimination Structures in Scientific Computing Alex Pothen Old Dominion University, Norfolk, Virginia, USA Sivan Toledo Tel Aviv University, Israel Data Structures for Databases Joachim Hammer and Markus Schneider University of Florida, Gainesville, USA Data Mining Vipin Kumar and Michael Steinbach University of Minnesota, Minneapolis, USA Pang-Ning Tan Michigan State University, East Lansing, USA Computational Geometry: Fundamental Structures Mark de Berg and Bettina Speckmann Technical University, Eindhoven, The Netherlands Computational Geometry: Proximity and Location Sunil Arya The Hong Kong University of Scienceand Technology, Kowloon David M. Mount University of Maryland, College Park, USA Computational Geometry: Generalized Intersection Searching Prosenjit Gupta International Institute of Information Technology, Hyderabad, India Ravi Janardan University of Minnesota, Minneapolis, USA Michiel Smid Carleton University, Ottawa, Ontario, Canada