Open Data Structures

Acknowledgments- xi Why This Book?- xiii 1. Introduction- 1 1.1 The Need for Efficiency- 2 1.2 Interfaces- 4 1.3 Mathematical Background- 9 1.4 The Model of Computation- 18 1.5 Correctness, Time Complexity, and Space Complexity- 19 1.6 Code Samples- 22 1.7 List of Data Structures- 22 1.8 Discussion and Exercises- 26 2. Array-Based Lists- 29 2.1 ArrayStack: Fast Stack Operations Using an Array- 30 2.2 FastArrayStack: An Optimized ArrayStack- 35 2.3 ArrayQueue: An Array-Based Queue- 36 2.4 ArrayDeque: Fast Deque Operations Using an Array- 40 2.5 DualArrayDeque: Building a Deque from Two Stacks- 43 2.6 RootishArrayStack: A Space-Efficient Array Stack- 49 2.7 Discussion and Exercises- 59 3. Linked Lists- 63 3.1 SLList: A Singly-Linked List- 63 3.2 DLList: A Doubly-Linked List- 67 3.3 SEList: A Space-Efficient Linked List- 71 3.4 Discussion and Exercises- 82 4. Skiplists- 87 4.1 The Basic Structure- 87 4.2 SkiplistSSet: An Efficient Sset- 90 4.3 SkiplistList: An Efficient Random-Access List- 93 4.4 Analysis of Skiplists- 98 4.5 Discussion and Exercises- 102 5. Hash Tables- 107 5.1 ChainedHashTable: Hashing with Chaining- 107 5.2 LinearHashTable: Linear Probing- 114 5.3 Hash Codes- 122 5.4 Discussion and Exercises- 128 6. Binary Trees- 133 6.1 BinaryTree: A Basic Binary Tree- 135 6.2 BinarySearchTree: An Unbalanced Binary Search Tree- 140 6.3 Discussion and Exercises- 147 7. Random Binary Search Trees- 153 7.1 Random Binary Search Trees- 153 7.2 Treap: A Randomized Binary Search Tree- 159 7.3 Discussion and Exercises- 168 8. Scapegoat Trees- 173 8.1 ScapegoatTree: A Binary Search Tree with Partial Rebuilding- 173 8.2 Discussion and Exercises- 181 9. Red-Black Trees- 185 9.1 2-4 Trees- 186 9.2 RedBlackTree: A Simulated 2-4 Tree- 190 9.3 Summary- 205 9.4 Discussion and Exercises- 206 10. Heaps- 211 10.1 BinaryHeap: An Implicit Binary Tree- 211 10.2 MeldableHeap: A Randomized Meldable Heap- 217 10.3 Discussion and Exercises- 222 11. Sorting Algorithms- 225 11.1 Comparison-Based Sorting- 226 11.2 Counting Sort and Radix Sort- 238 11.3 Discussion and Exercises- 243 12. Graphs- 247 12.1 AdjacencyMatrix: Representing a Graph by a Matrix- 249 12.2 AdjacencyLists: A Graph as a Collection of Lists- 252 12.3 Graph Traversal- 256 12.4 Discussion and Exercises- 261 13. Data Structures for Integers- 265 13.1 BinaryTrie: A digital search tree- 266 13.2 XFastTrie: Searching in Doubly-Logarithmic Time- 272 13.3 YFastTrie: A Doubly-Logarithmic Time SSet- 275 13.4 Discussion and Exercises- 280 14. External Memory Searching- 283 14.1 The Block Store- 285 14.2 B-Trees- 285 14.3 Discussion and Exercises- 304 Bibliography- 309 Index- 317