| |
| |
| Preface | |
| |
| |
| |
| Elementary Structures | |
| |
| |
| |
| Stack | |
| |
| |
| |
| Queue | |
| |
| |
| |
| Double-Ended Queue | |
| |
| |
| |
| Dynamical Allocation of Nodes | |
| |
| |
| |
| Shadow Copies of Array-Based Structures | |
| |
| |
| |
| Search Trees | |
| |
| |
| |
| Two Models of Search Trees | |
| |
| |
| |
| General Properties and Transformations | |
| |
| |
| |
| Height of a Search Tree | |
| |
| |
| |
| Basic Find, Insert, and Delete | |
| |
| |
| |
| Returning from Leaf to Root | |
| |
| |
| |
| Dealing with Nonunique Keys | |
| |
| |
| |
| Queries for the Keys in an Interval | |
| |
| |
| |
| Building Optimal Search Trees | |
| |
| |
| |
| Converting Trees into Lists | |
| |
| |
| |
| Removing a Tree | |
| |
| |
| |
| Balanced Search Trees | |
| |
| |
| |
| Height-Balanced Trees | |
| |
| |
| |
| Weight-Balanced Trees | |
| |
| |
| |
| (a, b)- and B-Trees | |
| |
| |
| |
| Red-Black Trees and Trees of Almost Optimal Height | |
| |
| |
| |
| Top-Down Rebalancing for Red-Black Trees | |
| |
| |
| |
| Trees with Constant Update Time at a Known Location | |
| |
| |
| |
| Finger Trees and Level Linking | |
| |
| |
| |
| Trees with Partial Rebuilding: Amortized Analysis | |
| |
| |
| |
| Splay Trees: Adaptive Data Structures | |
| |
| |
| |
| Skip Lists: Randomized Data Structures | |
| |
| |
| |
| Joining and Splitting Balanced Search Trees | |
| |
| |
| |
| Tree Structures for Sets of Intervals | |
| |
| |
| |
| Interval Trees | |
| |
| |
| |
| Segment Trees | |
| |
| |
| |
| Trees for the Union of Intervals | |
| |
| |
| |
| Trees for Sums of Weighted Intervals | |
| |
| |
| |
| Trees for Interval-Restricted Maximum Sum Queries | |
| |
| |
| |
| Orthogonal Range Trees | |
| |
| |
| |
| Higher-Dimensional Segment Trees | |
| |
| |
| |
| Other Systems of Building Blocks | |
| |
| |
| |
| Range-Counting and the Semigroup Model | |
| |
| |
| |
| kd-Trees and Related Structures | |
| |
| |
| |
| Heaps | |
| |
| |
| |
| Balanced Search Trees as Heaps | |
| |
| |
| |
| Array-Based Heaps | |
| |
| |
| |
| Heap-Ordered Trees and Half-Ordered Trees | |
| |
| |
| |
| Leftist Heaps | |
| |
| |
| |
| Skew Heaps | |
| |
| |
| |
| Binomial Heaps | |
| |
| |
| |
| Changing Keys in Heaps | |
| |
| |
| |
| Fibonacci Heaps | |
| |
| |
| |
| Heaps of Optimal Complexity | |
| |
| |
| |
| Double-Ended Heap Structures and Multidimensional Heaps | |
| |
| |
| |
| Heap-Related Structures with Constant-Time Updates | |
| |
| |
| |
| Union-Find and Related Structures | |
| |
| |
| |
| Union-Find: Merging Classes of a Partition | |
| |
| |
| |
| Union-Find with Copies and Dynamic Segment Trees | |
| |
| |
| |
| List Splitting | |
| |
| |
| |
| Problems on Root-Directed Trees | |
| |
| |
| |
| Maintaining a Linear Order | |
| |
| |
| |
| Data Structure Transformations | |
| |
| |
| |
| Making Structures Dynamic | |
| |
| |
| |
| Making Structures Persistent | |
| |
| |
| |
| Data Structures for Strings | |
| |
| |
| |
| Tries and Compressed Tries | |
| |
| |
| |
| Dictionaries Allowing Errors in Queries | |
| |
| |
| |
| Suffix Trees | |
| |
| |
| |
| Suffix Arrays | |
| |
| |
| |
| Hash Tables | |
| |
| |
| |
| Basic Hash Tables and Collision Resolution | |
| |
| |
| |
| Universal Families of Hash Functions | |
| |
| |
| |
| Perfect Hash Functions | |
| |
| |
| |
| Hash Trees | |
| |
| |
| |
| Extendible Hashing | |
| |
| |
| |
| Membership Testers and Bloom Filters | |
| |
| |
| |
| Appendix | |
| |
| |
| |
| The Pointer Machine and Alternative Computation Models | |
| |
| |
| |
| External Memory Models and Cache-Oblivious Algorithms | |
| |
| |
| |
| Naming of Data Structures | |
| |
| |
| |
| Solving Linear Recurrences | |
| |
| |
| |
| Very Slowly Growing Functions | |
| |
| |
| |
| References | |
| |
| |
| Author Index | |
| |
| |
| Subject Index | |