Handbook of data structures and applications (Dinesh P. Mehta, Sartaj Sahni (editors))（Z-Library）
,
Data
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.
10
Views
Registered users can read the full content for free
Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.
Page
1
CHAPMAN & HALL/CRC COMPUTER and INFORMATION SCIENCE SERIES Handbook of DATA STRUCTURES and APPLICATIONS © 2005 by Chapman & Hall/CRC
Page
2
PUBLISHED TITLES HANDBOOK OF SCHEDULING: ALGORITHMS, MODELS, AND PERFORMANCE ANALYSIS Joseph Y-T. Leung THE PRACTICAL HANDBOOK OF INTERNET COMPUTING Munindar P. Singh HANDBOOK OF DATA STRUCTURES AND APPLICATIONS Dinesh P. Mehta and Sartaj Sahni FORTHCOMING TITLES DISTRIBUTED SENSOR NETWORKS S. Sitharama Iyengar and Richard R. Brooks SPECULATIVE EXECUTION IN HIGH PERFORMANCE COMPUTER ARCHITECTURES David Kaeli and Pen-Chung Yew CHAPMAN & HALL/CRC COMPUTER and INFORMATION SCIENCE SERIES Series Editor: Sartaj Sahni © 2005 by Chapman & Hall/CRC
Page
3
CHAPMAN & HALL/CRC A CRC Press Company Boca Raton London New York Washington, D.C. CHAPMAN & HALL/CRC COMPUTER and INFORMATION SCIENCE SERIES Edited by Dinesh P. Mehta Colorado School of Mines Golden and Sartaj Sahni University of Florida Gainesville Handbook of DATA STRUCTURES and APPLICATIONS © 2005 by Chapman & Hall/CRC
Page
4
This book contains information obtained from authentic and highly regarded sources. Reprinted material is quoted with permission, and sources are indicated. A wide variety of references are listed. Reasonable efforts have been made to publish reliable data and information, but the author and the publisher cannot assume responsibility for the validity of all materials or for the consequences of their use. Neither this book nor any part may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, microfilming, and recording, or by any information storage or retrieval system, without prior permission in writing from the publisher. All rights reserved. Authorization to photocopy items for internal or personal use, or the personal or internal use of specific clients, may be granted by CRC Press, provided that $1.50 per page photocopied is paid directly to Copyright Clearance Center, 222 Rosewood Drive, Danvers, MA 01923 USA. The fee code for users of the Transactional Reporting Service is ISBN 1-58488-435-5/04/$0.00+$1.50. The fee is subject to change without notice. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. The consent of CRC Press does not extend to copying for general distribution, for promotion, for creating new works, or for resale. Specific permission must be obtained in writing from CRC Press for such copying. Direct all inquiries to CRC Press, 2000 N.W. Corporate Blvd., Boca Raton, Florida 33431. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation, without intent to infringe. © 2005 by Chapman & Hall/CRC No claim to original U.S. Government works International Standard Book Number 1-58488-435-5 Library of Congress Card Number 2004055286 Printed in the United States of America 1 2 3 4 5 6 7 8 9 0 Printed on acid-free paper Library of Congress Cataloging-in-Publication Data Handbook of data structures and applications / edited by Dinesh P. Mehta and Sartaj Sahni. p. cm. — (Chapman & Hall/CRC computer & information science) Includes bibliographical references and index. ISBN 1-58488-435-5 (alk. paper) 1. System design—Handbooks, manuals, etc. 2. Data structures (Computer science)—Handbooks, manuals, etc. I. Mehta, Dinesh P. II. Sahni, Sartaj. III. Chapman & Hall/CRC computer and information science series QA76.9.S88H363 2004 005.7'3—dc22 2004055286 © 2005 by Chapman & Hall/CRC Visit the CRC Press Web site at www.crcpress.com For Chapters 7, 20, and 23 the authors retain the copyright.
Page
5
Dedication To our wives, Usha Mehta and Neeta Sahni © 2005 by Chapman & Hall/CRC
Page
6
Preface In the late sixties, Donald Knuth, winner of the 1974 Turing Award, published his landmark book The Art of Computer Programming: Fundamental Algorithms. This book brought to- gether a body of knowledge that defined the data structures area. The term data structure, itself, was defined in this book to be A table of data including structural relationships. Niklaus Wirth, the inventor of the Pascal language and winner of the 1984 Turing award, stated that “Algorithms + Data Structures = Programs”. The importance of algorithms and data structures has been recognized by the community and consequently, every under- graduate Computer Science curriculum has classes on data structures and algorithms. Both of these related areas have seen tremendous advances in the decades since the appearance of the books by Knuth and Wirth. Although there are several advanced and specialized texts and handbooks on algorithms (and related data structures), there is, to the best of our knowledge, no text or handbook that focuses exclusively on the wide variety of data structures that have been reported in the literature. The goal of this handbook is to provide a comprehensive survey of data structures of different types that are in existence today. To this end, we have subdivided this handbook into seven parts, each of which addresses a different facet of data structures. Although this material is covered in all standard data structures texts, it was included to make the handbook self-contained and in recognition of the fact that there are many practitioners and theoretical in nature: they discuss the data structures, their operations and their complex- ities. use of data structures in real programs. Many of the data structures discussed in previous parts are very intricate and take some effort to program. The development of data structure libraries and visualization tools by skilled programmers are of critical importance in reduc- ing the gap between theory and practice. structures. of applications is discussed. Some of the data structures discussed here have been invented solely in the context of these applications and are not well-known to the broader commu- nity. Some of the applications discussed include Internet Routing, Web Search Engines, Databases, Data Mining, Scientific Computing, Geographical Information Systems, Com- putational Geometry, Computational Biology, VLSI Floorplanning and Layout, Computer Graphics and Image Processing. For data structure and algorithm researchers, we hope that the handbook will suggest new ideas for research in data structures and for an appreciation of the application contexts in which data structures are deployed. For the practitioner who is devising an algorithm, we hope that the handbook will lead to insights in organizing data that make it possible to solve the algorithmic problem more cleanly and efficiently. For researchers in specific application areas, we hope that they will gain some insight from the ways other areas have handled their data structuring problems. Although we have attempted to make the handbook as complete as possible, it is impos- sible to undertake a task of this magnitude without some omissions. For this, we apologize in advance and encourage readers to contact us with information about significant data © 2005 by Chapman & Hall/CRC Part I is a review of introductory material. programmers who may not have had a formal education in Computer Science. Parts II, III, and IV discuss Priority Queues, Dictionary Structures, and Multidimensional structures, respectively. These are all well-known classes of data structures. Part V is a catch-all used Part VI addresses mechanisms and tools that have been developed to facilitate the Finally, Part VII examines applications of data for well-known data structures that eluded easy classification. Parts I through V are largely The deployment of many data structures from Parts I through V in a variety
Page
7
structures or applications that do not appear here. These could be included in future edi- tions of this handbook. We would like to thank the excellent team of authors, who are at the forefront of research in data structures, that have contributed to this handbook. The handbook would not have been possible without their painstaking efforts. We are extremely saddened by the untimely demise of a prominent data structures researcher, Professor Gı́sli R. Hjaltason, who was to write a chapter for this handbook. He will be missed greatly by the Computer Science community. Finally, we would like to thank our families for their support during the development of the handbook. Dinesh P. Mehta Sartaj Sahni © 2005 by Chapman & Hall/CRC
Page
8
About the Editors Dinesh P. Mehta Dinesh P. Mehta received the B.Tech. degree in computer science and engineering from the Indian Institute of Technology, Bombay, in 1987, the M.S. degree in computer science from the University of Minnesota in 1990, and the Ph.D. degree in computer science from the University of Florida in 1992. He was on the faculty at the University of Tennessee Space Institute from 1992-2000, where he received the Vice President’s Award for Teaching Excellence in 1997. He was a Visiting Professor at Intel’s Strategic CAD Labs in 1996 and 1997. He has been an Associate Professor in the Mathematical and Computer Sciences department at the Colorado School of Mines since 2000. Dr. Mehta is a co-author of the text Fundamentals of Data Structures in C ++. His publications and research interests are in VLSI design automation, parallel computing, and applied algorithms and data structures. His data structures-related research has involved the development or application of diverse data structures such as directed acyclic word graphs (DAWGs) for strings, corner stitching for VLSI layout, the Q-sequence floorplan representation, binary decision trees, Voronoi diagrams and TPR trees for indexing moving points. Dr. Mehta is currently an Associate Editor of the IEEE Transactions on Circuits and Systems-I. Sartaj Sahni Sartaj Sahni is a Distinguished Professor and Chair 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 2003 ACM Karl Karlstrom Outstanding Educator Award. Dr. Sahni received his B.Tech. (Electrical Engineering) degree from the Indian Institute of Technology, Kanpur, and the M.S. and Ph.D. degrees in Computer Science from Cornell University. Dr. Sahni has published over two hundred and fifty research papers and written 15 texts. His research publications are on the design and analysis of efficient algorithms, parallel computing, interconnection networks, design automation, and medical algorithms. Dr. Sahni is a co-editor-in-chief of the Journal of Parallel and Distributed Computing, a managing editor of the International Journal of Foundations of Computer Science, and a member of the editorial boards of Computer Systems: Science and Engineering, Inter- national Journal of High Performance Computing and Networking, International Journal of Distributed Sensor Networks and Parallel Processing Letters. He has served as program committee chair, general chair, and been a keynote speaker at many conferences. Dr. Sahni has served on several NSF and NIH panels and he has been involved as an external evaluator of several Computer Science and Engineering departments. © 2005 by Chapman & Hall/CRC
Page
9
Contributors Srinivas Aluru Iowa State University Ames, Iowa Arne Andersson Uppsala University Uppsala, Sweden Lars Arge Duke University Durham, North Carolina Sunil Arya Hong Kong University of Science and Technology Kowloon, Hong Kong Surender Baswana Indian Institute of Technology, Delhi New Delhi, India Mark de Berg Technical University, Eindhoven Eindhoven, The Netherlands Gerth Stølting Brodal University of Aarhus Aarhus, Denmark Bernard Chazelle Princeton University Princeton, New Jersey Chung-Kuan Cheng University of California, San Diego San Diego, California Siu-Wing Cheng Hong Kong University of Science and Technology Kowloon, Hong Kong Camil Demetrescu Universitá di Roma Rome, Italy Narsingh Deo University of Central Florida Orlando, Florida Sumeet Dua Louisiana Tech University Ruston, Louisiana Christian A. Duncan University of Miami Miami, Florida Peter Eades University of Sydney and NICTA Sydney, Australia Andrzej Ehrenfeucht University of Colorado, Boulder Boulder, Colorado Rolf Fagerberg University of Southern Denmark Odense, Denmark Zhou Feng Fudan University Shanghai, China Irene Finocchi Universitá di Roma Rome, Italy Michael L. Fredman Rutgers University, New Brunswick New Brunswick, New Jersey Teofilo F. Gonzalez University of California, Santa Barbara Santa Barbara, California Michael T. Goodrich University of California, Irvine Irvine, California Leonidas Guibas Stanford University Palo Alto, California S. Gunasekaran Louisiana State University Baton Rouge, Louisiana Pankaj Gupta Cypress Semiconductor San Jose, California Prosenjit Gupta International Institute of Information Technology Hyderabad, India Joachim Hammer University of Florida Gainesville, Florida Monika Henzinger Google, Inc. Mountain View, California Seok-Hee Hong University of Sydney and NICTA Sydney, Australia Wen-Lian Hsu Academia Sinica Taipei, Taiwan Giuseppe F. Italiano Universitá di Roma Rome, Italy S. S. Iyengar Louisiana State University Baton Rouge, Louisiana Ravi Janardan University of Minnesota Minneapolis, Minnesota © 2005 by Chapman & Hall/CRC
Page
10
Haim Kaplan Tel Aviv University Tel Aviv, Israel Kun Suk Kim University of Florida Gainesville, Florida Vipin Kumar University of Minnesota Minneapolis, Minnesota Stefan Kurtz University of Hamburg Hamburg, Germany Kim S. Larsen University of Southern Denmark Odense, Denmark D. T. Lee Academia Sinica Taipei, Taiwan Sebastian Leipert Center of Advanced European Studies and Research Bonn, Germany Scott Leutenegger University of Denver Denver, Colorado Ming C. Lin University of North Carolina Chapel Hill, North Carolina Stefano Lonardi University of California, Riverside Riverside, California Mario A. Lopez University of Denver Denver, Colorado Haibin Lu University of Florida Gainesville, Florida S. N. Maheshwari Indian Institute of Technology, Delhi New Delhi, India Dinesh Manocha University of North Carolina Chapel Hill, North Carolina Ross M. McConnell Colorado State University Fort Collins, Colorado Dale McMullin Colorado School of Mines Golden, Colorado Dinesh P. Mehta Colorado School of Mines Golden, Colorado Mark Moir Sun Microsystems Laboratories Burlington, Massachusetts Pat Morin Carleton University Ottawa, Canada David M. Mount University of Maryland College Park, Maryland J. Ian Munro University of Waterloo Ontario, Canada Stefan Naeher University of Trier Trier, Germany Bruce F. Naylor University of Texas, Austin Austin, Texas Chris Okasaki United States Military Academy West Point, New York C. Pandu Rangan Indian Institute of Technology, Madras Chennai, India Alex Pothen Old Dominion University Norfolk, Virginia Alyn Rockwood Colorado School of Mines Golden, Colorado S. Srinivasa Rao University of Waterloo Ontario, Canada Rajeev Raman University of Leicester Leicester, United Kingdom Wojciech Rytter New Jersey Institute of Technology Newark, New Jersey & Warsaw University Warsaw, Poland Sartaj Sahni University of Florida Gainesville, Florida Hanan Samet University of Maryland College Park, Maryland Sanjeev Saxena Indian Institute of Technology, Kanpur Kanpur, India © 2005 by Chapman & Hall/CRC
Page
11
Markus Schneider University of Florida Gainesville, Florida Bernhard Seeger University of Marburg Marburg, Germany Sandeep Sen Indian Institute of Technology, Delhi New Delhi, India Nir Shavit Sun Microsystems Laboratories Burlington, Massachusetts Michiel Smid Carleton University Ottawa, Canada Bettina Speckmann Technical University, Eindhoven Eindhoven, The Netherlands John Stasko Georgia Institute of Technology Atlanta, Georgia Michael Steinbach University of Minnesota Minneapolis, Minnesota Roberto Tamassia Brown University Providence, Rhode Island Pang-Ning Tang Michigan State University East Lansing, Michigan Sivan Toledo Tel Aviv University Tel Aviv, Israel Luca Vismara Brown University Providence, Rhode Island V. K. Vaishnavi Georgia State University Atlanta, Georgia Jeffrey Scott Vitter Purdue University West Lafayette, Indiana Mark Allen Weiss Florida International University Miami, Florida Peter Widmayer ETH Zürich, Switzerland Bo Yao University of California, San Diego San Diego, California Donghui Zhang Northeastern University Boston, Massachusetts © 2005 by Chapman & Hall/CRC
Page
12
Contents Part I: Fundamentals 1 Analysis of Algorithms Sartaj Sahni . . . . . . . . . . . . . . . . . . . . 1-1 2 Basic Structures Dinesh P. Mehta . . . . . . . . . . . . . . . . . . . . . 2-1 3 Trees Dinesh P. Mehta . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-1 4 Graphs Narsingh Deo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-1 Part II: Priority Queues 5 Leftist Trees Sartaj Sahni . . . . . . . . . . . . . . . . . . . . . . . . . . 5-1 6 Skew Heaps C. Pandu Rangan . . . . . . . . . . . . . . . . . . . . . . . 6-1 7 Binomial, Fibonacci, and Pairing Heaps Michael L. Fredman . . . . . 7-1 8 Double-Ended Priority Queues Sartaj Sahni . . . . . . . . . . . . . . . 8-1 Part III: Dictionary Structures 9 Hash Tables Pat Morin . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9-1 10 Balanced Binary Search Trees Arne Andersson, Rolf Fagerberg, and Kim S. Larsen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10-1 11 Finger Search Trees Gerth Stølting Brodal . . . . . . . . . . . . . . . . 11-1 12 Splay Trees Sanjeev Saxena . . . . . . . . . . . . . . . . . . . . . . . . . 12-1 13 Randomized Dictionary Structures C. Pandu Rangan . . . . . . . . . 13-1 14 Trees with Minimum Weighted Path Length Wojciech Rytter . . . . 14-1 15 B Trees Donghui Zhang . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15-1 Part IV: Multidimensional and Spatial Structures 16 Multidimensional Spatial Data Structures Hanan Samet . . . . . . . 16-1 17 Planar Straight Line Graphs Siu-Wing Cheng . . . . . . . . . . . . . . 17-1 18 Interval, Segment, Range, and Priority Search Trees D. T. Lee . . . . 18-1 19 Quadtrees and Octrees Srinivas Aluru . . . . . . . . . . . . . . . . . . . 19-1 20 Binary Space Partitioning Trees . . . . . . . . . . . . 20-1 21 R-trees Scott Leutenegger and Mario A. Lopez . . . . . . . . . . . . . 21-1 22 Managing Spatio-Temporal Data Sumeet Dua and S. S. Iyengar . . 22-1 23 Kinetic Data Structures Leonidas Guibas . . . . . . . . . . . . . . . . . 23-1 24 Online Dictionary Structures Teofilo F. Gonzalez . . . . . . . . . . . . 24-1 25 Cuttings . . . . . . . . . . . . . . . . . . . . . . . . . . 25-1 26 Approximate Geometric Query Structures Christian A. Duncan and Michael T. Goodrich . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26-1 27 Geometric and Spatial Data Structures in External Memory Jeffrey Scott Vitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27-1 © 2005 by Chapman & Hall/CRC Bruce F. Naylor Bernard Chazelle
Page
13
Part V: Miscellaneous Data Structures 28 Tries Sartaj Sahni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28-1 29 Suffix Trees and Suffix Arrays Srinivas Aluru . . . . . . . . . . . . . . 29-1 30 String Searching Andrzej Ehrenfeucht and Ross M. McConnell . . . . 30-1 31 Persistent Data Structures Haim Kaplan . . . . . . . . . . . . . . . . . 31-1 32 PQ Trees, PC Trees, and Planar Graphs Wen-Lian Hsu and Ross M. McConnell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32-1 33 Data Structures for Sets Rajeev Raman . . . . . . . . . . . . . . . . . . 33-1 34 Cache-Oblivious Data Structures Lars Arge, Gerth Stølting Brodal, and Rolf Fagerberg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34-1 35 Dynamic Trees Camil Demetrescu, Irene Finocchi, and Giuseppe F. Ital- iano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35-1 36 Dynamic Graphs Camil Demetrescu, Irene Finocchi, and Giuseppe F. Italiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36-1 37 Succinct Representation of Data Structures J. Ian Munro and S. Srini- vasa Rao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37-1 38 Randomized Graph Data-Structures for Approximate Shortest Paths Suren- der Baswana and Sandeep Sen . . . . . . . . . . . . . . . . . . . . . . . . . 38-1 39 Searching and Priority Queues in o(log n) Time Arne Andersson . . 39-1 Part VI: Data Structures in Languages and Libraries 40 Functional Data Structures Chris Okasaki . . . . . . . . . . . . . . . . 40-1 41 LEDA, a Platform for Combinatorial and Geometric Computing Stefan Naeher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41-1 42 Data Structures in C++ Mark Allen Weiss . . . . . . . . . . . . . . . . 42-1 43 Data Structures in JDSL Michael T. Goodrich, Roberto Tamassia, and Luca Vismara . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43-1 44 Data Structure Visualization John Stasko . . . . . . . . . . . . . . . . . 44-1 45 Drawing Trees Sebastian Leipert . . . . . . . . . . . . . . . . . . . . . . 45-1 46 Drawing Graphs Peter Eades and Seok-Hee Hong . . . . . . . . . . . . 46-1 47 Concurrent Data Structures Mark Moir and Nir Shavit . . . . . . . . 47-1 Part VII: Applications 48 IP Router Tables Sartaj Sahni, Kun Suk Kim, and Haibin Lu . . . 48-1 49 Multi-Dimensional Packet Classification Pankaj Gupta . . . . . . . . 49-1 50 Data Structures in Web Information Retrieval Monika Henzinger . . 50-1 51 The Web as a Dynamic Graph S. N. Maheshwari . . . . . . . . . . . . 51-1 52 Layout Data Structures Dinesh P. Mehta . . . . . . . . . . . . . . . . . 52-1 53 Floorplan Representation in VLSI Zhou Feng, Bo Yao, and Chung- Kuan Cheng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53-1 54 Computer Graphics Dale McMullin and Alyn Rockwood . . . . . . . 54-1 55 Geographic Information Systems Bernhard Seeger and Peter Widmayer 55-1 56 Collision Detection Ming C. Lin and Dinesh Manocha . . . . . . . . . 56-1 © 2005 by Chapman & Hall/CRC
Page
14
57 Image Data Structures S. S. Iyengar, V. K. Vaishnavi, and S. Gu- nasekaran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57-1 58 Computational Biology Stefan Kurtz and Stefano Lonardi . . . . . . 58-1 59 Elimination Structures in Scientific Computing Alex Pothen and Sivan Toledo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59-1 60 Data Structures for Databases Joachim Hammer and Markus Schneider 60-1 61 Data Mining Vipin Kumar, Pang-Ning Tan, and Michael Steinbach 61-1 62 Computational Geometry: Fundamental Structures Mark de Berg and Bettina Speckmann . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62-1 63 Computational Geometry: Proximity and Location Sunil Arya and David M. Mount . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63-1 64 Computational Geometry: Generalized Intersection Searching Prosenjit Gupta, Ravi Janardan, and Michiel Smid . . . . . . . . . . . . . . . . . . 64-1 © 2005 by Chapman & Hall/CRC
Page
15
I Fundamentals 1 Analysis of Algorithms Sartaj Sahni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-1 Introduction • Operation Counts • Step Counts • Counting Cache Misses • Asymp- totic Complexity • Recurrence Equations • Amortized Complexity • Practical Com- plexities 2 Basic Structures Dinesh P. Mehta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-1 Introduction • Arrays • Linked Lists • Stacks and Queues 3 Trees Dinesh P. Mehta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-1 Introduction • Tree Representation • Binary Trees and Properties • Binary Tree Traversals • Threaded Binary Trees • Binary Search Trees • Heaps • Tournament Trees 4 Graphs Narsingh Deo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-1 Introduction • Graph Representations • Connectivity, Distance, and Spanning Trees • Searching a Graph • Simple Applications of DFS and BFS • Minimum Spanning Tree • Shortest Paths • Eulerian and Hamiltonian Graphs © 2005 by Chapman & Hall/CRC
Page
16
1 Analysis of Algorithms Sartaj Sahni University of Florida 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-1 1.2 Operation Counts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-2 1.3 Step Counts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-4 1.4 Counting Cache Misses . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-6 A Simple Computer Model • Effect of Cache Misses on Run Time • Matrix Multiplication 1.5 Asymptotic Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-9 Big Oh Notation (O) • Omega (Ω) and Theta (Θ) Notations • Little Oh Notation (o) 1.6 Recurrence Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-12 Substitution Method • Table-Lookup Method 1.7 Amortized Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-14 What is Amortized Complexity? • Maintenance Contract • The McWidget Company • Subset Generation 1.8 Practical Complexities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-23 1.1 Introduction The topic “Analysis of Algorithms” is concerned primarily with determining the memory (space) and time requirements (complexity) of an algorithm. Since the techniques used to determine memory requirements are a subset of those used to determine time requirements, in this chapter, we focus on the methods used to determine the time complexity of an algorithm. The time complexity (or simply, complexity) of an algorithm is measured as a function of the problem size. Some examples are given below. 1. The complexity of an algorithm to sort n elements may be given as a function of n. 2. The complexity of an algorithm to multiply an m×n matrix and an n×p matrix may be given as a function of m, n, and p. 3. The complexity of an algorithm to determine whether x is a prime number may be given as a function of the number, n, of bits in x. Note that n = log2(x+1). We partition our discussion of algorithm analysis into the following sections. 1. Operation counts. 2. Step counts. 3. Counting cache misses. 1-1 © 2005 by Chapman & Hall/CRC
Page
17
1-2 Handbook of Data Structures and Applications 4. Asymptotic complexity. 5. Recurrence equations. 6. Amortized complexity. 7. Practical complexities. 1.2 Operation Counts One way to estimate the time complexity of a program or method is to select one or more operations, such as add, multiply, and compare, and to determine how many of each is done. The success of this method depends on our ability to identify the operations that contribute most to the time complexity. Example 1.1 [Max Element] Figure 1.1 gives an algorithm that returns the position of the largest element in the array a[0:n-1]. When n > 0, the time complexity of this algorithm can be estimated by determining the number of comparisons made between elements of the array a. When n ≤ 1, the for loop is not entered. So no comparisons between elements of a are made. When n > 1, each iteration of the for loop makes one comparison between two elements of a, and the total number of element comparisons is n-1. Therefore, the number of element comparisons is max{n-1, 0}. The method max performs other comparisons (for example, each iteration of the for loop is preceded by a comparison between i and n) that are not included in the estimate. Other operations such as initializing positionOfCurrentMax and incrementing the for loop index i are also not included in the estimate. int max(int [] a, int n) { if (n < 1) return -1; // no max int positionOfCurrentMax = 0; for (int i = 1; i < n; i++) if (a[positionOfCurrentMax] < a[i]) positionOfCurrentMax = i; return positionOfCurrentMax; } FIGURE 1.1: Finding the position of the largest element in a[0:n-1]. The algorithm of Figure 1.1 has the nice property that the operation count is precisely determined by the problem size. For many other problems, however, this is not so. element in a[0:n-1] relocates to position a[n-1]. The number of swaps performed by this algorithm depends not only on the problem size n but also on the particular values of the elements in the array a. The number of swaps varies from a low of 0 to a high of n − 1. © 2005 by Chapman & Hall/CRC See [1, 3–5] for additional material on algorithm analysis. ure 1.2 gives an algorithm that performs one pass of a bubble sort. In this pass, the largest Fig-
Page
18
Analysis of Algorithms 1-3 void bubble(int [] a, int n) { for (int i = 0; i < n - 1; i++) if (a[i] > a[i+1]) swap(a[i], a[i+1]); } FIGURE 1.2: A bubbling pass. Since the operation count isn’t always uniquely determined by the problem size, we ask for the best, worst, and average counts. Example 1.2 [Sequential Search] Figure 1.3 gives an algorithm that searches a[0:n-1] for the first oc- currence of x. The number of comparisons between x and the elements of a isn’t uniquely determined by the problem size n. For example, if n = 100 and x = a[0], then only 1 comparison is made. However, if x isn’t equal to any of the a[i]s, then 100 comparisons are made. A search is successful when x is one of the a[i]s. All other searches are unsuccessful. Whenever we have an unsuccessful search, the number of comparisons is n. For successful searches the best comparison count is 1, and the worst is n. For the average count assume that all array elements are distinct and that each is searched for with equal frequency. The average count for a successful search is 1 n n∑ i=1 i = (n + 1)/2 int sequentialSearch(int [] a, int n, int x) { // search a[0:n-1] for x int i; for (i = 0; i < n && x != a[i]; i++); if (i == n) return -1; // not found else return i; } FIGURE 1.3: Sequential search. Example 1.3 sorted array a[0:n-1]. We wish to determine the number of comparisons made between x and the elements of a. For the problem size, we use the number n of elements initially in a. Assume that n ≥ 1. The best or minimum number of comparisons is 1, which happens when the new element x © 2005 by Chapman & Hall/CRC [Insertion into a Sorted Array] Figure 1.4 gives an algorithm to insert an element x into a
Page
19
1-4 Handbook of Data Structures and Applications void insert(int [] a, int n, int x) { // find proper place for x int i; for (i = n - 1; i >= 0 && x < a[i]; i--) a[i+1] = a[i]; a[i+1] = x; // insert x } FIGURE 1.4: Inserting into a sorted array. is to be inserted at the right end. The maximum number of comparisons is n, which happens when x is to be inserted at the left end. For the average assume that x has an equal chance of being inserted into any of the possible n+1 positions. If x is eventually inserted into position i+1 of a, i ≥ 0, then the number of comparisons is n-i. If x is inserted into a[0], the number of comparisons is n. So the average count is 1 n + 1 ( n−1∑ i=0 (n − i) + n) = 1 n + 1 ( n∑ j=1 j + n) = 1 n + 1 ( n(n + 1) 2 + n) = n 2 + n n + 1 This average count is almost 1 more than half the worst-case count. 1.3 Step Counts The operation-count method of estimating time complexity omits accounting for the time spent on all but the chosen operations. In the step-count method, we attempt to account for the time spent in all parts of the algorithm. As was the case for operation counts, the step count is a function of the problem size. A step is any computation unit that is independent of the problem size. Thus 10 additions can be one step; 100 multiplications can also be one step; but n additions, where n is the problem size, cannot be one step. The amount of computing represented by one step may be different from that represented by another. For example, the entire statement return a+b+b*c+(a+b-c)/(a+b)+4; can be regarded as a single step if its execution time is independent of the problem size. We may also count a statement such as x = y; as a single step. To determine the step count of an algorithm, we first determine the number of steps per execution (s/e) of each statement and the total number of times (i.e., frequency) each statement is executed. Combining these two quantities gives us the total contribution of each statement to the total step count. We then add the contributions of all statements to obtain the step count for the entire algorithm. © 2005 by Chapman & Hall/CRC
Page
20
Analysis of Algorithms 1-5 Statement s/e Frequency Total steps int sequentialSearch(· · · ) 0 0 0 { 0 0 0 int i; 1 1 1 for (i = 0; i < n && x != a[i]; i++); 1 1 1 if (i == n) return -1; 1 1 1 else return i; 1 1 1 } 0 0 0 Total 4 TABLE 1.1 Statement s/e Frequency Total steps int sequentialSearch(· · · ) 0 0 0 { 0 0 0 int i; 1 1 1 for (i = 0; i < n && x != a[i]; i++); 1 n + 1 n + 1 if (i == n) return -1; 1 1 1 else return i; 1 0 0 } 0 0 0 Total n + 3 TABLE 1.2 Worst-case step count for Figure 1.3 Statement s/e Frequency Total steps int sequentialSearch(· · · ) 0 0 0 { 0 0 0 int i; 1 1 1 for (i = 0; i < n && x != a[i]; i++); 1 j + 1 j + 1 if (i == n) return -1; 1 1 1 else return i; 1 1 1 } 0 0 0 Total j + 4 TABLE 1.3 Step count for Figure 1.3 when x = a[j] Example 1.4 [Sequential Search] Tables 1.1 and 1.2 show the best- and worst-case step-count analyses For the average step-count analysis for a successful search, we assume that the n values in a are distinct and that in a successful search, x has an equal probability of being any one of these values. Under these assumptions the average step count for a successful search is the sum of the step counts for the n possible successful searches divided by n. To obtain this average, we first obtain the step count for the case x = a[j] where j is in the range Now we obtain the average step count for a successful search: 1 n n−1∑ j=0 (j + 4) = (n + 7)/2 This value is a little more than half the step count for an unsuccessful search. Now suppose that successful searches occur only 80 percent of the time and that each a[i] still has the same probability of being searched for. The average step count for sequentialSearch is .8 ∗ (average count for successful searches) + .2 ∗ (count for an unsuccessful search) = .8(n + 7)/2 + .2(n + 3) = .6n + 3.4 © 2005 by Chapman & Hall/CRC [0, n − 1] (see Table 1.3). Best-case step count for Figure 1.3 for sequentialSearch (Figure 1.3).
The above is a preview of the first 20 pages. Register to read the complete e-book.
AI Reading Assistant
Whole-book reading guide from stratified index samples; jump to passages in the text
AI guide
【One-Line Pitch】
A comprehensive, research-oriented reference that surveys the full landscape of data structures—from arrays and search trees to priority queues, dictionaries, multidimensional and spatial structures—and connects them to real applications. Best suited for graduate students, researchers, and practitioners who already know the basics and want a single authoritative map of the field.
【Book Arc】
- **Opening (~0%–10%)**: Reviews introductory material—arrays (including irregular and sparse matrices), binary search trees, and basic algorithm analysis—establishing shared vocabulary and the cost model (cache behavior, memory layout) used throughout.
- **Early (~10%–35%)**: Covers well-known classes: balanced search trees, heaps and priority queues (pairing heaps, skew heaps, double-ended priority queues), and the amortized-analysis lens used to judge them.
- **Middle (~35%–55%)**: Moves into dictionary structures—hashing, balanced trees with relaxed balance, randomized dictionaries, and splay/self-adjusting trees—where the emphasis shifts from worst-case to amortized and probabilistic guarantees.
- **Late (~55%–80%)**: Treats multidimensional and spatial structures plus "miscellaneous" structures that resist easy classification, broadening the toolkit beyond one-dimensional keys.
- **Ending (~80%–100%)**: Addresses mechanisms and tools for using data structures in real programs, then applications—showing where these structures earn their keep in practice.
【Key Takeaways】
- **Data structures deserve a book of their own, separate from algorithms** (Opening): the editors argue no existing handbook focused exclusively on the variety of structures reported in the literature, so this fills a genuine reference gap.
- **Memory behavior is part of the analysis** (Opening): matrix-multiplication examples show loop order changing L2 cache misses by factors of 2.5–8.5, reminding readers that constant factors and locality matter, not just Big-O.
- **Amortized analysis is the right lens for self-adjusting structures** (Early): splay trees and similar structures are judged by cumulative cost over operation sequences, formalized via potential functions rather than per-operation worst case.
- **Priority queues come in rich families** (Early): pairing heaps, skew-pairing heaps, and double-ended priority queues (twin heaps, total/leaf correspondence) show how one abstract type spawns many engineering trade-offs in space and time.
- **Balanced trees can be "relaxed" for concurrency** (Middle): relaxed red-black trees replace strict color constraints with weights, allowing updates without immediate rebalancing—useful where locking entire search paths is costly.
- **Randomization removes bad inputs** (Middle): randomized dictionaries trade deterministic worst-case guarantees for expected-time bounds, so quality is judged statistically rather than by adversarial inputs.
- **The book is a map for further research, not a tutorial** (throughout): each chapter points to primary literature, making it a launchpad for new ideas and application contexts.
【Reading Tips】
- **Skim Part 1 if you know the basics**: the introductory review is a refresher; spend your time on the priority-queue, dictionary, and multidimensional chapters where the handbook's distinctive value lies.
- **Deep-read the amortized-analysis and relaxed-balance sections**: these are the conceptual hinges that make later chapters intelligible; the potential-function arguments are the hardest spots and reward patience.
- **Use chapters as entry points, not sequences**: jump to the structure relevant to your problem (e.g., spatial structures for geometry work) and follow its references outward.
- **Read the applications part last but don't skip it**: it converts abstract structures into deployment decisions and is where practitioners get the most practical return.
【Coverage Limits】
The excerpts cover the book's structure, introductory material, priority queues, balanced/randomized dictionaries, and amortized analysis, but do not detail the multidimensional, miscellaneous, tools, or applications chapters in depth; specific chapter titles beyond those shown are not confirmed.
Passage locations
Excerpt 1
ng into the array c. The remainder of the work is the same. void fastSquareMultiply(int [][] a, int [][] b, int [][] c, int n) { for (int i = 0; i < n; i++)...
View in text
Excerpt 2
ys the “nearest neighbor” strategy and is commonly referred to as Prim’s algorithm. In this method one starts with an arbitrary vertex s and joins it to its...
View in text
Excerpt 3
is a distinct element d in minPQ such that d ≤ c. Figure 8.28 shows a leaf correspondence heap. Efficient leaf correspondence DEPQs may be constructed easily...
View in text
Excerpt 4
one node will be present), for any node x, size(x) ≥ (1/n). Thus, we have following bounds for the ranks— r(t) ≤ 0 and r(x) ≥ − logn. © 2005 by Chapman & Hal...
View in text
Recommended for You
{{#thumbnailUrl}}
{{/thumbnailUrl}}
{{^thumbnailUrl}}
{{/thumbnailUrl}}
Loading recommended books...
Failed to load, please try again later
Tip the Site
Scan the WeChat Pay or Alipay code to tip. No login required.
WeChat Pay
Alipay