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.

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