Advanced data structures

Preface

1. Elementary Structures

1.1. Stack

1.2. Queue

1.3. Double-Ended Queue

1.4. Dynamical Allocation of Nodes

1.5. Shadow Copies of Array-Based Structures

2. Search Trees

2.1. Two Models of Search Trees

2.2. General Properties and Transformations

2.3. Height of a Search Tree

2.4. Basic Find, Insert, and Delete

2.5. Returning from Leaf to Root

2.6. Dealing with Nonunique Keys

2.7. Queries for the Keys in an Interval

2.8. Building Optimal Search Trees

2.9. Converting Trees into Lists

2.10. Removing a Tree

3. Balanced Search Trees

3.1. Height-Balanced Trees

3.2. Weight-Balanced Trees

3.3. (a, b)- and B-Trees

3.4. Red-Black Trees and Trees of Almost Optimal Height

3.5. Top-Down Rebalancing for Red-Black Trees

3.6. Trees with Constant Update Time at a Known Location

3.7. Finger Trees and Level Linking

3.8. Trees with Partial Rebuilding: Amortized Analysis

3.9. Splay Trees: Adaptive Data Structures

3.10. Skip Lists: Randomized Data Structures

3.11. Joining and Splitting Balanced Search Trees

4. Tree Structures for Sets of Intervals

4.1. Interval Trees

4.2. Segment Trees

4.3. Trees for the Union of Intervals

4.4. Trees for Sums of Weighted Intervals

4.5. Trees for Interval-Restricted Maximum Sum Queries

4.6. Orthogonal Range Trees

4.7. Higher-Dimensional Segment Trees

4.8. Other Systems of Building Blocks

4.9. Range-Counting and the Semigroup Model

4.10. kd-Trees and Related Structures

5. Heaps

5.1. Balanced Search Trees as Heaps

5.2. Array-Based Heaps

5.3. Heap-Ordered Trees and Half-Ordered Trees

5.4. Leftist Heaps

5.5. Skew Heaps

5.6. Binomial Heaps

5.7. Changing Keys in Heaps

5.8. Fibonacci Heaps

5.9. Heaps of Optimal Complexity

5.10. Double-Ended Heap Structures and Multidimensional Heaps

5.11. Heap-Related Structures with Constant-Time Updates

6. Union-Find and Related Structures

6.1. Union-Find: Merging Classes of a Partition

6.2. Union-Find with Copies and Dynamic Segment Trees

6.3. List Splitting

6.4. Problems on Root-Directed Trees

6.5. Maintaining a Linear Order

7. Data Structure Transformations

7.1. Making Structures Dynamic

7.2. Making Structures Persistent

8. Data Structures for Strings

8.1. Tries and Compressed Tries

8.2. Dictionaries Allowing Errors in Queries

8.3. Suffix Trees

8.4. Suffix Arrays

9. Hash Tables

9.1. Basic Hash Tables and Collision Resolution

9.2. Universal Families of Hash Functions

9.3. Perfect Hash Functions

9.4. Hash Trees

9.5. Extendible Hashing

9.6. Membership Testers and Bloom Filters

10. Appendix

10.1. The Pointer Machine and Alternative Computation Models

10.2. External Memory Models and Cache-Oblivious Algorithms

10.3. Naming of Data Structures

10.4. Solving Linear Recurrences

10.5. Very Slowly Growing Functions

11. References

Author Index

Subject Index