| Preface | p. xi |
| Elementary Structures | p. 1 |
| Stack | p. 1 |
| Queue | p. 8 |
| Double-Ended Queue | p. 16 |
| Dynamical Allocation of Nodes | p. 16 |
| Shadow Copies of Array-Based Structures | p. 18 |
| Search Trees | p. 23 |
| Two Models of Search Trees | p. 23 |
| General Properties and Transformations | p. 26 |
| Height of a Search Tree | p. 29 |
| Basic Find, Insert, and Delete | p. 31 |
| Returning from Leaf to Root | p. 35 |
| Dealing with Nonunique Keys | p. 37 |
| Queries for the Keys in an Interval | p. 38 |
| Building Optimal Search Trees | p. 40 |
| Converting Trees into Lists | p. 47 |
| Removing a Tree | p. 48 |
| Balanced Search Trees | p. 50 |
| Height-Balanced Trees | p. 50 |
| Weight-Balanced Trees | p. 61 |
| (a, b)- and B-Trees | p. 72 |
| Red-Black Trees and Trees of Almost Optimal Height | p. 89 |
| Top-Down Rebalancing for Red-Black Trees | p. 101 |
| Trees with Constant Update Time at a Known Location | p. 111 |
| Finger Trees and Level Linking | p. 114 |
| Trees with Partial Rebuilding: Amortized Analysis | p. 119 |
| Splay Trees: Adaptive Data Structures | p. 122 |
| Skip Lists: Randomized Data Structures | p. 135 |
| Joining and Splitting Balanced Search Trees | p. 143 |
| Tree Structures for Sets of Intervals | p. 148 |
| Interval Trees | p. 148 |
| Segment Trees | p. 154 |
| Trees for the Union of Intervals | p. 162 |
| Trees for Sums of Weighted Intervals | p. 169 |
| Trees for Interval-Restricted Maximum Sum Queries | p. 174 |
| Orthogonal Range Trees | p. 182 |
| Higher-Dimensional Segment Trees | p. 196 |
| Other Systems of Building Blocks | p. 199 |
| Range-Counting and the Semigroup Model | p. 202 |
| kd-Trees and Related Structures | p. 204 |
| Heaps | p. 209 |
| Balanced Search Trees as Heaps | p. 210 |
| Array-Based Heaps | p. 214 |
| Heap-Ordered Trees and Half-Ordered Trees | p. 221 |
| Leftist Heaps | p. 227 |
| Skew Heaps | p. 235 |
| Binomial Heaps | p. 239 |
| Changing Keys in Heaps | p. 248 |
| Fibonacci Heaps | p. 250 |
| Heaps of Optimal Complexity | p. 262 |
| Double-Ended Heap Structures and Multidimensional Heaps | p. 267 |
| Heap-Related Structures with Constant-Time Updates | p. 271 |
| Union-Find and Related Structures | p. 278 |
| Union-Find: Merging Classes of a Partition | p. 279 |
| Union-Find with Copies and Dynamic Segment Trees | p. 293 |
| List Splitting | p. 303 |
| Problems on Root-Directed Trees | p. 306 |
| Maintaining a Linear Order | p. 317 |
| Data Structure Transformations | p. 321 |
| Making Structures Dynamic | p. 321 |
| Making Structures Persistent | p. 330 |
| Data Structures for Strings | p. 335 |
| Tries and Compressed Tries | p. 336 |
| Dictionaries Allowing Errors in Queries | p. 356 |
| Suffix Trees | p. 360 |
| Suffix Arrays | p. 367 |
| Hash Tables | p. 374 |
| Basic Hash Tables and Collision Resolution | p. 374 |
| Universal Families of Hash Functions | p. 380 |
| Perfect Hash Functions | p. 391 |
| Hash Trees | p. 397 |
| Extendible Hashing | p. 398 |
| Membership Testers and Bloom Filters | p. 402 |
| Appendix | p. 406 |
| The Pointer Machine and Alternative Computation Models | p. 406 |
| External Memory Models and Cache-Oblivious Algorithms | p. 408 |
| Naming of Data Structures | p. 409 |
| Solving Linear Recurrences | p. 410 |
| Very Slowly Growing Functions | p. 412 |
| References | p. 415 |
| Author Index | p. 441 |
| Subject Index | p. 455 |
| Table of Contents provided by Ingram. All Rights Reserved. |
