CHAPMAN & HALL/CRC COMPUTER and INFORMATION SCIENCE SERIES Handbook of DATA STRUCTURES and APPLICATIONS © 2005 by Chapman & Hall/CRC CHAPMAN & HALL/CRC COMPUTER and INFORMATION SCIENCE SERIES Series Editor: Sartaj Sahni 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 © 2005 by Chapman & Hall/CRC CHAPMAN & HALL/CRC COMPUTER and INFORMATION SCIENCE SERIES Handbook of DATA STRUCTURES and APPLICATIONS Edited by Dinesh P. Mehta Colorado School of Mines Golden and Sartaj Sahni University of Florida Gainesville CHAPMAN & HALL/CRC A CRC Press Company Boca Raton London New York Washington, D.C. © 2005 by Chapman & Hall/CRC For Chapters 7, 20, and 23 the authors retain the copyright. 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 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. Visit the CRC Press Web site at www.crcpress.com © 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 © 2005 by Chapman & Hall/CRC Dedication To our wives, Usha Mehta and Neeta Sahni © 2005 by Chapman & Hall/CRC Preface Inthelatesixties,DonaldKnuth,winnerofthe1974TuringAward,publishedhislandmark bookThe Art of Computer Programming: Fundamental Algorithms. This bookbroughtto- getherabody ofknowledgethatdefinedthedatastructuresarea. Thetermdatastructure, 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 recognizedby the community and consequently, every under- graduateComputerSciencecurriculumhasclassesondatastructuresandalgorithms. 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 structuresthathavebeenreportedintheliterature. Thegoalofthishandbookistoprovide a comprehensive survey of data structures of different types that are in existence today. To this end, we havesubdivided this handbook into sevenparts, eachofwhich addresses a different facet of data structures. Part I is a review of introductory material. Although this material is covered in all standard data structures texts, it was included to make the handbookself-containedandinrecognitionofthefactthattherearemanypractitionersand programmerswhomaynothavehadaformaleducationinComputerScience. PartsII,III, and IV discuss Priority Queues, Dictionary Structures, and Multidimensional structures, respectively. These are all well-knownclasses of data structures. PartV is a catch-all used forwell-knowndatastructuresthateludedeasyclassification. PartsIthroughVarelargely theoretical in nature: they discuss the data structures, their operations and their complex- ities. Part VI addresses mechanisms and tools that have been developed to facilitate the use of data structures in real programs. Many of the data structures discussed in previous partsareveryintricateandtakesomeefforttoprogram. Thedevelopmentofdatastructure librariesand visualizationtools by skilled programmersare of criticalimportance in reduc- ing the gap between theory and practice. Finally, Part VII examines applications of data structures. The deployment of many data structures from Parts I through V in a variety 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 newideasforresearchindatastructuresandforanappreciationoftheapplicationcontexts 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 haveattempted 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 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 handbookwouldnothavebeenpossiblewithouttheirpainstakingefforts. Weareextremely saddenedbytheuntimelydemiseofaprominentdata structuresresearcher,ProfessorG´ı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 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 SpaceInstitute from1992-2000,wherehe receivedthe VicePresident’sAwardforTeaching Excellence in 1997. He was a Visiting Professorat 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 textFundamentals of Data Structures inC++. His publications andresearchinterestsare inVLSIdesignautomation,parallelcomputing,andappliedalgorithmsanddatastructures. His data structures-relatedresearchhas involvedthe 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 SartajSahniisaDistinguishedProfessorandChairofComputerandInformationSciences andEngineeringattheUniversityofFlorida. HeisalsoamemberoftheEuropeanAcademy 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 committeechair,generalchair,andbeenakeynotespeakeratmanyconferences. Dr. Sahni hasservedonseveralNSFandNIHpanelsandhehasbeeninvolvedasanexternalevaluator of several Computer Science and Engineering departments. © 2005 by Chapman & Hall/CRC Contributors Srinivas Aluru Arne Andersson Lars Arge IowaState University UppsalaUniversity DukeUniversity Ames,Iowa Uppsala,Sweden Durham,NorthCarolina Sunil Arya Surender Baswana Mark de Berg HongKongUniversityof IndianInstitute ofTechnology, Technical University,Eindhoven ScienceandTechnology Delhi Eindhoven, TheNetherlands Kowloon,HongKong NewDelhi,India Gerth Stølting Brodal Bernard Chazelle Chung-Kuan Cheng UniversityofAarhus PrincetonUniversity UniversityofCalifornia,San Aarhus,Denmark Princeton,NewJersey Diego SanDiego,California Siu-Wing Cheng Camil Demetrescu Narsingh Deo HongKongUniversityof Universita´diRoma UniversityofCentralFlorida ScienceandTechnology Rome,Italy Orlando,Florida Kowloon,HongKong Sumeet Dua Christian A. Duncan Peter Eades LouisianaTechUniversity UniversityofMiami UniversityofSydneyand Ruston,Louisiana Miami,Florida NICTA Sydney, Australia Andrzej Ehrenfeucht Rolf Fagerberg Zhou Feng UniversityofColorado,Boulder UniversityofSouthern FudanUniversity Boulder,Colorado Denmark Shanghai, China Odense,Denmark Irene Finocchi Michael L. Fredman Teofilo F. Gonzalez Universita´diRoma RutgersUniversity,New UniversityofCalifornia,Santa Rome,Italy Brunswick Barbara NewBrunswick,NewJersey SantaBarbara,California Michael T. Goodrich Leonidas Guibas S. Gunasekaran UniversityofCalifornia,Irvine StanfordUniversity LouisianaStateUniversity Irvine,California PaloAlto,California BatonRouge,Louisiana Pankaj Gupta Prosenjit Gupta Joachim Hammer CypressSemiconductor International Institute of UniversityofFlorida SanJose,California InformationTechnology Gainesville,Florida Hyderabad,India Monika Henzinger Seok-Hee Hong Wen-Lian Hsu Google,Inc. UniversityofSydneyand AcademiaSinica MountainView,California NICTA Taipei,Taiwan Sydney,Australia Giuseppe F. Italiano S. S. Iyengar Ravi Janardan Universita´diRoma LouisianaStateUniversity UniversityofMinnesota Rome,Italy BatonRouge, Louisiana Minneapolis,Minnesota © 2005 by Chapman & Hall/CRC Haim Kaplan Kun Suk Kim Vipin Kumar TelAvivUniversity UniversityofFlorida UniversityofMinnesota TelAviv,Israel Gainesville,Florida Minneapolis,Minnesota Stefan Kurtz Kim S. Larsen D. T. Lee UniversityofHamburg UniversityofSouthern AcademiaSinica Hamburg,Germany Denmark Taipei,Taiwan Odense,Denmark Sebastian Leipert Scott Leutenegger Ming C. Lin CenterofAdvancedEuropean UniversityofDenver UniversityofNorthCarolina StudiesandResearch Denver,Colorado ChapelHill,NorthCarolina Bonn,Germany Stefano Lonardi Mario A. Lopez Haibin Lu UniversityofCalifornia, UniversityofDenver UniversityofFlorida Riverside Denver,Colorado Gainesville,Florida Riverside,California S. N. Maheshwari Dinesh Manocha Ross M. McConnell IndianInstitute ofTechnology, UniversityofNorthCarolina ColoradoState University Delhi ChapelHill,NorthCarolina FortCollins,Colorado NewDelhi,India Dale McMullin Dinesh P. Mehta Mark Moir ColoradoSchoolofMines ColoradoSchoolofMines SunMicrosystemsLaboratories Golden,Colorado Golden,Colorado Burlington,Massachusetts Pat Morin David M. Mount J. Ian Munro CarletonUniversity UniversityofMaryland UniversityofWaterloo Ottawa,Canada CollegePark,Maryland Ontario,Canada Stefan Naeher Bruce F. Naylor Chris Okasaki UniversityofTrier UniversityofTexas,Austin UnitedStatesMilitaryAcademy Trier,Germany Austin,Texas WestPoint,NewYork C. Pandu Rangan Alex Pothen Alyn Rockwood IndianInstitute ofTechnology, OldDominionUniversity ColoradoSchool ofMines Madras Norfolk,Virginia Golden,Colorado Chennai,India S. Srinivasa Rao Rajeev Raman Wojciech Rytter UniversityofWaterloo UniversityofLeicester NewJerseyInstitute of Ontario,Canada Leicester,UnitedKingdom Technology Newark,NewJersey& WarsawUniversity Warsaw,Poland Sartaj Sahni Hanan Samet Sanjeev Saxena UniversityofFlorida UniversityofMaryland IndianInstituteofTechnology, Gainesville,Florida CollegePark,Maryland Kanpur Kanpur,India © 2005 by Chapman & Hall/CRC