Handbook of Data Structures and Applications

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 Thread