Handbook of Data Structures and Applications (e-Book) book cover

Handbook of Data Structures and Applications

Edited by Dinesh P. Mehta, Dinesh P. Mehta, Sartaj Sahni

Series Editor: Sartaj Sahni

Contributors: Arne Andersson, S. Sitharama Iyengar, Roberto Tamassia, Alyn R. Rockwood, Giuseppe F. Italiano, Michael T. Goodrich, Ravi Janardan, Hanan Samet, J. Ian Munro, Bernard Chazelle, Leonidas J. Guibas, Ming C. Lin, Srinivas Aluru, Donghui Zhang, Stefano Lonardi, Der Tasi Lee, Camil Demetrescu, Pankaj Gupta, Prosenjit Gupta, Sandeep Sen, Sumeet Dua, Irene Finocchi, Patrick Ryan Morin, Luca Vismara, Ross M. McConnell, Gerth Stolting Brodal, Christian Duncan, Chris Okasaki, Narsingh Deo, Wojciech Rytter, Mark Allen Weiss, Jeffrey Scott Vitter, Mark de Berg, Bettina Speckman, David Mount, Sunil Arya, Stefan Kurtz, Stefan Nahev, Alex Pothen, Haim Kaplan, Mark Moir, Nir Shavit, Scott Leutenegger, Lars A. Arge, John Stasko, Michael Fredman, C. Pandu Rangan, Wen-Lian Hsu, Rajeev Raman, Chung-Kuan Cheng, Peter Eades, Andrzej Ehrenfeucht, Joachim Hammer, Vipin Kumar, S.N. Maheshwari, Dale Robert McMullin, Bruce F. Naylor, Bernhard Seeger, Sebastian Leipert, Kim S. Larsen, Dinesh Manocha, Teofilo F. Gonzalez, Siu-Wing Cheng, Habin Lu, Kun Suk Kim, Michiel Smid, Monika Henzinger, Sanjeev Saxena, Surender Baswana, Zhou Feng, Bo Yao, Rolf Fagerberg, Seok-Hee Hong, Mario A. Lopez, Markus Schneider, Michael Steinbach, Sivan Toledo, Vijay K. Vaishnavi, Peter Widmayer, S. Gunasekaran, S. Srinivasa Rao, Pang-Ning Tang

© 2004 – Chapman and Hall/CRC

1,392 pages | 656 B/W Illus.

This product is not available in your shipping region
FREE Standard Shipping!

Description

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

About the Series

Chapman & Hall/CRC Computer and Information Science Series

Learn more…

Subject Categories

BISAC Subject Codes/Headings:
COM000000
COMPUTERS / General
COM051300
COMPUTERS / Programming / Algorithms
TEC007000
TECHNOLOGY & ENGINEERING / Electrical