Advanced Data Structures

Advanced Data Structures presents a comprehensive look at the ideas, analysis, and implementation details of data structures as a specialized topic in applied algorithms. Data structures are how data is stored within a computer, and how one can go about searching for data within. This text examines efficient ways to search and update sets of numbers, intervals, or strings by various data structures, such as search trees, structures for sets of intervals or piece-wise constant functions, orthogonal range search structures, heaps, union-find structures, dynamization and persistence of structures, structures for strings, and hash tables. This is the first volume to show data structures as a crucial algorithmic topic, rather than relegating them as trivial material used to illustrate object-oriented programming methodology, filling a void in the ever-increasing computer science market. Numerous code examples in C and more than 500 references make Advanced Data Structures an indispensable text. topic. Numerous code examples in C and more than 500 references make Advanced Data Structures an indispensable text. Cover 1 Half-title 3 Title 5 Copyright 6 Contents 9 Preface 13 Basic Concepts 15 Code Examples 17 1 Elementary Structures 19 1.1 Stack 19 1.2 Queue 26 1.3 Double-Ended Queue 34 1.4 Dynamical Allocation of Nodes 34 1.5 Shadow Copies of Array-Based Structures 36 2 Search Trees 41 2.1 Two Models of Search Trees 41 2.2 General Properties and Transformations 44 2.3 Height of a Search Tree 47 2.4 Basic Find, Insert, and Delete 49 2.5 Returning from Leaf to Root 53 2.6 Dealing with Nonunique Keys 55 2.7 Queries for the Keys in an Interval 56 2.8 Building Optimal Search Trees 58 2.9 Converting Trees into Lists 65 2.10 Removing a Tree 66 3 Balanced Search Trees 68 3.1 Height-Balanced Trees 68 3.2 Weight-Balanced Trees 79 3.3 (a, b)- and B-Trees 90 3.4 Red-Black Trees and Trees of Almost Optimal Height 107 3.5 Top-Down Rebalancing for Red-Black Trees 119 3.6 Trees with Constant Update Time at a Known Location 130 3.7 Finger Trees and Level Linking 132 3.8 Trees with Partial Rebuilding: Amortized Analysis 137 3.9 Splay Trees: Adaptive Data Structures 140 3.10 Skip Lists: Randomized Data Structures 153 3.11 Joining and Splitting Balanced Search Trees 161 4 Tree Structures for Sets of Intervals 166 4.1 Interval Trees 166 4.2 Segment Trees 172 4.3 Trees for the Union of Intervals 180 4.4 Trees for Sums of Weighted Intervals 187 4.5 Trees for Interval-Restricted Maximum Sum Queries 192 4.6 Orthogonal Range Trees 200 4.7 Higher-Dimensional Segment Trees 214 4.8 Other Systems of Building Blocks 217 4.9 Range-Counting and the Semigroup Model 220 4.10 kd-Trees and Related Structures 222 5 Heaps 227 5.1 Balanced Search Trees as Heaps 228 5.2 Array-Based Heaps 232 5.3 Heap-Ordered Trees and Half-Ordered Trees 239 5.4 Leftist Heaps 245 5.5 Skew Heaps 253 5.6 Binomial Heaps 257 5.7 Changing Keys in Heaps 266 5.8 Fibonacci Heaps 268 5.9 Heaps of Optimal Complexity 280 5.10 Double-Ended Heap Structures and Multidimensional Heaps 285 5.11 Heap-Related Structures with Constant-Time Updates 289 6 Union-Find and Related Structures 296 6.1 Union-Find: Merging Classes of a Partition 297 6.2 Union-Find with Copies and Dynamic Segment Trees 311 6.3 List Splitting 321 6.4 Problems on Root-Directed Trees 324 6.5 Maintaining a Linear Order 335 7 Data Structure Transformations 339 7.1 Making Structures Dynamic 339 7.2 Making Structures Persistent 348 8 Data Structures for Strings 353 8.1 Tries and Compressed Tries 354 8.2 Dictionaries Allowing Errors in Queries 374 8.3 Suffix Trees 378 8.4 Suffix Arrays 385 9 Hash Tables 392 9.1 Basic Hash Tables and Collision Resolution 392 9.2 Universal Families of Hash Functions 398 9.3 Perfect Hash Functions 409 9.4 Hash Trees 415 9.5 Extendible Hashing 416 9.6 Membership Testers and Bloom Filters 420 10 Appendix 424 10.1 The Pointer Machine and Alternative Computation Models 424 10.2 External Memory Models and Cache-Oblivious Algorithms 426 10.3 Naming of Data Structures 427 10.4 Solving Linear Recurrences 428 10.5 Very Slowly Growing Functions 430 11 References 433 Author Index 459 Author Index 473 Advanced Data Structures Presents A Comprehensive Look At The Ideas, Analysis, And Implementation Details Of Data Structures As A Specialized Topic In Applied Algorithms. This Book Examines Efficient Ways To Realize Query And Update Operations On Sets Of Numbers, Intervals, Or Strings By Various Data Structures, Including Search Trees, Structures For Sets Of Intervals Or Piecewise Constant Functions, Orthogonal Range Search Structures, Heaps, Union-find Structures, Dynamization And Persistence Of Structures, Structures For Strings, And Hash Tables. Instead Of Relegating Data Structures To Trivial Material Used To Illustrate Object-oriented Programming Methodology, This Is The First Volume To Show Data Structures As A Crucial Algorithmic Topic. Numerous Code Examples In C And More Than 500 References Make Advanced Data Structures An Indispensable Text.--jacket. Elementary Structures -- Search Trees -- Balanced Search Trees -- Tree Structures For Sets Of Intervals -- Heaps -- Union-find And Related Structures -- Data Structure Transformations -- Data Structures For Strings -- Hash Tables. Peter Brass. Includes Bibliographical References (p. 415-440) And Indexes. This text closely examines ideas, analysis, and implementation details of data structures as a specialised topic in applied algorithms. It looks at efficient ways to realise query and update operations on sets of numbers, intervals, or strings by various data structures, including: search trees; structures for sets of intervals or piece-wise constant functions; orthogonal range search structures; heaps; union-find structures; dynamization and persistence of structures; structures for strings; and hash tables. Instead of relegating data structures to trivial material used to illustrate object-oriented programming methodology, this is the first volume to show data structures as a crucial algorithmic topic. Numerous code examples in C and more than 500 references make Advanced Data Structures an indispensable text. The first book to show data structures as a crucial algorithmic topic, not trivial material to illustrate object-orientation