List of Background Concepts ................................. ix
Preface ..................................................... xi
1 Why Data Structures? A Motivating Example .................... 1
1.1 Boyer and Moore's Algorithm ............................. 3
1.2 The Bad-Character Heuristic ............................. 4
1.3 The Good-Suffix Heuristic ............................... 7
Exercises ................................................... 12
2 Linear Lists ................................................ 14
2.1 Managing Data Storage .................................. 14
2.2 Queues ................................................. 16
2.3 Stacks ................................................. 21
2.4 Other Linear Lists ..................................... 28
Exercises ................................................... 31
3 Graplis ..................................................... 33
3.1 Extending the Relationships between Records ............ 33
3.2 Graph Representations .................................. 38
3.3 Graph Exploration ...................................... 40
3.4 The Usefulness of Graphs ............................... 41
Exercises ................................................... 47
4 Trees ....................................................... 50
4.1 Allowing Multiple Successors ........................... 50
4.2 General versus Binary Trees ............................ 52
4.3 Binary Trees: Properties and Examples .................. 55
4.4 Binary Search Trees .................................... 58
Exercises ................................................... 64
5 AVL Trees ................................................... 65
5.1 Bounding the Depth of Trees ............................ 65
5.2 Depth of AVL Trees ..................................... 66
5.3 Insertions into AVL Trees .............................. 71
5.4 Deletions from AVL Trees ............................... 77
5.5 Alternatives ........................................... 80
Exercises ................................................... 80
6 B-Trees ..................................................... 83
6.1 Higher-Order Search Trees .............................. 83
6.2 Definition of B-Trees .................................. 85
6.3 Insertion into B-Trees ................................. 86
6.4 Deletions from B-Trees ................................. 90
6.5 Variants ............................................... 92
Exercises ................................................... 99
7 Heaps ...................................................... 101
7.1 Priority Queues ....................................... 101
7.2 Definition and Updates ................................ 102
7.3 Array Implementation of Heaps ......................... 105
7.4 Construction of Heaps ................................. 106
7.5 Heapsort .............................................. 110
Exercises .................................................. 112
8 Sets ....................................................... 114
8.1 Representing a Set by a Bitmap ........................ 114
8.2 Union-Find ............................................ 117
Exercises .................................................. 125
9 Hash Tables ................................................ 127
9.1 Calculating instead of Comparing ...................... 127
9.2 Hash Functions ........................................ 129
9.3 Handling Collisions ................................... 134
9.4 Analysis of Uniform Hashing ........................... 140
9.5 Deletions from Hash Tables ............................ 147
9.6 Concluding Remarks .................................... 148
Exercises .................................................. 150
10 Sorting .................................................... 152
10.1 A Sequence of Sorting Algorithms ...................... 152
10.2 Lower Bound on the Worst Case ......................... 156
10.3 Lower Bound on the Average ............................ 160
10.4 Quicksort ............................................. 166
10.5 Finding the kth Largest Element ....................... 170
Exercises .................................................. 177
11 Codes ...................................................... 178
11.1 Representing the Data ................................. 178
11.2 Compression Codes ..................................... 179
11.3 Universal Codes ....................................... 189
11.4 Error Correcting Codes ................................ 194
11.5 Cryptographic Codes ................................... 199
Exercises .................................................. 202
Appendix Solutions to Selected Exercises ..................... 205
Index ...................................................... 217
|