Contents

Preface to the Second Edition

Preface to the First Edition

Editors

Contributors

PART IFundamentals

1Analysis of Algorithms

Sartaj Sahni

2Basic Structures

Dinesh P. Mehta

3Trees

Dinesh P. Mehta

4Graphs

Narsingh Deo

PART IIPriority Queues

5Leftist Trees

Sartaj Sahni

6Skew Heaps

C. Pandu Rangan

7Binomial, Fibonacci, and Pairing Heaps

Michael L. Fredman

8Double-Ended Priority Queues

Sartaj Sahni

PART IIIDictionary Structures

9Hash Tables

Pat Morin

10Bloom Filter and Its Variants

Shigang Chen

11Balanced Binary Search Trees

Arne Andersson, Rolf Fagerberg, and Kim S. Larsen

12Finger Search Trees

Gerth Stølting Brodal

13Splay trees

Sanjeev Saxena

14Randomized Dictionary Structures

C. Pandu Rangan

15Trees with Min Weighted Path Length

Wojciech Rytter

16B Trees

Donghui Zhang

PART IVMultidimensional/Spatial Structures

17Multidimensional Spatial Data Structures

Hanan Samet

18Planar Straight Line Graphs

Siu-Wing Cheng

19Interval, Segment, Range, Priority Search Trees

D. T. Lee and Hung-I Yu

20Quadtrees and Octtrees

Srinivas Aluru

21BSP Trees

Bruce F. Naylor

22R-Trees

Scott Leutenegger and Mario A. Lopez

23Managing Spatio-Temporal Data

Sumeet Dua and S. S. Iyengar

24Kinetic Data Structures

Leonidas Guibas

25Online Dictionary Structures

Teofilo F. Gonzalez

26Cuttings

Bernard Chazelle

27Approximate Geom Query Structures

Christian A. Duncan and Michael T. Goodrich

28Geometric and Spatial Data Structures in External Memory

Jeffrey Scott Vitter

PART VMiscellaneous

29Tries

Sartaj Sahni

30Suffix Trees and Suffix Arrays

Srinivas Aluru

31String Searching

Andrzej Ehrenfeucht and Ross M. McConnell

32Binary Decision Diagrams

Shin-ichi Minato

33Persistent Data Structures

Haim Kaplan

34Data Structures for Sets

Rajeev Raman

35Cache Oblivious Data Structures

Lars Arge, Gerth Stølting Brodal, and Rolf Fagerberg

36Dynamic Trees

Camil Demetrescu, Irene Finocchi, and Giuseppe F. Italiano

37Dynamic Graphs

Camil Demetrescu, Irene Finocchi, and Giuseppe F. Italiano

38Succinct Representation of Data Structures

J. Ian Munro and S. Srinivasa Rao

39Randomized Graph Data Structures

Surender Baswana and Sandeep Sen

40Searching and Priority Queues in o(log n) Time

Arne Andersson

PART VIData Structures in Langs and Libraries

41Functional Data Structures

Chris Okasaki

42LEDA, a Platform for Combinatorial and Geometric Computing

Stefan Naeher

43Data Structures in C++

Mark Allen Weiss

44Data Structures in JDSL

Michael T. Goodrich, Roberto Tamassia, and Luca Vismara

45Data Structure Visualization

John Stasko

46Drawing Trees

Sebastian Leipert

47Drawing Graphs

Peter Eades and Seok-Hee Hong

48Concurrent Data Structures

Mark Moir and Nir Shavit

PART VIIApplications

49IP Router Tables

Sartaj Sahni, Kun Suk Kim, and Haibin Lu

50Multidimensional Packet Classification

Pankaj Gupta

51Data Structures in Web Information Retrieval

Monika Henzinger

52The Web as a Dynamic Graph

S. N. Maheshwari

53Layout Data Structures

Dinesh P. Mehta

54Floorplan Rep in VLSI

Zhou Feng, Bo Yao, and Chung-Kuan Cheng

55Computer Graphics

Dale McMullin and Alyn Rockwood

56Geographic Information Systems

Bernhard Seeger and Peter Widmayer

57Collision Detection

Ming C. Lin and Dinesh Manocha

58Image Data Structures

S. S. Iyengar, V. K. Vaishnavi, and S. Gunasekaran

59Computational Biology

Paolo Ferragina, Stefan Kurtz, Stefano Lonardi, and Giovanni Manzini

60Data Structures for Cheminformatics

Dinesh P. Mehta and John D. Crabtree

61Elimination Structures in Scientific Computing

Alex Pothen and Sivan Toledo

62Data Structures for Databases

Joachim Hammer and Markus Schneider

63Data Structures for Big Data Stores

Arun A. Ravindran and Dinesh P. Mehta

64Data Mining

Vipin Kumar, Pang-Ning Tan, and Michael Steinbach

65Computational Geometry: Fundamental Structures

Mark de Berg and Bettina Speckmann

66Computational Geometry: Proximity and Location

Sunil Arya and David M. Mount

67Computational Geometry: Generalized (or Colored) Intersection Searching

Prosenjit Gupta, Ravi Janardan, Saladi Rahul, and Michiel Smid

Index