xiv Contents

7.6 Graph Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201

7.7 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
7.8 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
7.9 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
8 Membership Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
8.1 Chapter Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
8.2 Bloom Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
8.2.1 The Hashing Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
8.2.2 The Bloom Filter Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
8.2.3 Drawbacks of a Bloom Filter . . . . . . . . . . . . . . . . . . . . . . . . 211
8.3 The Trie Datatype . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
8.3.1 Inserting into a Trie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
8.3.2 Membership in a Trie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
8.3.3 Comparing Tries and Bloom Filters . . . . . . . . . . . . . . . . . . 214
8.4 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
8.5 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
8.6 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
9 Heaps ............................................................... 217
9.1 Chapter Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
9.2 Key Ideas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
9.3 Building a Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
9.4 The Heapsort Algorithm Version 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
9.5 Analysis of Version 1 Phase I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
9.6 Phase II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
9.7 Analysis of Phase II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
9.8 The Heapsort Algorithm Version 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
9.9 Analysis of Heapsort Version 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
9.10 Comparison to Other Sortling Algorithms . . . . . . . . . . . . . . . . . . . . 236
9.11 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
9.12 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
9.13 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
10 Balanced Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
10.1 Chapter Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
10.2 Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
10.3 AVL Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
10.3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
10.3.2 Implementation Alternatives . . . . . . . . . . . . . . . . . . . . . . . . . 244
10.3.3 AVL Tree Iterative Insert . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
10.3.4 Rotations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
10.3.5 AVL Tree Recursive Insert . . . . . . . . . . . . . . . . . . . . . . . . . . 251
10.3.6 Maintaining Balance Versus Height . . . . . . . . . . . . . . . . . . 254
10.3.7 Deleting an Item from an AVL Tree . . . . . . . . . . . . . . . . . 254