About the Book
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
