I INTRODUCTION 1
1 Design Principles 3
1.1 Object-Oriented Design and This Book . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Encapsulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Invariants and Representation Properties . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Interfaces and Data Abstraction . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Case Study on Conceptual Design: Historical Event Collection . . . . . . . . . . 8
1.6 Case Study on Structural Design: Trees . . . . . . . . . . . . . . . . . . . . . . . 10
1.7 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Selecting an Abstract Data Type 15
2.1 An Illustrative Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Broad ADT groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3 Partition of a Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4 A Collection of Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5 Markers and Trackers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.6 Positioning and Finding Elements . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.6.1 Manually Positioned Collections . . . . . . . . . . . . . . . . . . . . . . 26
2.6.2 Algorithmically Positioned Collections . . . . . . . . . . . . . . . . . . 26
2.7 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3 How to Use This Book 35
3.1 Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2 Parts II and III Presentation Structure . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.1 ADT Chapters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.2 Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2.3 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3 Appendices and CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
II COLLECTION DATA STRUCTURES AND ALGORITHMS 43
4 Part II Organization 45
5 Foundations 49
5.1 Wrappers for Delegation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.2 Objects Abstract Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.2.1 Singleton Classes: Empty and Deleted . . . . . . . . . . . . . . . . . . . 51
5.2.2 Object Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.2.3 Object Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
vii
© 2008 by Taylor & Francis Group, LLC
viii
5.3 Digitizer Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.4 Bucketizer Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.5 Object Pool to Reduce Garbage Collection Overhead . . . . . . . . . . . . . . . . 59
5.6 Concurrency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.7 Iterators for Traversing Data Structures . . . . . . . . . . . . . . . . . . . . . . . 62
5.8 Locator Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.8.1 Case Study: Maintaining Request Quorums for Byzantine Agreement . . 63
5.8.2 Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.8.3 Markers and Trackers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.8.4 Iteration Using Locators . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.8.5 Iteration Order and Concurrent Modifications . . . . . . . . . . . . . . . 68
5.9 Version Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.10 Visitors for Traversing Data Structures . . . . . . . . . . . . . . . . . . . . . . . 71
6 Partition ADT and the Union-Find Data Structure 73
6.1 Partition Element Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.2 Selecting a Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.3 Union-Find Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.4 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
6.5 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
6.6 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.7 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.8 Case Study: Preserving Locators When Merging Data Structures . . . . . . . . . 81
6.9 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.10 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
7 Collection of Elements 89
7.1 Collection Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.2 Tracked Collection Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
7.3 ADTs Implementing the Collection Interface . . . . . . . . . . . . . . . . . . . . 92
7.3.1 Manually Positioned Collections . . . . . . . . . . . . . . . . . . . . . . 92
7.3.2 Algorithmically Positioned Untagged Collections . . . . . . . . . . . . . 92
7.3.3 Algorithmically Positioned Tagged Ungrouped Collections . . . . . . . . 93
7.3.4 Algorithmically Positioned Tagged Grouped Collections . . . . . . . . . 94
8 Abstract Collection 95
8.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
8.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
8.3 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
8.3.1 Trivial Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
8.3.2 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
8.3.3 Representation Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . 99
8.3.4 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
8.4 Abstract Locater Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
8.5 Visiting Iterator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
8.6 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
8.7 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
© 2008 by Taylor & Francis Group, LLC
ix
9 Positional Collection ADT 107
9.1 Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
9.2 Positional Collection Locator Interface . . . . . . . . . . . . . . . . . . . . . . . 109
9.3 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
9.4 Competing ADTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
9.5 Selecting a Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
9.5.1 Tradeoffs among Array-Based Data Structures . . . . . . . . . . . . . . 114
9.5.2 Tradeoffs among List-Based Data Structures . . . . . . . . . . . . . . . 115
9.6 Summary of Positional Collection Data Structures . . . . . . . . . . . . . . . . . 116
9.7 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
10 Abstract Positional Collection 121
10.1 Abstract Positional Collection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
10.2 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
10.3 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
11 Array Data Structure 125
11.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
11.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
11.3 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
11.3.1 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
11.3.2 Trivial Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
11.3.3 Representation Accessors . . . . . . . . . . . . . . . . . . . . . . . . . 130
11.3.4 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
11.3.5 Representation Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . 132
11.3.6 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
11.3.7 Locator Initializers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
11.4 SortingAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
11.4.1 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
11.4.2 Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
11.4.3 Heap Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
11.4.4 Tree Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
11.4.5 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
11.4.6 Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
11.4.7 Bucket Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
11.5 Selection and Median Finding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
11.6 Basic Marker Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
11.7 Marker Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
11.8 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
11.9 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
11.10 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
12 Circular Array Data Structure 171
12.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
12.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
12.3 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
12.3.1 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
12.3.2 Representation Accessors . . . . . . . . . . . . . . . . . . . . . . . . . 174
12.3.3 Representation Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . 175
12.3.4 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
12.4 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
12.5 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
© 2008 by Taylor & Francis Group, LLC
x
13 Dynamic Array and Dynamic Circular Array Data Structures 185
13.1 Dynamic Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
13.2 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
13.3 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
13.4 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
13.4.1 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
13.4.2 Representation Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . 188
13.4.3 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
13.5 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
13.6 Dynamic Circular Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
14 Tracked Array Data Structure 193
14.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
14.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
14.3 Node Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
14.4 Tracked Array Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
14.4.1 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
14.4.2 Representation Accessors . . . . . . . . . . . . . . . . . . . . . . . . . 199
14.4.3 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
14.4.4 Representation Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . 200
14.4.5 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
14.4.6 Locator Initializers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
14.5 Wrappers for Sorting Tracked Arrays . . . . . . . . . . . . . . . . . . . . . . . . 205
14.6 Tracker Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
14.7 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
14.8 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
15 Singly Linked List Data Structure 217
15.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
15.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
15.3 List Item Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
15.4 Singly Linked List Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
15.4.1 Constructors and Factory Methods . . . . . . . . . . . . . . . . . . . . . 221
15.4.2 Representation Accessors . . . . . . . . . . . . . . . . . . . . . . . . . 222
15.4.3 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
15.4.4 Representation Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . 224
15.4.5 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
15.4.6 Locator Initializers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
15.5 SortingAlgorithmsRevisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
15.5.1 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
15.5.2 Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
15.5.3 Heap Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
15.5.4 Tree Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
15.5.5 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
15.5.6 Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
15.5.7 Bucket Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
15.6 Selection and Median Finding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
15.7 Tracker Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
15.8 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
15.9 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
© 2008 by Taylor & Francis Group, LLC
xi
16 Doubly Linked List Data Structure 257
16.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
16.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
16.3 Doubly Linked List Item Inner Class . . . . . . . . . . . . . . . . . . . . . . . . 259
16.4 Doubly Linked List Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
16.4.1 Constructors and Factory Methods . . . . . . . . . . . . . . . . . . . . . 259
16.4.2 Representation Accessors . . . . . . . . . . . . . . . . . . . . . . . . . 260
16.4.3 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
16.4.4 Representation Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . 261
16.5 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
16.6 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
17 Buffer ADT and Its Implementation 265
17.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
17.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
17.3 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
17.3.1 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
17.3.2 Trivial Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
17.3.3 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
17.3.4 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
17.3.5 Locator Initializers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
17.4 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
17.5 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
18 Queue ADT and Implementation 271
18.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
18.2 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
18.3 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
18.4 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
19 Stack ADT and Implementation 275
19.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
19.2 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
19.3 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
19.4 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
20 Set ADT 279
20.1 Case Study: Airline Travel Agent . . . . . . . . . . . . . . . . . . . . . . . . . . 279
20.2 Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
20.3 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
20.4 Hasher Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
20.5 Competing ADTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
20.6 Selecting a Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
20.7 Summary of Set Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
20.8 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
21 Direct Addressing Data Structure 291
21.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
21.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
21.3 Default Direct Addressing Hasher Class . . . . . . . . . . . . . . . . . . . . . . . 293
21.4 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
© 2008 by Taylor & Francis Group, LLC
xii
21.4.1 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
21.4.2 Trivial Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
21.4.3 Representation Accessors . . . . . . . . . . . . . . . . . . . . . . . . . 294
21.4.4 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
21.4.5 Representation Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . 296
21.4.6 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
21.4.7 Locator Initializers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
21.5 Marker Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
21.6 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
21.7 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
22 Open Addressing Data Structure 305
22.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
22.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
22.3 Default Open Addressing Hasher Class . . . . . . . . . . . . . . . . . . . . . . . 309
22.4 Open Addressing Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
22.4.1 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
22.4.2 Trivial Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
22.4.3 Representation Accessors . . . . . . . . . . . . . . . . . . . . . . . . . 311
22.4.4 Selecting a Hash Function . . . . . . . . . . . . . . . . . . . . . . . . . 312
22.4.5 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
22.4.6 Representation Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . 314
22.4.7 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
22.5 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
22.6 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
23 Separate Chaining Data Structure 321
23.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
23.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
23.3 Chain Item Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
23.4 Default Separate Chaining Hasher Class . . . . . . . . . . . . . . . . . . . . . . 326
23.5 Separate Chaining Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
23.5.1 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
23.5.2 Trivial Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
23.5.3 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
23.5.4 Representation Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . 329
23.5.5 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
23.5.6 Locator Initializers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
23.6 Marker Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
23.7 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
23.8 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
24 Priority Queue ADT 343
24.1 Case Study: Huffman Compression . . . . . . . . . . . . . . . . . . . . . . . . . 343
24.2 Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
24.3 Priority Queue Locator Interface . . . . . . . . . . . . . . . . . . . . . . . . . . 345
24.4 Selecting a Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
24.5 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
24.6 Competing ADTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
24.7 Summary of Priority Queue Data Structures . . . . . . . . . . . . . . . . . . . . 348
24.8 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
© 2008 by Taylor & Francis Group, LLC
xiii
25 Binary Heap Data Structure 353
25.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
25.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
25.3 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
25.3.1 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
25.3.2 Trivial Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
25.3.3 Representation Accessors . . . . . . . . . . . . . . . . . . . . . . . . . 357
25.3.4 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
25.3.5 Representation Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . 358
25.3.6 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
25.3.7 Locator Initializers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
25.4 Locator Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
25.5 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
25.6 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
26 Leftist Heap Data Structure 373
26.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
26.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
26.3 Leftist Heap Node Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
26.4 Leftist Heap Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
26.4.1 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
26.4.2 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
26.4.3 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
26.4.4 Locator Initializers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
26.5 Tracker Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
26.6 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
26.7 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396
27 Pairing Heap Data Structure 399
27.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399
27.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
27.3 Heap Node Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
27.4 Pairing Heap Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405
27.4.1 Constructors and Factory Methods . . . . . . . . . . . . . . . . . . . . . 406
27.4.2 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 406
27.4.3 Representation Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . 407
27.4.4 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
27.4.5 Locator Initializers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
27.5 Tracker Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
27.6 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
27.7 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
28 Fibonacci Heap Data Structure 423
28.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424
28.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426
28.3 Fibonacci Heap Node Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . 426
28.4 Fibonacci Heap Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
28.4.1 Constructors and Factory Methods . . . . . . . . . . . . . . . . . . . . . 428
28.4.2 Representation Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . 429
28.4.3 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
28.5 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437
28.6 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441
© 2008 by Taylor & Francis Group, LLC
xiv
29 Ordered Collection ADT 443
29.1 Case Study: Historical Event Collection (Range Queries) . . . . . . . . . . . . . 443
29.2 Case Study: Linux Virtual Memory Map . . . . . . . . . . . . . . . . . . . . . . 444
29.3 Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
29.4 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446
29.5 Competing ADTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447
29.6 Selecting a Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447
29.7 Summary of Ordered Collection Data Structures . . . . . . . . . . . . . . . . . . 449
29.8 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452
30 Sorted Array Data Structure 455
30.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455
30.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
30.3 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
30.3.1 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
30.3.2 Trivial Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
30.3.3 Binary Search Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 458
30.3.4 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
30.3.5 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464
30.3.6 Utilities for the B-Tree and B+-Tree Classes . . . . . . . . . . . . . . . . 465
30.3.7 Locator Initializers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467
30.4 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467
30.5 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469
31 Abstract Search Tree Class 471
31.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
31.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
31.3 Abstract Tree Node Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . 474
31.4 Abstract Search Tree Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475
31.5 Abstract Search Tree Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475
31.5.1 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475
31.5.2 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 475
31.5.3 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
31.6 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
32 Binary Search Tree Data Structure 481
32.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481
32.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
32.3 BSTNode Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
32.4 Binary Search Tree Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
32.4.1 Constructors and Factory Methods . . . . . . . . . . . . . . . . . . . . . 490
32.4.2 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 490
32.4.3 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496
32.4.4 Locator Initializers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500
32.5 Tracker Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501
32.6 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504
32.7 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
33 Balanced Binary Search Trees 509
33.1 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 510
33.2 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512
© 2008 by Taylor & Francis Group, LLC
xv
34 Red-Black Tree Data Structure 513
34.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
34.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515
34.3 RBNode Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515
34.4 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517
34.4.1 Constructors and Factory Methods . . . . . . . . . . . . . . . . . . . . . 517
34.4.2 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517
34.5 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528
34.6 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528
35 Splay Tree Data Structure 531
35.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
35.2 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532
35.2.1 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532
35.2.2 Representation Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . 533
35.2.3 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 533
35.2.4 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537
35.2.5 Locator Initializers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541
35.3 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541
35.4 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543
36 B-Tree Data Structure 545
36.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546
36.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549
36.3 B-Tree Node Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549
36.3.1 B-Tree Node Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 550
36.3.2 B-Tree Node Representation Mutators . . . . . . . . . . . . . . . . . . . 551
36.3.3 B-Tree Node Content Mutators . . . . . . . . . . . . . . . . . . . . . . . 555
36.4 B-Tree Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557
36.4.1 Constructors and Factory Methods . . . . . . . . . . . . . . . . . . . . . 557
36.4.2 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 558
36.4.3 Representation Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . 562
36.4.4 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563
36.4.5 Locator Initializers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567
36.5 Marker Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568
36.6 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 570
36.7 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573
37 B+-Tree Data Structure 575
37.1 Case Study: A Web Search Engine . . . . . . . . . . . . . . . . . . . . . . . . . 576
37.2 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 577
37.3 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578
37.4 Leaf Node Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 579
37.5 B+-Tree Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583
37.5.1 Constructors and Factory Methods . . . . . . . . . . . . . . . . . . . . . 584
37.5.2 Representation Accessors . . . . . . . . . . . . . . . . . . . . . . . . . 584
37.5.3 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 585
37.5.4 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588
37.6 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589
37.7 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 591
© 2008 by Taylor & Francis Group, LLC
xvi
38 Skip List Data Structure 593
38.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593
38.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 596
38.3 Tower Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 597
38.4 Skip List Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 598
38.4.1 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 598
38.4.2 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 600
38.4.3 Representation Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . 604
38.4.4 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605
38.4.5 Locator Initializers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 610
38.5 Tracker Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 610
38.6 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 613
38.7 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 617
39 Digitized Ordered Collection ADT 619
39.1 Case Study: Packet Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 619
39.2 Case Study: Inverted Index for Text Retrieval . . . . . . . . . . . . . . . . . . . . 620
39.3 Digitized Ordered Collection Interface . . . . . . . . . . . . . . . . . . . . . . . 621
39.4 Selecting a Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 622
39.5 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623
39.6 Competing ADTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624
39.7 Summary of Digitized Ordered Collection Data Structures . . . . . . . . . . . . . 625
39.8 TrieVariations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 630
39.9 Suffix Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 630
39.10 Indexing Tries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 631
39.11 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633
40 Trie Node Types 635
40.1 Trie Node Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 635
40.2 Abstract Trie Node Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 635
40.3 Trie Leaf Node Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 636
40.4 Abstract Trie Leaf Node Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . 637
41 Trie Data Structure 639
41.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 639
41.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 642
41.3 Internal Node Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 642
41.4 Leaf Node Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644
41.5 Search Data Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644
41.6 FindResult Enumerated Type . . . . . . . . . . . . . . . . . . . . . . . . . . . . 649
41.7 Trie Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 650
41.7.1 Constructors and Factory Methods . . . . . . . . . . . . . . . . . . . . . 650
41.7.2 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 651
41.7.3 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 657
41.7.4 Locator Initializers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 661
41.8 Trie Tracker Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 662
41.9 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664
41.10 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667
© 2008 by Taylor & Francis Group, LLC
xvii
42 Compact Trie Data Structure 671
42.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671
42.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 672
42.3 Compact Trie Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 672
42.3.1 Constructors and Factory Methods . . . . . . . . . . . . . . . . . . . . . 673
42.3.2 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 673
42.3.3 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675
42.4 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 679
42.5 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 680
43 Compressed Trie Data Structure 683
43.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 683
43.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 685
43.3 Compressed Trie Node Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . 686
43.4 Internal Node Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 686
43.5 Compressed Trie Leaf Node Inner Class . . . . . . . . . . . . . . . . . . . . . . 687
43.6 Compressed Trie Search Data Inner Class . . . . . . . . . . . . . . . . . . . . . . 687
43.7 Compressed Trie Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 688
43.7.1 Constructors and Factory Methods . . . . . . . . . . . . . . . . . . . . . 688
43.7.2 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 689
43.7.3 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 690
43.8 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 693
43.9 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 694
44 Patricia Trie Data Structure 697
44.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 697
44.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 699
44.3 Patricia Trie Node Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . 700
44.4 Patricia Trie Search Data Inner Class . . . . . . . . . . . . . . . . . . . . . . . . 702
44.5 Patricia Trie Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705
44.5.1 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705
44.5.2 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 706
44.6 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 717
44.7 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 717
45 Ternary Search Trie Data Structure 719
45.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 719
45.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 721
45.3 Ternary Search Trie Internal Node Inner Class . . . . . . . . . . . . . . . . . . . 722
45.4 Ternary Search Trie Search Data Inner Class . . . . . . . . . . . . . . . . . . . . 722
45.5 Ternary Search Trie Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 723
45.5.1 Constructors and Factory Methods . . . . . . . . . . . . . . . . . . . . . 723
45.5.2 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 724
45.6 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725
45.7 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725
46 Spatial Collection ADT 729
46.1 Case Study: Collision Detection in Video Games . . . . . . . . . . . . . . . . . . 729
46.2 Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 730
46.3 Competing ADTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 731
46.4 Summary of Spatial Collection Data Structures . . . . . . . . . . . . . . . . . . . 732
46.5 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 732
© 2008 by Taylor & Francis Group, LLC
xviii
47 KD-Tree Data Structure 735
47.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 736
47.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 739
47.3 Alternating Comparator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 739
47.4 KDNode Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 742
47.5 KDTreeImpl Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 747
47.6 KD-Tree Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 750
47.7 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 752
47.8 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 754
48 Quad Tree Data Structure 757
48.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 757
48.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 760
48.3 Partitioning a Two-Dimensional Space . . . . . . . . . . . . . . . . . . . . . . . 761
48.4 QTNode Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 762
48.5 Box Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 765
48.6 Quad Tree Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 767
48.6.1 Constructors and Factory Methods . . . . . . . . . . . . . . . . . . . . . 767
48.6.2 Representation Accessors . . . . . . . . . . . . . . . . . . . . . . . . . 768
48.6.3 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 768
48.6.4 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 772
48.6.5 Locator Initializers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 781
48.7 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 782
48.8 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 782
49 Tagged Collection ADTs 785
49.1 Tagged Element . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 786
49.1.1 Mutable Tagged Element . . . . . . . . . . . . . . . . . . . . . . . . . . 787
49.1.2 Tagged Element Comparator . . . . . . . . . . . . . . . . . . . . . . . . 787
49.1.3 Tagged Element Digitizer . . . . . . . . . . . . . . . . . . . . . . . . . 788
49.1.4 Tagged Element XY Comparator . . . . . . . . . . . . . . . . . . . . . . 788
49.2 Tagged Collection Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 789
49.3 Tracked Tagged Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 791
49.4 Competing ADTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 791
49.5 Selecting a Tagged Collection ADT . . . . . . . . . . . . . . . . . . . . . . . . . 792
49.6 Tagged Collection Wrapper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 793
49.7 Mapping ADT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 797
49.7.1 Direct Addressing Mapping . . . . . . . . . . . . . . . . . . . . . . . . 799
49.7.2 Open Addressing Mapping . . . . . . . . . . . . . . . . . . . . . . . . . 799
49.7.3 Separate Chaining Mapping . . . . . . . . . . . . . . . . . . . . . . . . 801
49.8 Tagged Priority Queue ADT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 801
49.8.1 Tagged Priority Queue Wrapper . . . . . . . . . . . . . . . . . . . . . . 803
49.8.2 Tagged Binary Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . 806
49.8.3 Tagged Leftist Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . 806
49.8.4 Tagged Pairing Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . 807
49.8.5 Tagged Fibonacci Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . 807
49.9 Tagged Ordered Collection ADT . . . . . . . . . . . . . . . . . . . . . . . . . . 807
49.9.1 Tagged Ordered Collection Wrapper . . . . . . . . . . . . . . . . . . . . 811
49.9.2 Tagged Sorted Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . 812
49.9.3 Tagged Binary Search Tree . . . . . . . . . . . . . . . . . . . . . . . . . 813
49.9.4 Tagged Splay Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 813
© 2008 by Taylor & Francis Group, LLC
xix
49.9.5 Tagged Red-Black Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . 813
49.9.6 Tagged B-Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 813
49.9.7 Tagged B+-Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 814
49.9.8 Tagged Skip List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 814
49.10 Tagged Digitized Ordered Collection ADT . . . . . . . . . . . . . . . . . . . . . 814
49.10.1 Tagged Digitized Ordered Collection Wrapper . . . . . . . . . . . . . . 818
49.10.2 Tagged Trie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 818
49.10.3 Tagged Compact Trie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 819
49.10.4 Tagged Compressed Trie . . . . . . . . . . . . . . . . . . . . . . . . . . 819
49.10.5 Tagged Patricia Trie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 819
49.10.6 Tagged Ternary Search Trie . . . . . . . . . . . . . . . . . . . . . . . . 819
49.11 Tagged Spatial Collection ADT . . . . . . . . . . . . . . . . . . . . . . . . . . . 820
49.11.1 Tagged Spatial Collection Wrapper . . . . . . . . . . . . . . . . . . . . 821
49.11.2 Tagged KD-Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 822
49.11.3 Tagged Quad Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 823
50 Tagged Bucket Collection ADTs 825
50.1 Case Study: Historical Event Collection (Indexing) . . . . . . . . . . . . . . . . . 826
50.2 Case Study: Biosequence Comparison . . . . . . . . . . . . . . . . . . . . . . . 828
50.3 Bucket Factory Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 829
50.4 Tagged Bucket Collection Interface . . . . . . . . . . . . . . . . . . . . . . . . . 829
50.5 Selecting a Tagged Bucket Collection ADT . . . . . . . . . . . . . . . . . . . . . 831
50.6 Selecting a Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 832
50.7 Tagged Bucket Collection Wrapper . . . . . . . . . . . . . . . . . . . . . . . . . 832
III GRAPH DATA STRUCTURES AND ALGORITHMS 839
51 Part III Organization 841
52 Graph ADT 843
52.1 Case Study: Task Scheduler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 844
52.2 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 845
52.3 Edge Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 848
52.4 Graph Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 848
52.5 Graph Representation Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . 850
52.6 Selecting a Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 851
52.7 Summary of Graph Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . 854
53 Abstract Graph and Graph Algorithms 857
53.1 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 858
53.2 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 858
53.3 In-Tree Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 861
53.4 Finding Shortest Paths with Breadth-First Search . . . . . . . . . . . . . . . . . . 865
53.5 Finding Cycles and Connected Components with Depth-First Search . . . . . . . 867
53.6 Topological Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 873
53.7 Strongly Connected Components . . . . . . . . . . . . . . . . . . . . . . . . . . 875
53.8 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 878
53.9 Case Study: Garbage Collection . . . . . . . . . . . . . . . . . . . . . . . . . . . 878
53.10 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 880
53.11 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 881
© 2008 by Taylor & Francis Group, LLC
xx
54 Adjacency Matrix Data Structure 883
54.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 883
54.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 886
54.3 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 887
54.3.1 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 887
54.3.2 Trivial Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 888
54.3.3 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 888
54.3.4 Representation Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . 889
54.3.5 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 890
54.4 Edge Iterators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 893
54.5 Incident Edge Iterator Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . 893
54.6 Adjacency Matrix Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 896
54.7 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 897
54.8 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 898
55 Adjacency List Data Structure 901
55.1 Internal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 902
55.2 Representation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 905
55.3 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 906
55.3.1 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 906
55.3.2 Trivial Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 906
55.3.3 Algorithmic Accessors . . . . . . . . . . . . . . . . . . . . . . . . . . . 906
55.3.4 Content Mutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 908
55.4 Edge Iterators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 910
55.5 Edge Iterator Inner Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 910
55.6 Adjacency List Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 912
55.7 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 912
55.8 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 915
56 Weighted Graph ADT 917
56.1 Case Study: Airline Travel Agent (Revisited) . . . . . . . . . . . . . . . . . . . . 917
56.2 Case Study: Image Segmentation . . . . . . . . . . . . . . . . . . . . . . . . . . 919
56.3 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 921
56.4 Weighted Edge Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 922
56.5 Simple Weighted Edge Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . 922
56.6 Weighted Graph Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 923
56.7 Selecting a Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 923
56.8 Weighted Adjacency Matrix Data Structure . . . . . . . . . . . . . . . . . . . . . 924
56.9 Weighted Adjacency List Data Structure . . . . . . . . . . . . . . . . . . . . . . 924
57 Abstract Weighted Graph andWeighted Graph Algorithms 925
57.1 Greedy Tree Builder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 926
57.2 Dijkstra’s Single-Source Shortest Path Algorithm . . . . . . . . . . . . . . . . . . 931
57.3 Prim’s Minimum Spanning Tree Algorithm . . . . . . . . . . . . . . . . . . . . . 935
57.4 Kruskal’s Minimum Spanning Tree Algorithm . . . . . . . . . . . . . . . . . . . 938
57.5 Bellman-Ford’s Single-Source Shortest Path Algorithm . . . . . . . . . . . . . . 941
57.6 Shortest Path Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 943
57.7 Floyd-Warshall’s All-Pairs Shortest Path Algorithm . . . . . . . . . . . . . . . . 945
57.8 Edmonds-Karp Maximum Flow Algorithm . . . . . . . . . . . . . . . . . . . . . 948
57.9 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 954
57.10 Quick Method Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 955
© 2008 by Taylor & Francis Group, LLC
xxi