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......Page 1 Half-title......Page 3 Title......Page 5 Copyright......Page 6 Contents......Page 9 Preface......Page 13 Basic Concepts......Page 15 Code Examples......Page 17 1.1 Stack......Page 19 1.2 Queue......Page 26 1.4 Dynamical Allocation of Nodes......Page 34 1.5 Shadow Copies of Array-Based Structures......Page 36 2.1 Two Models of Search Trees......Page 41 2.2 General Properties and Transformations......Page 44 2.3 Height of a Search Tree......Page 47 2.4 Basic Find, Insert, and Delete......Page 49 2.5 Returning from Leaf to Root......Page 53 2.6 Dealing with Nonunique Keys......Page 55 2.7 Queries for the Keys in an Interval......Page 56 2.8 Building Optimal Search Trees......Page 58 2.9 Converting Trees into Lists......Page 65 2.10 Removing a Tree......Page 66 3.1 Height-Balanced Trees......Page 68 3.2 Weight-Balanced Trees......Page 79 3.3 (a, b)- and B-Trees......Page 90 3.4 Red-Black Trees and Trees of Almost Optimal Height......Page 107 3.5 Top-Down Rebalancing for Red-Black Trees......Page 119 3.6 Trees with Constant Update Time at a Known Location......Page 130 3.7 Finger Trees and Level Linking......Page 132 3.8 Trees with Partial Rebuilding: Amortized Analysis......Page 137 3.9 Splay Trees: Adaptive Data Structures......Page 140 3.10 Skip Lists: Randomized Data Structures......Page 153 3.11 Joining and Splitting Balanced Search Trees......Page 161 4.1 Interval Trees......Page 166 4.2 Segment Trees......Page 172 4.3 Trees for the Union of Intervals......Page 180 4.4 Trees for Sums of Weighted Intervals......Page 187 4.5 Trees for Interval-Restricted Maximum Sum Queries......Page 192 4.6 Orthogonal Range Trees......Page 200 4.7 Higher-Dimensional Segment Trees......Page 214 4.8 Other Systems of Building Blocks......Page 217 4.9 Range-Counting and the Semigroup Model......Page 220 4.10 kd-Trees and Related Structures......Page 222 5 Heaps......Page 227 5.1 Balanced Search Trees as Heaps......Page 228 5.2 Array-Based Heaps......Page 232 5.3 Heap-Ordered Trees and Half-Ordered Trees......Page 239 5.4 Leftist Heaps......Page 245 5.5 Skew Heaps......Page 253 5.6 Binomial Heaps......Page 257 5.7 Changing Keys in Heaps......Page 266 5.8 Fibonacci Heaps......Page 268 5.9 Heaps of Optimal Complexity......Page 280 5.10 Double-Ended Heap Structures and Multidimensional Heaps......Page 285 5.11 Heap-Related Structures with Constant-Time Updates......Page 289 6 Union-Find and Related Structures......Page 296 6.1 Union-Find: Merging Classes of a Partition......Page 297 6.2 Union-Find with Copies and Dynamic Segment Trees......Page 311 6.3 List Splitting......Page 321 6.4 Problems on Root-Directed Trees......Page 324 6.5 Maintaining a Linear Order......Page 335 7.1 Making Structures Dynamic......Page 339 7.2 Making Structures Persistent......Page 348 8 Data Structures for Strings......Page 353 8.1 Tries and Compressed Tries......Page 354 8.2 Dictionaries Allowing Errors in Queries......Page 374 8.3 Suffix Trees......Page 378 8.4 Suffix Arrays......Page 385 9.1 Basic Hash Tables and Collision Resolution......Page 392 9.2 Universal Families of Hash Functions......Page 398 9.3 Perfect Hash Functions......Page 409 9.4 Hash Trees......Page 415 9.5 Extendible Hashing......Page 416 9.6 Membership Testers and Bloom Filters......Page 420 10.1 The Pointer Machine and Alternative Computation Models......Page 424 10.2 External Memory Models and Cache-Oblivious Algorithms......Page 426 10.3 Naming of Data Structures......Page 427 10.4 Solving Linear Recurrences......Page 428 10.5 Very Slowly Growing Functions......Page 430 11 References......Page 433 Author Index......Page 459 Author Index......Page 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