Advanced Data Structures

Peter Brass978-0-511-43685-7, 978-0-521-88037-4

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.

---

Table of contents :
Contents……Page 3
Preface……Page 6
Basic Concepts……Page 8
Code Examples……Page 10
1.1 Stack……Page 12
1.2 Queue……Page 19
1.4 Dynamical Allocation of Nodes……Page 27
1.5 Shadow Copies of Array-Based Structures……Page 29
2.1 Two Models of Search Trees……Page 34
2.2 General Properties and Transformations……Page 37
2.3 Height of a Search Tree……Page 40
2.4 Basic Find, Insert, and Delete……Page 42
2.5 Returning from Leaf to Root……Page 46
2.6 Dealing with Nonunique Keys……Page 48
2.7 Queries for the Keys in an Interval……Page 49
2.8 Building Optimal Search Trees……Page 51
2.9 Converting Trees into Lists……Page 58
2.10 Removing a Tree……Page 59
3.1 Height-Balanced Trees……Page 61
3.2 Weight-Balanced Trees……Page 72
3.3 (a, b)- and B-Trees……Page 83
3.4 Red-Black Trees and Trees of Almost Optimal Height……Page 100
3.5 Top-Down Rebalancing for Red-Black Trees……Page 112
3.6 Trees with Constant Update Time at a Known Location……Page 123
3.7 Finger Trees and Level Linking……Page 125
3.8 Trees with Partial Rebuilding: Amortized Analysis……Page 130
3.9 Splay Trees: Adaptive Data Structures……Page 133
3.10 Skip Lists: Randomized Data Structures……Page 146
3.11 Joining and Splitting Balanced Search Trees……Page 154
4.1 Interval Trees……Page 159
4.2 Segment Trees……Page 165
4.3 Trees for the Union of Intervals……Page 173
4.4 Trees for Sums of Weighted Intervals……Page 180
4.5 Trees for Interval-Restricted Maximum Sum Queries……Page 185
4.6 Orthogonal Range Trees……Page 193
4.7 Higher-Dimensional Segment Trees……Page 207
4.8 Other Systems of Building Blocks……Page 210
4.9 Range-Counting and the Semigroup Model……Page 213
4.10 kd-Trees and Related Structures……Page 215
5 Heaps……Page 220
5.1 Balanced Search Trees as Heaps……Page 221
5.2 Array-Based Heaps……Page 225
5.3 Heap-Ordered Trees and Half-Ordered Trees……Page 232
5.4 Leftist Heaps……Page 238
5.5 Skew Heaps……Page 246
5.6 Binomial Heaps……Page 250
5.7 Changing Keys in Heaps……Page 259
5.8 Fibonacci Heaps……Page 261
5.9 Heaps of Optimal Complexity……Page 273
5.10 Double-Ended Heap Structures and Multidimensional Heaps……Page 278
5.11 Heap-Related Structures with Constant-Time Updates……Page 282
6 Union-Find and Related Structures……Page 289
6.1 Union-Find: Merging Classes of a Partition……Page 290
6.2 Union-Find with Copies and Dynamic Segment Trees……Page 304
6.3 List Splitting……Page 314
6.4 Problems on Root-Directed Trees……Page 317
6.5 Maintaining a Linear Order……Page 328
7.1 Making Structures Dynamic……Page 332
7.2 Making Structures Persistent……Page 341
8 Data Structures for Strings……Page 346
8.1 Tries and Compressed Tries……Page 347
8.2 Dictionaries Allowing Errors in Queries……Page 367
8.3 Suffix Trees……Page 371
8.4 Suffix Arrays……Page 378
9.1 Basic Hash Tables and Collision Resolution……Page 385
9.2 Universal Families of Hash Functions……Page 391
9.3 Perfect Hash Functions……Page 402
9.4 Hash Trees……Page 408
9.5 Extendible Hashing……Page 409
9.6 Membership Testers and Bloom Filters……Page 413
10.1 The Pointer Machine and Alternative Computation Models……Page 417
10.2 External Memory Models and Cache-Oblivious Algorithms……Page 419
10.3 Naming of Data Structures……Page 420
10.4 Solving Linear Recurrences……Page 421
10.5 Very Slowly Growing Functions……Page 423
11 References……Page 425
Author Index……Page 451
Author Index……Page 465