Handbook of Data Structures and Applications

书名：Handbook of Data Structures and Applications
作者：DineshP.Mehta
译者：
ISBN：9781584884354
出版社：ChapmanandHall/CRC
出版时间：2004-10-28
格式：epub/mobi/azw3/pdf
页数：1392
豆瓣评分：

书籍简介：

In the late sixties, Donald Knuth, winner of the 1974Turing 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 goalof this handbook is to provide a comprehensive survey of data structures of di?erent types that are in existence today. To this end, we have subdivided this handbook into seven parts, each of which addresses a di?erent 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 handbook self-containedand in recognitionofthe factthatthere aremany practitionersand 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 for well-known data structures that eluded easy classification. Parts I through V are largely 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 parts are very intricate and take some e?ort to program. The developmentof data structure libraries and visualization tools by skilled programmers are of critical importance 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. Bookmarks Handbook of DATA STRUCTURES and APPLICATIONS Dedication Preface About the Editors Contributors Contents Part I: Fundamentals Chapter 1: Analysis of Algorithms 1.1 Introduction 1.2 Operation Counts 1.3 Step Counts 1.4 Counting Cache Misses 1.4.1 A Simple Computer Model 1.4.2 Effect of Cache Misses on Run Time 1.4.3 Matrix Multiplication 1.5 Asymptotic Complexity 1.5.1 Big Oh Notation (O) 1.5.2 Omega (omega) and Theta (theta) Notations 1.5.3 Little Oh Notation (o) 1.6 Recurrence Equations 1.6.1 Substitution Method 1.6.2 Table-Lookup Method 1.7 Amortized Complexity 1.7.1 What is Amortized Complexity? 1.7.2 Maintenance Contract Problem Definition Worst-Case Method Aggregate Method Accounting Method Potential Method 1.7.3 The McWidget Company Problem Definition Worst-Case Method Aggregate Method Accounting Method Potential Method 1.7.4 Subset Generation Problem Definition Worst-Case Method Aggregate Method Accounting Method Potential Method 1.8 Practical Complexities Acknowledgment References Chapter 2: Basic Structures 2.1 Introduction 2.2 Arrays 2.2.1 Operations on an Array 2.2.2 Sorted Arrays 2.2.3 Array Doubling 2.2.4 Multiple Lists in a Single Array 2.2.5 Heterogeneous Arrays 2.2.6 Multidimensional Arrays Row- or Column Major Representation Array of Arrays Representation Irregular Arrays 2.2.7 Sparse Matrices 2.3 Linked Lists 2.3.1 Chains 2.3.2 Circular Lists 2.3.3 Doubly Linked Circular Lists 2.3.4 Generalized Lists 2.4 Stacks and Queues 2.4.1 Stack Implementation 2.4.2 Queue Implementation Acknowledgments References Chapter 3: Trees 3.1 Introduction 3.2 Tree Representation 3.2.1 List Representation 3.2.2 Left Child-Right Sibling Representation 3.2.3 Binary Tree Representation 3.3 Binary Trees and Properties 3.3.1 Properties 3.3.2 Binary Tree Representation 3.4 Binary Tree Traversals 3.4.1 Inorder Traversal 3.4.2 Preorder Traversal 3.4.3 Postorder Traversal 3.4.4 Level Order Traversal 3.5 Threaded Binary Trees 3.5.1 Threads 3.5.2 Inorder Traversal of a Threaded Binary Tree 3.6 Binary Search Trees 3.6.1 Definition 3.6.2 Search 3.6.3 Insert 3.6.4 Delete 3.6.5 Miscellaneous 3.7 Heaps 3.7.1 Priority Queues 3.7.2 Definition of a Max-Heap 3.7.3 Insertion 3.7.4 Deletion 3.8 Tournament Trees 3.8.1 Winner Trees 3.8.2 Loser Trees Acknowledgments References Chapter 4: Graphs 4.1 Introduction 4.2 Graph Representations 4.2.1 Weighted Graph Representation 4.3 Connectivity, Distance, and Spanning Trees 4.3.1 Spanning Trees 4.4 Searching a Graph 4.4.1 Depth-First Search 4.4.2 Breadth-First Search 4.5 Simple Applications of DFS and BFS 4.5.1 Depth-First Search on a Digraph 4.5.2 Topological Sorting 4.6 Minimum Spanning Tree 4.6.1 Kruskal’s MST Algorithm 4.6.2 Prim’s MST Algorithm 4.6.3 Boruvka’s MST Algorithm 4.6.4 Constrained MST 4.7 Shortest Paths 4.7.1 Single-Source Shortest Paths, Nonnegative Weights 4.7.2 Single-Source Shortest Paths, Arbitrary Weights 4.7.3 All-Pairs Shortest Paths 4.8 Eulerian and Hamiltonian Graphs Acknowledgment References Part II: Priority Queues Chapter 5: Leftist Trees 5.1 Introduction 5.2 Height-Biased Leftist Trees 5.2.1 Definition 5.2.2 Insertion into a Max HBLT 5.2.3 Deletion of Max Element from a Max HBLT 5.2.4 Melding Two Max HBLTs 5.2.5 Initialization 5.2.6 Deletion of Arbitrary Element from a Max HBLT 5.3 Weight-Biased Leftist Trees 5.3.1 Definition 5.3.2 Max WBLT Operations Acknowledgment References Chapter 6: Skew Heaps 6.1 Introduction 6.2 Basics of Amortized Analysis 6.3 Meldable Priority Queues and Skew Heaps 6.3.1 Meldable Priority Queue Operations 6.3.2 Amortized Cost of Meld Operation 6.4 Bibliographic Remarks References Chapter 7: Binomial, Fibonacci, and Pairing Heaps 7.1 Introduction 7.2 Binomial Heaps 7.3 Fibonacci Heaps 7.4 Pairing Heaps 7.5 Pseudocode Summaries of the Algorithms 7.5.1 Link and Insertion Algorithms 7.5.2 Binomial Heap-Specific Algorithms 7.5.3 Fibonacci Heap-Specific Algorithms 7.5.4 Pairing Heap-Specific Algorithms 7.6 Related Developments Skew-Pairing Heaps Adaptive Properties of Pairing Heaps Soft Heaps References Chapter 8: Double-Ended Priority Queues 8.1 Definition and an Application 8.2 Symmetric Min-Max Heaps 8.3 Interval Heaps 8.3.1 Inserting an Element 8.3.2 Removing the Min Element 8.3.3 Initializing an Interval Heap 8.3.4 Complexity of Interval Heap Operations 8.3.5 The Complementary Range Search Problem 8.4 Min-Max Heaps 8.4.1 Inserting an Element 8.4.2 Removing the Min Element 8.5 Deaps 8.5.1 Inserting an Element 8.5.2 Removing the Min Element 8.6 Generic Methods for DEPQs 8.6.1 Dual Priority Queues 8.6.2 Total Correspondence 8.6.3 Leaf Correspondence 8.7 Meldable DEPQs Acknowledgment References Part III: Dictionary Structures Chapter 9: Hash Tables 9.1 Introduction 9.2 Hash Tables for Integer Keys 9.2.1 Hashing by Division 9.2.2 Hashing by Multiplication 9.2.3 Universal Hashing 9.2.4 Static Perfect Hashing 9.2.5 Dynamic Perfect Hashing 9.3 Random Probing 9.3.1 Hashing with Chaining 9.3.2 Hashing with Open Addressing 9.3.3 Linear Probing 9.3.4 Quadratic Probing 9.3.5 Double Hashing 9.3.6 Brent’s Method 9.3.7 Multiple-Choice Hashing 9.3.8 Asymmetric Hashing 9.3.9 LCFS Hashing 9.3.10 Robin-Hood Hashing 9.3.11 Cuckoo Hashing 9.4 Historical Notes 9.5 Other Developments Acknowledgment References Chapter 10: Balanced Binary Search Trees 10.1 Introduction 10.2 Basic Definitions 10.2.1 Trees 10.2.2 Binary Trees as Dictionaries Simple Searching Simple Updates More Searching Procedures Operations Involving More Trees 10.2.3 Implementation of Binary Search Trees 10.3 Generic Discussion of Balancing 10.3.1 Balance Definitions 10.3.2 Rebalancing Algorithms 10.3.3 Complexity Results 10.4 Classic Balancing Schemes 10.4.1 AVL-Trees 10.4.2 Weight-Balanced Trees 10.4.3 Balanced Binary Trees Based on Multi-Way Trees 10.5 Rebalancing a Tree to Perfect Balance 10.6 Schemes with no Balance Information 10.6.1 Implicit Representation of Balance Information Using Empty Pointers Swapping Pointers 10.6.2 General Balanced Trees 10.6.3 Application to Multi-Dimensional Search Trees 10.7 Low Height Schemes 10.8 Relaxed Balance 10.8.1 Red-Black Trees 10.8.2 AVL-Trees 10.8.3 Multi-Way Trees 10.8.4 Other Results References Chapter 11: Finger Search Trees 11.1 Finger Searching 11.2 Dynamic Finger Search Trees 11.3 Level Linked (2,4)-Trees 11.4 Randomized Finger Search Trees 11.4.1 Treaps 11.4.2 Skip Lists 11.5 Applications 11.5.1 Optimal Merging and Set Operations 11.5.2 Arbitrary Merging Order 11.5.3 List Splitting 11.5.4 Adaptive Merging and Sorting Acknowledgment References Chapter 12: Splay Trees 12.1 Introduction 12.2 Splay Trees 12.3 Analysis 12.3.1 Access and Update Operations 12.4 Optimality of Splay Trees 12.4.1 Static Optimality 12.4.2 Static Finger Theorem 12.4.3 Working Set Theorem 12.4.4 Other Properties and Conjectures 12.5 Linking and Cutting Trees 12.5.1 Data Structure 12.5.2 Solid Trees 12.5.3 Rotation 12.5.4 Splicing 12.5.5 Splay in Virtual Tree 12.5.6 Analysis of Splay in Virtual Tree 12.5.7 Implementation of Primitives for Linking and Cutting Trees 12.6 Case Study: Application to Network Flows Push(v,w) Relabel(v) Preflow-Push Algorithms 12.7 Implementation Without Linking and Cutting Trees Push/Relabel(v) Discharge(v) FIFO/Queue 12.8 FIFO: Dynamic Tree Implementation Tree-Push(v) Analysis 12.9 Variants of Splay Trees and Top-Down Splaying Acknowledgment References Chapter 13: Randomized Dictionary Structures 13.1 Introduction 13.2 Preliminaries 13.2.1 Randomized Algorithms 13.2.2 Basics of Probability Theory 13.2.3 Conditional Probability 13.2.4 Some Basic Distributions Bernoulli Distribution Binomial Distribution Geometric Distribution Negative Binomial distribution 13.2.5 Tail Estimates 13.3 Skip Lists 13.4 Structural Properties of Skip Lists 13.4.1 Number of Levels in Skip List 13.4.2 Space Complexity 13.5 Dictionary Operations 13.6 Analysis of Dictionary Operations 13.7 Randomized Binary Search Trees 13.7.1 Insertion in RBST 13.7.2 Deletion in RBST 13.8 Bibliographic Remarks References Chapter 14: Trees with Minimum Weighted Path Length 14.1 Introduction 14.2 Huffman Trees 14.2.1 O(n log n) Time Algorithm 14.2.2 Linear Time Algorithm for Presorted Sequence of Items 14.2.3 Relation between General Uniquely Decipherable Codes and Prefix-free Codes 14.2.4 Huffman Codes and Entropy 14.2.5 Huffman Algorithm for t-ary Trees 14.3 Height Limited Huffman Trees 14.3.1 Reduction to the Coin Collector Problem 14.3.2 The Algorithm for the Coin Collector Problem 14.4 Optimal Binary Search Trees 14.4.1 Approximately Optimal Binary Search Trees 14.5 Optimal Alphabetic Tree Problem 14.5.1 Computing the Cost of Optimal Alphabetic Tree 14.5.2 Construction of Optimal Alphabetic Tree 14.5.3 Optimal Alphabetic Trees for Presorted Items 14.6 Optimal Lopsided Trees 14.7 Parallel Algorithms References Chapter 15: B Trees 15.1 Introduction 15.2 The Disk-Based Environment 15.3 The B-tree 15.3.1 B-tree Definition 15.3.2 B-tree Query 15.3.3 B-tree Insertion 15.3.4 B-tree Deletion 15.4 The B+-tree 15.4.1 Copy-up and Push-up 15.4.2 B+-tree Query 15.4.3 B+-tree Insertion 15.4.4 B+-tree Deletion 15.5 Further Discussions 15.5.1 Eficiency Analysis 15.5.2 Why is the B+-tree Widely Accepted? 15.5.3 Bulk-Loading a B+-tree 15.5.4 Aggregation Query in a B+-tree References Part IV: Multidimensional and Spatial Structures Chapter 16: Multidimensional Spatial Data Structures 16.1 Introduction 16.2 Point Data 16.3 Bucketing Methods 16.4 Region Data 16.5 Rectangle Data 16.6 Line Data and Boundaries of Regions 16.7 Research Issues and Summary Acknowledgment References Chapter 17: Planar Straight Line Graphs 17.1 Introduction 17.2 Features of PSLGs 17.3 Operations on PSLGs Edge insertion and deletion Vertex split and edge contraction 17.4 Winged-Edge 17.5 Halfedge Access functions Edge insertion and deletion Vertex split and edge contraction 17.6 Quadedge 17.7 Further Remarks 17.8 Glossary Acknowledgment References Chapter 18: Interval, Segment, Range, and Priority Search Trees 18.1 Introduction 18.2 Interval Trees 18.2.1 Construction of Interval Trees 18.2.2 Example and Its Applications 18.3 Segment Trees 18.3.1 Construction of Segment Trees 18.3.2 Examples and Its Applications 18.4 Range Trees 18.4.1 Construction of Range Trees 18.4.2 Examples and Its Applications 18.5 Priority Search Trees 18.5.1 Construction of Priority Search Trees 18.5.2 Examples and Its Applications Acknowledgment References Chapter 19: Quadtrees and Octrees 19.1 Introduction 19.2 Quadtrees for Point Data 19.2.1 Point Quadtrees 19.2.2 Region Quadtrees 19.2.3 Compressed Quadtrees and Octrees 19.2.4 Cell Orderings and Space-Filling Curves 19.2.5 Construction of Compressed Quadtrees A Divide-and-Conquer Construction Algorithm Bottom-up Construction 19.2.6 Basic Operations Point and Cell Queries Insertions and Deletions Cell Insertion Cell Deletion 19.2.7 Practical Considerations 19.3 Spatial Queries with Region Quadtrees 19.3.1 Range Query 19.3.2 Spherical Region Queries 19.3.3 k-Nearest Neighbors 19.4 Image Processing Applications 19.4.1 Construction of Image Quadtrees 19.4.2 Union and Intersection of Images 19.4.3 Rotation and Scaling 19.4.4 Connected Component Labeling 19.5 Scientific Computing Applications 19.5.1 The N-body Problem Acknowledgment References Chapter 20: Binary Space Partitioning Trees 20.1 Introduction 20.2 BSP Trees as a Multi-Dimensional Search Structure 20.3 Visibility Orderings 20.3.1 Total Ordering of a Collection of Objects 20.3.2 Visibility Ordering as Tree Traversal 20.3.3 Intra-Object Visibility 20.4 BSP Tree as a Hierarchy of Regions 20.4.1 Tree Merging 20.4.2 Good BSP Trees 20.4.3 Converting B-reps to Trees 20.4.4 Boundary Representations vs. BSP Trees Bibliography Chapter 21: R-trees 21.1 Introduction 21.2 Basic Concepts Intersection queries Updating the tree 21.3 Improving Performance 21.3.1 R* Tree 21.3.2 Hilbert Tree 21.3.3 Bulk Loading General Algorithm Nearest-X (NX) Hilbert Sort (HS) Sort-Tile-Recursive (STR) 21.4 Advanced Operations 21.4.1 Nearest Neighbor Queries 21.4.2 Spatial Joins 21.5 Analytical Models Acknowledgment References Chapter 22: Managing Spatio-Temporal Data 22.1 Introduction and Background 22.2 Overlapping Linear Quadtree 22.2.1 Insertion of an Object in MVLQ 22.2.2 Deletion of an Object in MVLQ 22.2.3 Updating an Object in MVLQ 22.3 3D R-tree 22.3.1 Answering Spatio-Temporal Queries Using the Unified Schema 22.3.2 Performance Analysis of 3D R-trees 22.3.3 Handling Queries with Open Transaction-Times 22.4 2+3 R-tree 22.5 HR-tree 22.6 MV3R-tree 22.7 Indexing Structures for Continuously Moving Objects 22.7.1 TPR-tree 22.7.2 REXP -tree 22.7.3 STAR-tree 22.7.4 TPR*-tree References Chapter 23: Kinetic Data Structures 23.1 Introduction 23.2 Motion in Computational Geometry 23.3 Motion Models 23.4 Kinetic Data Structures 23.4.1 Convex Hull Example 23.4.2 Performance Measures for KDS 23.4.3 The Convex Hull, Revisited 23.5 A KDS Application Survey 23.5.1 Extent Problems 23.5.2 Proximity Problems 23.5.3 Triangulations and Tilings 23.5.4 Collision Detection 23.5.5 Connectivity and Clustering 23.5.6 Visibility 23.5.7 Result Summary 23.5.8 Open Problems Recovery after multiple certificate failures Hierarchical motion descriptions Motion sensitivity Non-canonical structures 23.6 Querying Moving Objects 23.7 Sources and Related Materials References Chapter 24: Online Dictionary Structures 24.1 Introduction 24.2 Trie Implementations 24.3 Binary Search Tree Implementations 24.4 Balanced BST Implementation 24.5 Additional Operations 24.6 Discussion References Chapter 25: Cuttings 25.1 Introduction 25.2 The Cutting Construction 25.2.1 Geometric Sampling 25.2.2 Optimal Cuttings 25.3 Applications 25.3.1 Point Location 25.3.2 Hopcroft’s problem 25.3.3 Convex Hulls and Voronoi Diagrams 25.3.4 Range Searching Acknowledgments References Chapter 26: Approximate Geometric Query Structures 26.1 Introduction 26.2 General Terminology 26.3 Approximate Queries 26.4 Quasi-BAR Bounds 26.5 BBD Trees 26.6 BAR Trees 26.7 Maximum-Spread k-d Trees Acknowledgment References Chapter 27: Geometric and Spatial Data Structures in External Memory 27.1 Introduction 27.1.1 Disk Model 27.1.2 Design Criteria for External Memory Data Structures 27.1.3 Overview of Chapter 27.2 EM Algorithms for Batched Geometric Problems 27.3 External Memory Tree Data Structures 27.3.1 B-trees and Variants 27.3.2 Weight-Balanced B-trees 27.3.3 Parent Pointers and Level-Balanced B-trees 27.3.4 Buffer Trees 27.4 Spatial Data Structures and Range Search 27.4.1 Linear-Space Spatial Structures 27.4.2 R-trees 27.4.3 Bootstrapping for 2-D Diagonal Corner and Stabbing Queries 27.4.4 Bootstrapping for Three-Sided Orthogonal 2-D Range Search 27.4.5 General Orthogonal 2-D Range Search 27.4.6 Lower Bounds for Orthogonal Range Search 27.5 Related Problems 27.6 Dynamic and Kinetic Data Structures 27.6.1 Logarithmic Method for Decomposable Search Problems 27.6.2 Continuously Moving Items 27.7 Conclusions Acknowledgment References Part V: Miscellaneous Data Structures Chapter 28: Tries 28.1 What Is a Trie? 28.2 Searching a Trie 28.3 Keys with Different Length 28.4 Height of a Trie 28.5 Space Required and Alternative Node Structures 28.6 Inserting into a Trie 28.7 Removing an Element 28.8 Prefix Search and Applications Criminology Automatic Command Completion 28.9 Compressed Tries 28.9.1 Compressed Tries with Digit Numbers Searching a Compressed Trie with Digit Numbers Inserting into a Compressed Trie with Digit Numbers Removing an Element from a Compressed Trie with Digit Numbers 28.9.2 Compressed Tries with Skip Fields 28.9.3 Compressed Tries with Edge Information Searching a Compressed Trie with Edge Information Inserting into a Compressed Trie with Edge Information Removing an Element from a Compressed Trie with Edge Information 28.9.4 Space Required by a Compressed Trie 28.10 Patricia 28.10.1 Searching 28.10.2 Inserting an Element 28.10.3 Removing an Element Acknowledgment References Chapter 29: Suffix Trees and Suffix Arrays 29.1 Basic Definitions and Properties 29.2 Linear Time Construction Algorithms 29.2.1 Suffix Trees vs. Suffix Arrays 29.2.2 Linear Time Construction of Suffix Trees McCreight’s Algorithm Generalized Suffix Trees 29.2.3 Linear Time Construction of Suffix Arrays K?r?kkanen and Sanders’ Algorithm 29.2.4 Space Issues 29.3 Applications 29.3.1 Pattern Matching Pattern Matching using Suffix Trees Pattern Matching using Suffix Arrays 29.3.2 Longest Common Substrings 29.3.3 Text Compression 29.3.4 String Containment 29.3.5 Suffix-Prefix Overlaps 29.4 Lowest Common Ancestors Bender and Farach’s lca algorithm 29.5 Advanced Applications 29.5.1 Suffix Links from Lowest Common Ancestors 29.5.2 Approximate Pattern Matching 29.5.3 Maximal Palindromes Acknowledgment References Chapter 30: String Searching 30.1 Introduction 30.2 Preliminaries 30.3 The DAWG 30.3.1 A Simple Algorithm for Constructing the DAWG 30.3.2 Constructing the DAWG in Linear Time 30.4 The Compact DAWG 30.4.1 Using the Compact DAWG to Find the Locations of a String in the Text 30.4.2 Variations and Applications 30.5 The Position Heap 30.5.1 Building the Position Heap 30.5.2 Querying the Position Heap 30.5.3 Time Bounds 30.5.4 Improvements to the Time Bounds References Chapter 31: Persistent Data Structures 31.1 Introduction 31.2 Algorithmic Applications of Persistent Data Structures 31.3 General Techniques for Making Data Structures Persistent 31.3.1 The Fat Node Method 31.3.2 Node Copying and Node Splitting 31.3.3 Handling Arrays 31.3.4 Making Data Structures Confluently Persistent 31.4 Making Specific Data Structures More Efficient 31.4.1 Redundant Binary Counters 31.4.2 Persistent Deques 31.5 Concluding Remarks and Open Questions Acknowledgment References Chapter 32: PQ Trees, PC Trees, and Planar Graphs 32.1 Introduction 32.2 The Consecutive-Ones Problem 32.2.1 A Data Structure for Representing the PC Tree 32.2.2 Finding the Terminal Path Efficiently 32.2.3 Performing the Update Step on the Terminal Path Efficiently 32.2.4 The Linear Time Bound 32.3 Planar Graphs 32.3.1 Preliminaries 32.3.2 The Strategy 32.3.3 Implementing the Recursive Step The Terminal Path Finding the Terminal Path The Linear Time Bound 32.3.4 Difierences between the Original PQ-Tree and the New PC-Tree Approaches 32.3.5 Returning a Kuratowski Subgraph when G is Non-Planar 32.4 Acknowledgment References Chapter 33: Data Structures for Sets 33.1 Introduction 33.1.1 Models of Computation 33.2 Simple Randomized Set Representations 33.2.1 The Hash Trie 33.2.2 Some Remarks on Unique Representations 33.3 Equality Testing 33.4 Extremal Sets and Subset Testing 33.4.1 Static Extremal Sets 33.4.2 Dynamic Set Intersections and Subset Testing 33.5 The Disjoint Set Union-Find Problem 33.5.1 The Classical Union-Find Problem and Variants 33.6 Partition Maintenance Algorithms 33.7 Conclusions References Chapter 34: Cache-Oblivious Data Structures 34.1 The Cache-Oblivious Model 34.2 Fundamental Primitives 34.2.1 Van Emde Boas Layout Layout Search Range query 34.2.2 k-Merger Binary mergers and merge trees k-merger Funnelsort 34.3 Dynamic B-Trees 34.3.1 Density Based Structure Updates Range queries 34.3.2 Exponential Tree Based Structure Search Updates Reducing space usage 34.4 Priority Queues 34.4.1 Merge Based Priority Queue: Funnel Heap Structure Layout Operations Analysis 34.4.2 Exponential Level Based Priority Queue Structure Layout Operations 34.5 2d Orthogonal Range Searching 34.5.1 Cache-Oblivious kd-Tree Structure Query Construction Updates 34.5.2 Cache-Oblivious Range Tree Three-Sided Queries Structure Layout Query Four-sided queries Acknowledgments References Chapter 35: Dynamic Trees 35.1 Introduction 35.2 Linking and Cutting Trees 35.2.1 Using Operations on Vertex-Disjoint Paths 35.2.2 Implementing Operations on Vertex-Disjoint Paths 35.3 Topology Trees 35.3.1 Construction 35.3.2 Updates 35.3.3 Applications 35.4 Top Trees 35.4.1 Updates 35.4.2 Representation and Applications 35.5 ET Trees 35.5.1 Updates 35.5.2 Applications 35.6 Reachability Trees 35.7 Conclusions Acknowledgments References Chapter 36: Dynamic Graphs 36.1 Introduction 36.2 Techniques for Undirected Graphs 36.2.1 Clustering 36.2.2 Sparsification 36.2.3 Randomization Maintaining Spanning Forests Random Sampling Graph Decomposition 36.3 Techniques for Directed Graphs 36.3.1 Kleene Closures Logarithmic Decomposition Recursive Decomposition 36.3.2 Long Paths 36.3.3 Locality 36.3.4 Matrices 36.4 Connectivity 36.4.1 Updates in O(log2 n) Time 36.5 Minimum Spanning Tree 36.5.1 Deletions in O(log2 n) Time 36.5.2 Updates in O(log4 n) Time 36.6 Transitive Closure 36.6.1 Updates in O( n2 log n) Time 36.6.2 Updates in O(n2) Time 36.7 All-Pairs Shortest Paths 36.7.1 Updates in O(n2.5…) Time 36.7.2 Updates in O(n2 log3 n) Time 36.8 Conclusions Acknowledgment References Chapter 37: Succinct Representation of Data Structures 37.1 Introduction 37.2 Bitvector 37.3 Succinct Dictionaries 37.3.1 Indexable Dictionary 37.3.2 Fully Indexable Dictionary 37.3.3 Dynamic Dictionary 37.4 Tree Representations 37.4.1 Binary Trees 37.4.2 Ordinal Trees 37.4.3 Cardinal Trees 37.4.4 Dynamic Binary Trees 37.5 Graph Representations 37.6 Succinct Structures for Indexing 37.7 Permutations and Functions 37.7.1 Permutations 37.7.2 Functions 37.8 Partial Sums 37.9 Arrays 37.9.1 Resizable Arrays 37.9.2 Dynamic Arrays 37.10 Conclusions References Chapter 38: Randomized Graph Data-Structures for Approximate Shortest Paths 38.1 Introduction 38.2 A Randomized Data-Structure for Static APASP : Approximate Distance Oracles 38.2.1 3-Approximate Distance Oracle 38.2.2 Preliminaries 38.2.3 (2k – 1)-Approximate Distance Oracle Reporting distance with stretch at-most (2k – 1) Size of the (2k – 1)-approximate distance oracle 38.2.4 Computing Approximate Distance Oracles Computing Balli(u) efficiently 38.3 A Randomized Data-Structure for Decremental APASP 38.3.1 Main Idea 38.3.2 Notations 38.3.3 Hierarchical Distance Maintaining Data-Structure 38.3.4 Bounding the Size of … under Edge-Deletions Maintaining the BFS tree … under edge deletions Some technical details 38.3.5 Improved Decremental Algorithm for APASP up to Distance d 38.4 Further Reading and Bibliography Acknowledgment References Chapter 39: Searching and Priority Queues in o(log n) Time 39.1 Introduction 39.2 Model of Computation 39.3 Overview 39.4 Achieving Sub-Logarithmic Time per Element by Simple Means 39.4.1 Range Reduction 39.4.2 Packing Keys 39.4.3 Combining 39.5 Deterministic Algorithms and Linear Space 39.5.1 Fusion Trees 39.5.2 Exponential Search Trees 39.6 From Amortized Update Cost to Worst-Case 39.7 Sorting and Priority Queues 39.7.1 Range Reduction 39.7.2 Packed Sorting 39.7.3 Combining the Techniques 39.7.4 Further Techniques and Faster Randomized Algorithms References Part VI: Data Structures in Languages and Libraries Chapter 40: Functional Data Structures 40.1 Introduction 40.1.1 Data Structures in Functional Languages Immutability Recursion Garbage Collection Pattern Matching 40.1.2 Functional Data Structures in Mainstream Languages Fewer Bugs Increased Sharing Decreased Synchronization 40.2 Stacks: A Simple Example 40.3 Binary Search Trees: Path Copying 40.4 Skew Heaps: Amortization and Lazy Evaluation 40.4.1 Analysis of Lazy Skew Heaps 40.5 Difficulties 40.6 Further Reading Acknowledgments References Chapter 41: LEDA, a Platform for Combinatorial and Geometric Computing 41.1 Introduction 41.1.1 Ease of Use 41.1.2 Extensibility 41.1.3 Correctness 41.1.4 Availability and Usage 41.2 The Structure of LEDA 41.3 Data Structures and Data Types 41.3.1 Basic Data Types 41.3.2 Numbers and Matrices 41.3.3 Advanced Data Types 41.3.4 Graph Data Structures 41.3.5 Geometry Kernels 41.3.6 Advanced Geometric Data Structures 41.4 Algorithms 41.5 Visualization 41.5.1 GraphWin 41.5.2 GeoWin 41.6 Example Programs 41.6.1 Word Count 41.6.2 Shortest Paths 41.6.3 Curve Reconstruction 41.6.4 Upper Convex Hull 41.6.5 Delaunay Flipping 41.6.6 Discussion 41.7 Projects Enabled by LEDA References Chapter 42: Data Structures in C++ 42.1 Introduction 42.2 Basic Containers 42.2.1 Sequence Containers 42.2.2 Sorted Associative Containers Sets and Multisets Maps and Multimaps 42.2.3 Container Adapters 42.3 Iterators 42.3.1 Basics 42.3.2 Reverse Iterators 42.4 Additional Components of the STL 42.4.1 Sorting, Searching, and Selection Sorting Selection Searching 42.4.2 Non-Standard Extensions 42.5 Sample Code Acknowledgment References Chapter 43: Data Structures in JDSL 43.1 Introduction 43.2 Design Concepts in JDSL 43.2.1 Containers and Accessors 43.2.2 Iterators 43.2.3 Decorations 43.2.4 Comparators 43.2.5 Algorithms 43.3 The Architecture of JDSL 43.3.1 Packages 43.3.2 Positional Containers Sequences Trees Graphs 43.3.3 Key-Based Containers Priority queues Dictionaries 43.3.4 Algorithms Sequence sorting Iterator-based tree traversals Euler tour tree traversal Graph traversals Topological numbering Dijkstra’s algorithm The Prim-Jarník algorithm 43.4 A Sample Application 43.4.1 Minimum-Time Flight Itineraries 43.4.2 Class IntegerDijkstraTemplate 43.4.3 Class IntegerDijkstraPathfinder 43.4.4 Class FlightDijkstra Acknowledgments References Chapter 44: Data Structure Visualization 44.1 Introduction 44.2 Value of Data Structure Rendering 44.3 Issues in Data Structure Visualization Systems 44.3.1 Purpose and Environment 44.3.2 Data Structure Views 44.3.3 Interacting with a System 44.4 Existing Research and Systems 44.4.1 Incense 44.4.2 VIPS 44.4.3 GELO 44.4.4 DDD 44.4.5 Other Systems 44.5 Summary and Open Problems References Chapter 45: Drawing Trees 45.1 Introduction 45.2 Preliminaries 45.3 Level Layout for Binary Trees 45.4 Level Layout for n-ary Trees 45.4.1 PrePosition 45.4.2 Combining a Subtree and Its Left Subforest 45.4.3 Ancestor 45.4.4 Apportion 45.4.5 Shifting the Smaller Subtrees 45.5 Radial Layout 45.6 HV-Layout Acknowledgment References Chapter 46: Drawing Graphs 46.1 Introduction 46.2 Preliminaries 46.3 Convex Drawing 46.3.1 Barycenter Algorithm 46.3.2 Divide and Conquer Algorithm 46.3.3 Algorithm Using Canonical Ordering 46.4 Symmetric Drawing 46.4.1 Displaying Rotational Symmetry 46.4.2 Displaying Axial Symmetry 46.4.3 Displaying Dihedral Symmetry 46.5 Visibility Drawing 46.5.1 Planar st-Graphs 46.5.2 The Bar Visibility Algorithm 46.5.3 Bar Visibility Representations and Layered Drawings 46.5.4 Bar Visibility Representations for Orthogonal Drawings 46.6 Conclusion References Chapter 47: Concurrent Data Structures 47.1 Designing Concurrent Data Structures 47.1.1 Performance 47.1.2 Blocking Techniques 47.1.3 Nonblocking Techniques 47.1.4 Complexity Measures 47.1.5 Correctness 47.1.6 Verification Techniques 47.1.7 Tools of the Trade Locks Barriers Transactional Synchronization Mechanisms 47.2 Shared Counters and Fetch-and-phi Structures Combining Counting Networks 47.3 Stacks and Queues Stacks Queues Deques 47.4 Pools 47.5 Linked Lists 47.6 Hash Tables 47.7 Search Trees 47.8 Priority Queues Heap-Based Priority Queues Tree-Based Priority Pools 47.9 Summary References Part VII: Applications Chapter 48: IP Router Tables 48.1 Introduction 48.2 Longest Matching-Prefix 48.2.1 Linear List 48.2.2 End-Point Array 48.2.3 Sets of Equal-Length Prefixes 48.2.4 Tries 1-Bit Tries Fixed-Stride Tries Variable-Stride Tries 48.2.5 Binary Search Trees 48.2.6 Priority Search Trees 48.3 Highest-Priority Matching 48.3.1 The Data Structure BOB 48.3.2 Search for the Highest-Priority Matching Range 48.4 Most-Specific-Range Matching 48.4.1 Nonintersecting Ranges 48.4.2 Conflict-Free Ranges Acknowledgment References Chapter 49: Multi-Dimensional Packet Classification 49.1 Introduction 49.1.1 Problem Statement 49.2 Performance Metrics for Classification Algorithms 49.3 Classification Algorithms 49.3.1 Background Bounds from Computational Geometry Range lookups 49.3.2 Taxonomy of Classification Algorithms 49.3.3 Basic Data Structures Linear search Hierarchical tries Set-pruning tries 49.3.4 Geometric Algorithms Grid-of-tries Cross-producting A 2-dimensional classification scheme Area-based quadtree Fat Inverted Segment tree (FIS-tree) Dynamic multi-level tree algorithms 49.3.5 Heuristics Recursive Flow Classification (RFC) Hierarchical Intelligent Cuttings (HiCuts) Tuple Space Search 49.3.6 Hardware-Based Algorithms Ternary CAMs Bitmap-intersection 49.4 Summary References Chapter 50: Data Structures in Web Information Retrieval 50.1 Introduction 50.2 Inverted Indices 50.2.1 Index Compression 50.2.2 Index Granularity 50.3 Fingerprints 50.4 Finding Near-Duplicate Documents 50.5 Conclusions References Chapter 51: The Web as a Dynamic Graph 51.1 Introduction 51.2 Experimental Observations 51.3 Theoretical Growth Models 51.4 Properties of Web Graphs and Web Algorithmics 51.4.1 Generating Function Framework 51.4.2 Average Path Length 51.4.3 Emergence of Giant Components 51.4.4 Search on Web Graphs 51.4.5 Crawling and Trawling 51.5 Conclusions References Chapter 52: Layout Data Structures 52.1 Introduction 52.2 VLSI Technology 52.3 Layout Data Structures: an Overview 52.4 Corner Stitching 52.4.1 Point Finding 52.4.2 Tile Insertion 52.4.3 Storage Requirements of the Corner Stitching Data Structure 52.5 Corner Stitching Extensions 52.5.1 Expanded Rectangles 52.5.2 Trapezoidal Tiles 52.5.3 Curved Tiles 52.5.4 L-shaped Tiles Rectilinear Polygons Parallel Corner Stitching Comments about Corner Stitching 52.6 Quad Trees and Variants 52.6.1 Bisector List Quad Trees 52.6.2 k-d Trees 52.6.3 Multiple Storage Quad Trees 52.6.4 Quad List Quad Trees 52.6.5 Bounded Quad Trees 52.6.6 HV Trees 52.6.7 Hinted Quad Trees 52.7 Concluding Remarks Acknowledgment References Chapter 53: Floorplan Representation in VLSI 53.1 Introduction 53.1.1 Statement of Floorplanning Problem 53.1.2 Motivation of the Representation 53.1.3 Combinations and Complexities of the Various Representations 53.1.4 Slicing, Mosaic, LB Compact, and General Floorplans 53.2 Graph Based Representations 53.2.1 Constraint Graphs The generation of constraint graphs Triangulation Tutte’s duality 53.2.2 Corner Stitching 53.2.3 Twin Binary Tree 53.2.4 Single Tree Representations 53.3 Placement Based Representations 53.3.1 Sequence-Pair 53.3.2 Bounded-Sliceline Grid 53.3.3 Corner Block List 53.3.4 Slicing Tree 53.4 Relationships of the Representations 53.4.1 Summary of the Relationships 53.4.2 A Mosaic Floorplan Example 53.4.3 A General Floorplan Example 53.5 Rectilinear Shape Handling 53.6 Conclusions 53.7 Acknowledgment References Chapter 54: Computer Graphics 54.1 Introduction 54.1.1 Hardware and Pipeline 54.2 Basic Applications 54.2.1 Meshes 54.2.2 CAD/CAM Drawings 54.2.3 Fonts 54.2.4 Bitmaps 54.2.5 Texture Mapping 54.3 Data Structures 54.3.1 Vertices, Edges, and Faces 54.3.2 Vertex, Normal, and Face Lists 54.3.3 Winged Edge 54.3.4 Tiled, Multidimensional Array 54.3.5 Linear Interpolation and Bezier Curves 54.4 Applications of Previously Discussed Structures 54.4.1 Hidden Surface Removal: An Application of the BSP Tree 54.4.2 Proximity and Collision: Other Applications of the BSP Tree 54.4.3 More With Trees: CSG Modeling References Chapter 55: Geographic Information Systems 55.1 Geographic Information Systems: What They Are All About 55.1.1 Geometric Objects 55.1.2 Topological versus Metric Data 55.1.3 Geometric Operations 55.1.4 Geometric Data Structures 55.1.5 Applications of Geographic Information Map Overlay Map Labeling Cartographic Generalization Road Maps Spatiotemporal Data Data Mining 55.2 Space Filling Curves: Order in Many Dimensions 55.2.1 Recursively Defined Space Filling Curves 55.2.2 Range Queries for Space Filling Curve Data Structures 55.2.3 Are All Space Filling Curves Created Equal? 55.2.4 Many Curve Pieces for a Query Range 55.2.5 One Curve Piece for a Query Range 55.3 Spatial Join 55.3.1 External Algorithms Index on both spatial relations Index on one spatial relation Index on none of the inputs 55.3.2 Advanced Issues 55.4 Models, Toolboxes and Systems for Geographic Information 55.4.1 Standardized Data Models 55.4.2 Commercial Systems Oracle SpatialWare LEDA and CGAL JTS Topology Suite 55.4.3 Research Prototypes SAND XXL Dedale Acknowledgment References Chapter 56: Collision Detection 56.1 Introduction 56.2 Convex Polytopes 56.2.1 Linear Programming 56.2.2 Voronoi-Based Marching Algorithm Polytope Representation Local Walk Implementation and Application 56.2.3 Minkowski Sums and Convex Optimization 56.3 General Polygonal Models 56.3.1 Interference Detection using Trees of Oriented Bounding Boxes OBBTree Construction Interference Detection OBB Representation and Overlap Test Implementation and Application 56.3.2 Performance of Bounding Volume Hierarchies 56.4 Penetration Depth Computation 56.4.1 Convex Polytopes 56.4.2 Incremental Penetration Depth Computation Local Walk Initialization and Refinement Implementation and Application 56.4.3 Non-Convex Models 56.5 Large Environments 56.5.1 Multiple-Object Collision Detection One-Dimensional Sweep and Prune Implementation and Application 56.5.2 Two-Dimensional Intersection Tests References Chapter 57: Image Data Structures 57.1 Introduction 57.2 What is Image Data? 57.3 Quadtrees 57.3.1 What is a Quadtree? 57.3.2 Variants of Quadtrees Region quadtrees Line quadtrees Edge quadtrees Template quadtrees 57.4 Virtual Quadtrees 57.4.1 Compact Quadtrees 57.4.2 Forest of Quadtrees (FQT) 57.5 Quadtrees and R-trees 57.6 Octrees 57.7 Translation Invariant Data Structure (TID) 57.8 Content-Based Image Retrieval System 57.8.1 What is CBIR? General structure of CBIR systems 57.8.2 An Example of CBIR System 57.9 Summary 57.10 Acknowledgments References Chapter 58: Computational Biology 58.1 Introduction 58.2 Discovering Unusual Words Statistical analysis of words Detecting unusual words 58.3 Comparing Whole Genomes Basic Definitions Computation of multiMEMs Space efficient computation of MEMs for two genomes Acknowledgment References Chapter 59: Elimination Structures in Scientific Computing 59.1 The Elimination Tree 59.1.1 The Elimination Game 59.1.2 The Elimination Tree Data Structure 59.1.3 An Algorithm 59.1.4 A Skeleton Graph 59.1.5 Supernodes 59.2 Applications of Etrees 59.2.1 Efficient Symbolic Factorization 59.2.2 Predicting Row and Column Nonzero Counts 59.2.3 Three Classes of Factorization Algorithms 59.2.4 Scheduling Parallel Factorizations 59.2.5 Scheduling Out-of-Core Factorizations 59.3 The Clique Tree 59.3.1 Chordal Graphs and Clique Trees 59.3.2 Design of Efficient Algorithms with Clique Trees 59.3.3 Compact Clique Trees 59.4 Clique Covers and Quotient Graphs 59.4.1 Clique Covers 59.4.2 Quotient Graphs 59.4.3 The Problem of Degree Updates 59.4.4 Covering the Column-Intersection Graph and Biclique Covers 59.5 Column Elimination Trees and Elimination DAGS 59.5.1 The Column Elimination Tree 59.5.2 Elimination DAGS 59.5.3 Elimination Structures for the Asymmetric Multifrontal Algorithm Acknowledgment References Chapter 60: Data Structures for Databases 60.1 Overview of the Functionality of a Database Management System 60.2 Data Structures for Query Processing 60.2.1 Index Structures One-dimensional Indexes Multi-dimensional Indexes 60.2.2 Sorting Large Data Sets 60.2.3 The Parse Tree 60.2.4 Expression Trees 60.2.5 Histograms 60.3 Data Structures for Buffer Management 60.4 Data Structures for Disk Space Management 60.4.1 Record Organizations 60.4.2 Page Organizations 60.4.3 File Organization 60.5 Conclusion References Chapter 61: Data Mining 61.1 Introduction 61.1.1 Data Mining Tasks and Techniques 61.1.2 Challenges of Data Mining 61.1.3 Data Mining and the Role of Data Structures and Algorithms 61.2 Classification 61.2.1 Nearest-Neighbor Classifiers 61.2.2 Proximity Graphs for Enhancing Nearest Neighbor Classifiers 61.3 Association Analysis 61.3.1 Hash Tree Structure 61.3.2 FP-Tree Structure 61.4 Clustering 61.4.1 Hierarchical and Partitional Clustering 61.4.2 Nearest Neighbor Search and Multi-Dimensional Access Methods 61.5 Conclusion Acknowledgment References Chapter 62: Computational Geometry: Fundamental Structures 62.1 Introduction 62.2 Arrangements 62.2.1 Substructures and Complexity 62.2.2 Decomposition 62.2.3 Duality 62.3 Convex Hulls 62.3.1 Complexity 62.3.2 Construction 62.3.3 Dynamic Convex Hulls 62.4 Voronoi Diagrams 62.4.1 Complexity 62.4.2 Construction 62.4.3 Variations 62.5 Triangulations 62.5.1 Delaunay Triangulation 62.5.2 Polygons 62.5.3 Polyhedra 62.5.4 Pseudo-Triangulations References Chapter 63: Computational Geometry: Proximity and Location 63.1 Introduction 63.2 Point Location 63.2.1 Kirkpatrick’s Algorithm 63.2.2 Slab-Based Methods and Persistent Trees 63.2.3 Separating Chains and Fractional Cascading 63.2.4 Trapezoidal Maps and the History Graph 63.2.5 Worst- and Expected-Case Optimal Point Location 63.3 Proximity Structures 63.3.1 Voronoi Diagrams 63.3.2 Delaunay Triangulations 63.3.3 Other Geometric Proximity Structures 63.4 Nearest Neighbor Searching 63.4.1 Nearest Neighbor Searching through Point Location 63.4.2 K-d trees 63.4.3 Other Approaches to Nearest Neighbor Searching 63.4.4 Approximate Nearest Neighbor Searching 63.4.5 Approximate Voronoi Diagrams 63.5 Sources and Related Material Acknowledgments References Chapter 64: Computational Geometry: Generalized Intersection Searching 64.1 Geometric Intersection Searching Problems 64.1.1 Generalized Intersection Searching 64.2 Summary of Known Results 64.2.1 Axes-Parallel Objects 64.2.2 Arbitrarily-Oriented Objects 64.2.3 Problems on the Grid 64.2.4 Single-Shot Problems 64.3 Techniques 64.3.1 A Transformation-Based Approach The Dynamic Reporting Problem The static counting problem The dynamic counting problem The static type-2 problem 64.3.2 A Sparsification-Based Approach Generalized halfspace range searching in R2 and R3 64.3.3 A Persistence-Based Approach Generalized semi-dynamic quadrant searching Generalized semidynamic 2-dimensional range searching Generalized 3-dimensional range searching 64.3.4 A General Approach for Reporting Problems 64.3.5 Adding Range Restrictions 64.4 Conclusion and Future Directions 64.5 Acknowledgment References

作者简介：

书友短评：

添加微信公众号:好书天下获取