handbookofdatastructuresandapplications

best book for learn data structures and algorithm! in englishChaPMan hall/crc computer and INfORMatION SCIENCE serieSHandbook ofDATASTRUCTURES andAPPLICATIONSedited bDinesh p mehtaColorado school of minesGoldenandSartaj sahniUniversity of floridaGainesvilledchapman HALL/CRcA CRC Press CompanyBoca raton London New york Washington Dc02005 by Chapman Hall/CRCFor Chapters 7, 20, and 23 the authors retain the copyrightLibrary of Congress Cataloging-in-Publication DataHandbook of data structures and applications /edited by Dinesh P Mehta and Sartaj Sahnip cm-( Chapman Ilal/CRC computer information science)Includes bibliographical rcfcrcnccs and index.IsBN 1-58488-435-5(alk. paper)1. System design--Handbooks, manuals, etc. 2. Data structures(Computerscience)-Handbooks, manuals, etc. I Mehta, Dinesh P. Il Sahni, Sartaj. Ill. ChapmanHall/CRC computer and information science seriesOA769S88H3632004005.73-dc222004055286This book contains information obtained from authentic and highly regarded sources. Reprinted material is quoted withpermission, and sources are indicated. a wide variety of references are listed. Reasonable efforts have been made to publishreliable data and information, but the author and the publisher cannot assume responsibility for the validity of all materialsor for the consequences of their useNeither this book nor any part may be reproduced or transmitted in any form or by any means, electronic or mechanicalncluding photocopying, microfilming, and recording, or by any information storage or retrieval system. without priorpermission in writing from the publisherAll rights reserved. Authorization to photocopy items for internal or personal use, or the personal or internal use of specificclients, may be granted by CRC Press, provided that $1.50 per page photocopied is paid directly to Copyright ClearanceCenter, 222 Rosewood Drive, Danvers, MA 01923 USA. The fee code for users of the Transactional Reporting Service isISBN 1-58488-435-5/04/$0.00+$1.50. The fee is subject lo change without notice. For organizations that have been granteda photocopy license by the CCC, a separate system of payment has been arrangedThe consent of CRC Press does nol extend to copying for general distribution, Tor pronuLioll, for creating new works,orfor resale. Specific permission must be obtained in writing from CRC Press for such copyingDirect all inquiries Lo CRC Press, 2000 N.W. Corporale blvd., Boca Ralon, Florida 33431Trademark Notice: Product or corporate names may be trademarks or registered trademarks. and are used only foridenlificalion and explanation, without intent to infringeVisitthecrCPressWebsiteatwww.crcpress.como 2005 by Chapman hall/CRCNo claim to original U. S Govcrnmcnt worksInternational Standard Book Number 1-58488-435-5Library of Congress Card Number 20040.55286Printed in the United States of America 1 2 3 456789 0Printed on acid-free paper02005 by Chapman Hall/CRCDedicationTo our wivesUsha mehta and neeta sahni02005 by Chapman Hall/CRCPrefaceIn the late sixties, Donald Knuth, winner of the 1974 Turing Award, published his landmarkbook The Art of Computer Programming: Fundamental algorithms. This book brought toether a body of knowledge that defined the data structures ared. The terIn data structure,itself, was defined in this book to be A table of data including structural relation shipsNiklaus Wirth, the inventor of the Pascal language and winner of thc 1984 Turing awardstated that "Algorithms Data Structures= Programs". The importance of algorithmsand data structures has been recognized by the community and consequently, every under-graduate Computer Science curriculum has classes on data structures and algorithms. Bothof these related areas have seen tremendous advances in the decades since the appearanceof the books by Knuth and Wirth. Although there are several advanced and specializedtexts and handbooks on algorithms (and related data structures). there is, to the best ofour knowledge, no text or handbook that focuscs exclusively on the wide varicty of datastructures that have been reported in the literature. The goal of this handbook is to providea comprehensive survey of data structures of different types that are in existence todayTo this cnd, we have subdivided this handbook into seven parts, cach of which addressesa different facet of data structures. Part I is a review of introductory material. Althoughthis material is covered in all standard data structures texts. it was included to make thehandbook self-contained and in recognition of the fact that there are many practitioners andprogrammers who may not have had a formal education in Computer Science. Parts Il, IIIand Iv discuss Priority Queues, Dictionary Structures, and Multidimensional structuresrespectively. These are all well-known classes of data structures. Part v is a catchfor well-known data structures that eluded easy classification. Parts I through V are largelytheoretical in nature: they discuss the data structures, thieir operatiOns and their conlplexities. Part VI addresses mechanisms and tools that have been developed to facilitate theuse of data structures in real programs. Many of the data structures discussed in previousparts are very intricate and take some effort to program. The development of data structurelibraries and visualization tools by skilled programmers are of critica I importance in reduc-ing the gap between theory and practice. Finally, Part vIl examines applications of datastructures. The deployment of many data structures from Parts I through V in a varietyof applications is discussed. Some of the data structures discussed here have been inventedsolely in the context of these applications and are not well-known to the broader community. Somc of thc applications discussed includc Intcrnct Routing, Wcb Scarch EnginesDatabases, Data Mining, Scientific Coinlputing, Geographical Iiforlllation Systells, CoIll-puttional Geomet, ry, Computationa. Biology, VLSI Floorplanning and Layout, ComputerGraphics and Image ProcessingFor data structialgorithe hope that the handbook willideas for reata structures and for an appreciation of the applicatiin 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 possibleto solve the algorithmic problem more cleanly and efficiently. For researchers in specificapplication areas, we hope that they will gain some insight from the ways other areas havehandled their data structuring problemsAlthough 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 apologizein advance and encourage roaders to contact us with information about significant data02005 by Chapman Hall/CRCstructures or applications that do not appear here. These could be included in future edtions of this handbook. We would like to thank the excellent team of authors. who are atthe forefront of research in data structures. that have contributed to this handbook. Thehandbook would not have been possible without their painstaking efforts. We are extremelysaddened by the untimely demise of a prominent data structures researcher, Professor GisliR. Hjaltason, who was to write a chapter for this handbook. He will be missed greatly byhe computer science community Finally, we would like to thank our families for theirsupport during the development of the handbookDinesh p. mehtaaj sahni02005 by Chapman Hall/CRCabout the editorsDinesh p mehtaDinesh P Mehta received the B Tech. degree in computer science and engineering fromthe Indian Institute of Technology, Bombay, in 1987, the M.s. degree in computer sciencefrom the University of Minnesota in 1990, and the Ph. D. degree in computer science fromhe University of Florida in 1992. He was on the faculty at the University of TennesseeSpace Inistitute froIn 1992-2000, where he received the Vice Presidents Award for TeachingExcellence in 1997. He was a Visiting Professor at Intels Strategic CAD Labs in 1996 and1997. He has bccn an Associate Professor in the Mathematical and Computcr Scicncesdepartment at the Colorado School of Mines since 2000. Dr. Mehta is a co-author of thetext Fundamental s of Data Structures in, C++. His publications and research interests arein vlsi design automation, parallel computing, and applied algorithms and data structuresHis data structures-related research has involved the development or application of diversedata structures such as directed acyclic word graphs(dawGs)for strings, corner stitchingfor VlSI layout, the Q-sequence floorplan representation, binary decision trees, Voronoidiagrams and TPR trcs for indexing moving points. Dr. Mchta is currently an AssociateEditor of the IEEE Transactions on Circuits and Systems-Tsartaj sahniSartaj sahni is a distinguished Professor and Chair of Computer and Information Sciencesand engineering at the University of Florida. He is also a member of the european academyof Sciences, a Fellow of IEEE, ACm, aAas and Minnesota Supercomputer Institute, anda Distinguished Alumnus of the Indian Institute of Technology, Kanpur. Dr. Sahni is therecipient of the 1997 IEEE Computer Society Taylor L Booth Education Award, the 2003IEEE Computer Society W. Wallace McDowell Award and the 2003 ACM Karl KarlstromOutstanding Educator Award. Dr. Sahni received his BTech.(Electrical Engineering)degree froIn the Indian Institute of Technology, Kanpur, and the M.s. and Ph.D. degreesin Computer Science from Cornell University. Dr. Sahni has published over two hundredand fifty research papers and written 15 texts. His research publications are on the designand analysis of efficient algorithms, parallel computing, interconnection networks, designautomation, and medical algorithmsDr. 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, andof the editorial boards of Corrp uler Syslernus: Science urd Engineering, Inlernational Journal of High Performance Computing and Networking, International journalof Distributed Sensor Networks and Parallel proccssing Letters. Hc has served as programcommittee chair, general chair, and been a keynote speaker at many conferences. Dr. Sahnihas served on several NsF and nih panels and he has been involved as an external evaluatorof several Computer Science and Engineering departments02005 by Chapman Hall/CRCContributorsSrinivas aluruArne anderssonLars argelowa State universityUppsala UniversityDuke UniversityAmes. lowaUppsala, SwedenDurham. North CarolinaSunil aryaSurender baswanaMark de bergHong Kong University ofIndian Institute of TechnologyTechnical niversity, EindhovenScience and Technolog yEindhoven the net herlandsKowloon, Hong KongNew delhi IndiaGerth Stolting Brodal Bernard ChazelleChung-Kuan ChengUniversity of a arhusPrinceton UniversityUniversity of California, SanAarhus. DenmarkPrinceton, Now JerseySiu-Wing ChengCamil demetrescuNarsingh DeoHong Kong University ofUniversita di romaUniversity of Central FloridaScience and technologyRome. ItalOrlando. FloridaKowloon, Hong KongSumeet uaChristian A. DuncanPeter eadesLouisiana Tech UniversitUniversity of MiamiUniversity of Sydney andRuston. louisianaMiami floridaNICTSydney, australiaAndrzej EhrenfeuchtRolf FagerbergZhou FengUniversity of Colorado, Boulder University of SouthernFudan UniversityBoulder, ColoradoDenmarkShanghai, chinaOdense. DenmarkIrene finocchiMichael L. FredmanTeofilo f. gonzalezUniversita di romaRutgers University, NeewUniversity of California, SantaRomc. ItalBrunswickBarbaraNew Brunswick,NewJerseySaula barbara. californiaMichaeli. goodrichLeonidas guibasS. GunasekaranUniversity of California, IrvineStanford UniversityLouisiana State UniversityIrvine. CaliforniaPalo Alto. CaliforniaBaton rouge. louisianaPankai guptaProsenjit GuptaJoachim hammerCypress SemiconductorInternational Institutc ofUnivcrsity of FloridaSal Jose, CaliforniaInlorinaliOl TechnologyGainesvilleHyderabad, India.Monika henzingerSeok-Hee HongWen-Lian hsUniversity of Sydney andAcademia SinicaMountain view. californiaNICTATSydney, australiaGiuseppe F.ItalianoS. s. lyengarRavi janardanUniversita di romaLouisiana State UniversityUniversity of MinnesotaRome, ItalyBaton rouge. louisianaMinneapolis Minnesota02005 by Chapman Hall/CRCHaim KaplanKun suk kimVipin kumarTel Aviv UniversitUnivcrsity of MinnesotaTel aviv, IsraelGainesville. FloridaMinneapolis, MinnesotaStefan KurtzKim s. larsenD. LeeUnivcrsity of HamburgUnivcrsity of SouthernAcademia sinicaHainburg, GermanyDenmarkTaiOdense. DenmarkSebastian LeipertScott leuteneggerMing c. LinCenter of Advanced EuropeanUniversity of DenverUniversity of North CarolinaStudies and researchDenver. ColoradoChapel Hill, North CarolinaBonn, GermanyStefano lonardiMario A. LopezHalpin uUniversity of CaliforniaUniversity of DenverUniversity of floridaerodeDenver ColoradoGainesville FloridaRiverside. Californias.n. MaheshwariDiuesh manochaRoss m. McConnellIndian Institute of TechnologUniversity of North CarolinaColorado State UniversityChapel Hill, North CarolinaFort Collins. ColoradoNew Delhi. IndiaDale mcmullinDinesh p. mehtaMark moirColorado School of minesColorado school of minesSun microsystems LaboratoriesGolden. ColoradoGolden. coloradoBurlington. MassachusettsPat morinDavid m. mountJ. Ian munroCarleton UniversityUniversity of marylandUniversity of WaterlooOttaawa,(Ontario. CanadaStefan naeherBruce F. NaylorChris okazakiUniversity of TrierUniversity of Texas, AustinUnited States Military AcademyTrier, GermanyAustin. TexasWest point, New YorkC. Pandu ranganAlex pothenAlyn RockwoodIndian Institute of TechnologyOld Dominion universityolorado school of minesMadrasNorfolk, virginiaGolden. ColoradoIndias. Srinivasa raoRajeev RamanWojciech RytterUniversity of WaterlooUniversity of LeicesterNew Jersey Institute ofOntario Canada.Leicester, United Kingdomtechnologyk new eUdiversityWarsaw. polandSarta] sannHanan SametSanjeev SaxenaUniversity of FloridaUniversity of MarylandIndian Institute of Technology,ainesville. FloridaCollege Park, MarylandKanpur, India02005 by Chapman Hall/CRC