Edited byDinesh P. Mehta
Colorado School of Mines
Golden
and
Sartaj Sahni
University of Florida
Gainesville
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-112 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
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
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
0 Your Comments:
Post a Comment