Data Structures and Algorithms in C++
2nd Edition
Published on 18. March 2011
Book
Paperback/Softback
736 pages
978-0-470-38327-8 (ISBN)
Description
This second edition of Data Structures and Algorithms in C++ is designed to provide an introduction to data structures and algorithms, including their design, analysis, and implementation. The authors offer an introduction to object-oriented design with C++ and design patterns, including the use of class inheritance and generic programming through class and function templates, and retain a consistent object-oriented viewpoint throughout the book. This is a "sister" book to Goodrich & Tamassia's Data Structures and Algorithms in Java, but uses C++ as the basis language instead of Java. This C++ version retains the same pedagogical approach and general structure as the Java version so schools that teach data structures in both C++ and Java can share the same core syllabus.
In terms of curricula based on the IEEE/ACM 2001 Computing Curriculum, this book is appropriate for use in the courses CS102 (I/O/B versions), CS103 (I/O/B versions), CS111 (A version), and CS112 (A/I/O/F/H versions).
In terms of curricula based on the IEEE/ACM 2001 Computing Curriculum, this book is appropriate for use in the courses CS102 (I/O/B versions), CS103 (I/O/B versions), CS111 (A version), and CS112 (A/I/O/F/H versions).
More details
Edition
2nd edition
Language
English
Place of publication
New York
United States
Target group
College/higher education
Professional and scholarly
Product notice
Paperback (trade)
Unsewn / adhesive bound
Dimensions
Height: 233 mm
Width: 189 mm
Thickness: 30 mm
Weight
1023 gr
ISBN-13
978-0-470-38327-8 (9780470383278)
Schweitzer Classification
Other editions
Previous edition
Michael T. Goodrich | Roberto Tamassia | David Mount
Data Structures and Algorithms in C++
Book
02/2003
1st Edition
Wiley
€39.90
Article exhausted; check for reprint
Persons
Michael Goodrich received his Ph.D. in computer science from Purdue University in 1987. He is currently a professor in the Department of Computer Science at University of California, Irvine. Previously, he was a professor at Johns Hopkins University. He is an editor for the International Journal of Computational Geometry & Applications and Journal of Graph Algorithms and Applications.
Roberto Tamassia received his Ph.D. in Electrical and Computer Engineering from the University of Illinois at Urbana-Champaign in 1988. He is currently a professor in the Department of Computer Science at Brown University. He is editor-in-chief for the Journal of Graph Algorithms and Applications and an editor for Computational Geometry: Theory and Applications. He previously served on the editorial board of IEEE Transactions on Computers.
Roberto Tamassia received his Ph.D. in Electrical and Computer Engineering from the University of Illinois at Urbana-Champaign in 1988. He is currently a professor in the Department of Computer Science at Brown University. He is editor-in-chief for the Journal of Graph Algorithms and Applications and an editor for Computational Geometry: Theory and Applications. He previously served on the editorial board of IEEE Transactions on Computers.
Content
1 A C++ Primer 1
1.1 Basic C++ Programming Elements 2
1.1.1 A Simple C++ Program 2
1.1.2 Fundamental Types 4
1.1.3 Pointers, Arrays, and Structures 7
1.1.4 Named Constants, Scope, and Namespaces 13
1.2 Expressions 16
1.2.1 Changing Types through Casting 20
1.3 Control Flow 23
1.4 Functions 26
1.4.1 Argument Passing 28
1.4.2 Overloading and Inlining 30
1.5 Classes 32
1.5.1 Class Structure 33
1.5.2 Constructors and Destructors 37
1.5.3 Classes and Memory Allocation 40
1.5.4 Class Friends and Class Members 43
1.5.5 The Standard Template Library 45
1.6 C++ Program and File Organization 47
1.6.1 An Example Program 48
1.7 Writing a C++ Program53
1.7.1 Design 54
1.7.2 Pseudo-Code 54
1.7.3 Coding 55
1.7.4 Testing and Debugging 57
1.8 Exercises 60
2 Object-Oriented Design 65
2.1 Goals, Principles, and Patterns 66
2.1.1 Object-Oriented Design Goals 66
2.1.2 Object-Oriented Design Principles 67
2.1.3 Design Patterns 70
2.2 Inheritance and Polymorphism 71
2.2.1 Inheritance in C++ 71
2.2.2 Polymorphism 78
2.2.3 Examples of Inheritance in C++ 79
2.2.4 Multiple Inheritance and Class Casting 84
2.2.5 Interfaces and Abstract Classes 87
2.3 Templates 90
2.3.1 Function Templates 90
2.3.2 Class Templates 91
2.4 Exceptions 93
2.4.1 Exception Objects 93
2.4.2 Throwing and Catching Exceptions 94
2.4.3 Exception Specification 96
2.5 Exercises 98
3 Arrays, Linked Lists, and Recursion 103
3.1 Using Arrays 104
3.1.1 Storing Game Entries in an Array 104
3.1.2 Sorting an Array 109
3.1.3 Two-Dimensional Arrays and Positional Games 111
3.2 Singly Linked Lists 117
3.2.1 Implementing a Singly Linked List 117
3.2.2 Insertion to the Front of a Singly Linked List 119
3.2.3 Removal from the Front of a Singly Linked List 119
3.2.4 Implementing a Generic Singly Linked List 121
3.3 Doubly Linked Lists 123
3.3.1 Insertion into a Doubly Linked List 123
3.3.2 Removal from a Doubly Linked List 124
3.3.3 A C++ Implementation 125
3.4 Circularly Linked Lists and List Reversal 129
3.4.1 Circularly Linked Lists 129
3.4.2 Reversing a Linked List 133
3.5 Recursion 134
3.5.1 Linear Recursion 140
3.5.2 Binary Recursion 144
3.5.3 Multiple Recursion 147
3.6 Exercises 149
4 Analysis Tools 153
4.1 The Seven Functions Used in This Book 154
4.1.1 The Constant Function 154
4.1.2 The Logarithm Function 154
4.1.3 The Linear Function 156
4.1.4 The N-Log-N Function 156
4.1.5 The Quadratic Function 156
4.1.6 The Cubic Function and Other Polynomials 158
4.1.7 The Exponential Function 159
4.1.8 Comparing Growth Rates 161
4.2 Analysis of Algorithms 162
4.2.1 Experimental Studies 163
4.2.2 Primitive Operations 164
4.2.3 Asymptotic Notation 166
4.2.4 Asymptotic Analysis 170
4.2.5 Using the Big-Oh Notation 172
4.2.6 A Recursive Algorithm for Computing Powers 176
4.2.7 Some More Examples of Algorithm Analysis 177
4.3 Simple Justification Techniques 181
4.3.1 By Example 181
4.3.2 The "Contra" Attack 181
4.3.3 Induction and Loop Invariants 182
4.4 Exercises 185
5 Stacks, Queues, and Deques 193
5.1 Stacks 194
5.1.1 The Stack Abstract Data Type 195
5.1.2 The STL Stack 196
5.1.3 A C++ Stack Interface 196
5.1.4 A Simple Array-Based Stack Implementation 198
5.1.5 Implementing a Stack with a Generic Linked List 202
5.1.6 Reversing a Vector Using a Stack 203
5.1.7 Matching Parentheses and HTML Tags 204
5.2 Queues 208
5.2.1 The Queue Abstract Data Type 208
5.2.2 The STL Queue 209
5.2.3 A C++ Queue Interface 210
5.2.4 A Simple Array-Based Implementation 211
5.2.5 Implementing a Queue with a Circularly Linked List 213
5.3 Double-Ended Queues 217
5.3.1 The Deque Abstract Data Type 217
5.3.2 The STL Deque 218
5.3.3 Implementing a Deque with a Doubly Linked List 218
5.3.4 Adapters and the Adapter Design Pattern 220
5.4 Exercises 223
6 List and Iterator ADTs 227
6.1 Vectors 228
6.1.1 The Vector Abstract Data Type 228
6.1.2 A Simple Array-Based Implementation 229
6.1.3 An Extendable Array Implementation 231
6.1.4 STL Vectors 236
6.2 Lists 238
6.2.1 Node-Based Operations and Iterators 238
6.2.2 The List Abstract Data Type 240
6.2.3 Doubly Linked List Implementation 242
6.2.4 STL Lists 247
6.2.5 STL Containers and Iterators 248
6.3 Sequences 255
6.3.1 The Sequence Abstract Data Type 255
6.3.2 Implementing a Sequence with a Doubly Linked List .255
6.3.3 Implementing a Sequence with an Array 257
6.4 Case Study: Bubble-Sort on a Sequence 259
6.4.1 The Bubble-Sort Algorithm 259
6.4.2 A Sequence-Based Analysis of Bubble-Sort 260
6.5 Exercises 262
7 Trees 267
7.1 General Trees 268
7.1.1 Tree Definitions and Properties 269
7.1.2 Tree Functions 272
7.1.3 A C++ Tree Interface 273
7.1.4 A Linked Structure for General Trees 274
7.2 Tree Traversal Algorithms 275
7.2.1 Depth and Height 275
7.2.2 Preorder Traversal 278
7.2.3 Postorder Traversal 281
7.3 Binary Trees 284
7.3.1 The Binary Tree ADT 285
7.3.2 A C++ Binary Tree Interface 286
7.3.3 Properties of Binary Trees 287
7.3.4 A Linked Structure for Binary Trees 289
7.3.5 A Vector-Based Structure for Binary Trees 295
7.3.6 Traversals of a Binary Tree 297
7.3.7 The Template Function Pattern 303
7.3.8 Representing General Trees with Binary Trees 309
7.4 Exercises 310
8 Heaps and Priority Queues 321
8.1 The Priority Queue Abstract Data Type 322
8.1.1 Keys, Priorities, and Total Order Relations 322
8.1.2 Comparators 324
8.1.3 The Priority Queue ADT 327
8.1.4 A C++ Priority Queue Interface 328
8.1.5 Sorting with a Priority Queue 329
8.1.6 The STL priority queue Class 330
8.2 Implementing a Priority Queue with a List 331
8.2.1 A C++ Priority Queue Implementation using a List 333
8.2.2 Selection-Sort and Insertion-Sort 335
8.3 Heaps 337
8.3.1 The Heap Data Structure 337
8.3.2 Complete Binary Trees and Their Representation 340
8.3.3 Implementing a Priority Queue with a Heap 344
8.3.4 C++ Implementation 349
8.3.5 Heap-Sort 351
8.3.6 Bottom-Up Heap Construction ? 353
8.4 Adaptable Priority Queues 357
8.4.1 A List-Based Implementation 358
8.4.2 Location-Aware Entries 360
8.5 Exercises 361
9 Hash Tables, Maps, and Skip Lists 367
9.1 Maps 368
9.1.1 The Map ADT 369
9.1.2 A C++ Map Interface 371
9.1.3 The STL map Class 372
9.1.4 A Simple List-Based Map Implementation 374
9.2 Hash Tables 375
9.2.1 Bucket Arrays 375
9.2.2 Hash Functions 376
9.2.3 Hash Codes 376
9.2.4 Compression Functions 380
9.2.5 Collision-Handling Schemes 382
9.2.6 Load Factors and Rehashing 386
9.2.7 A C++ Hash Table Implementation 387
9.3 Ordered Maps 394
9.3.1 Ordered Search Tables and Binary Search 395
9.3.2 Two Applications of Ordered Maps 399
9.4 Skip Lists 402
9.4.1 Search and Update Operations in a Skip List 404
9.4.2 A Probabilistic Analysis of Skip Lists ? 408
9.5 Dictionaries 411
9.5.1 The Dictionary ADT 411
9.5.2 A C++ Dictionary Implementation 413
9.5.3 Implementations with Location-Aware Entries 415
9.6 Exercises 417
10 Search Trees 423
10.1 Binary Search Trees 424
10.1.1 Searching 426
10.1.2 Update Operations 428
10.1.3 C++ Implementation of a Binary Search Tree 432
10.2 AVL Trees438
10.2.1 Update Operations 440
10.2.2 C++ Implementation of an AVL Tree 446
10.3 Splay Trees 450
10.3.1 Splaying 450
10.3.2 When to Splay 454
10.3.3 Amortized Analysis of Splaying ?456
10.4 (2,4) Trees 461
10.4.1 Multi-Way Search Trees 461
10.4.2 Update Operations for (2,4) Trees 467
10.5 Red-Black Trees473
10.5.1 Update Operations 475
10.5.2 C++ Implementation of a Red-Black Tree 488
10.6 Exercises 492
11 Sorting, Sets, and Selection 499
11.1 Merge-Sort500
11.1.1 Divide-and-Conquer 500
11.1.2 Merging Arrays and Lists 505
11.1.3 The Running Time of Merge-Sort 508
11.1.4 C++ Implementations of Merge-Sort 509
11.1.5 Merge-Sort and Recurrence Equations ? 511
11.2 Quick-Sort 513
11.2.1 Randomized Quick-Sort 521
11.2.2 C++ Implementations and Optimizations 523
11.3 Studying Sorting through an Algorithmic Lens 526
11.3.1 A Lower Bound for Sorting 526
11.3.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort 528
11.3.3 Comparing Sorting Algorithms 531
11.4 Sets and Union/Find Structures 533
11.4.1 The Set ADT 533
11.4.2 Mergable Sets and the Template Method Pattern 534
11.4.3 Partitions with Union-Find Operations 538
11.5 Selection 542
11.5.1 Prune-and-Search 542
11.5.2 Randomized Quick-Select 543
11.5.3 Analyzing Randomized Quick-Select 544
11.6 Exercises 545
12 Strings and Dynamic Programming 553
12.1 String Operations 554
12.1.1 The STL String Class 555
12.2 Dynamic Programming 557
12.2.1 Matrix Chain-Product 557
12.2.2 DNA and Text Sequence Alignment 560
12.3 Pattern Matching Algorithms 564
12.3.1 Brute Force 564
12.3.2 The Boyer-Moore Algorithm 566
12.3.3 The Knuth-Morris-Pratt Algorithm 570
12.4 Text Compression and the Greedy Method 575
12.4.1 The Huffman-Coding Algorithm 576
12.4.2 The Greedy Method 577
12.5 Tries 578
12.5.1 Standard Tries 578
12.5.2 Compressed Tries 582
12.5.3 Suffix Tries 584
12.5.4 Search Engines 586
12.6 Exercises 587
13 Graph Algorithms 593
13.1 Graphs 594
13.1.1 The Graph ADT 599
13.2 Data Structures for Graphs 600
13.2.1 The Edge List Structure 600
13.2.2 The Adjacency List Structure 603
13.2.3 The Adjacency Matrix Structure 605
13.3 Graph Traversals 607
13.3.1 Depth-First Search 607
13.3.2 Implementing Depth-First Search 611
13.3.3 A Generic DFS Implementation in C++ 613
13.3.4 Polymorphic Objects and Decorator Values ? 621
13.3.5 Breadth-First Search 623
13.4 Directed Graphs 626
13.4.1 Traversing a Digraph 628
13.4.2 Transitive Closure 630
13.4.3 Directed Acyclic Graphs 633
13.5 Shortest Paths 637
13.5.1 Weighted Graphs 637
13.5.2 Dijkstra's Algorithm 639
13.6 Minimum Spanning Trees 645
13.6.1 Kruskal's Algorithm 647
13.6.2 The Prim-Jarn?ik Algorithm 651
13.7 Exercises 654
14 Memory Management and B-Trees 665
14.1 Memory Management 666
14.1.1 Memory Allocation in C++ 669
14.1.2 Garbage Collection 671
14.2 External Memory and Caching 673
14.2.1 The Memory Hierarchy 673
14.2.2 Caching Strategies 674
14.3 External Searching and B-Trees679
14.3.1 (a,b) Trees 680
14.3.2 B-Trees 682
14.4 External-Memory Sorting 683
14.4.1 Multi-Way Merging 684
14.5 Exercises 685
A Useful Mathematical Facts 689
Bibliography 697
Index 702
1 A C++ Primer 1
1.1 Basic C++ Programming Elements 2
1.1.1 A Simple C++ Program 2
1.1.2 Fundamental Types 4
1.1.3 Pointers, Arrays, and Structures 7
1.1.4 Named Constants, Scope, and Namespaces 13
1.2 Expressions 16
1.2.1 Changing Types through Casting 20
1.3 Control Flow 23
1.4 Functions 26
1.4.1 Argument Passing 28
1.4.2 Overloading and Inlining 30
1.5 Classes 32
1.5.1 Class Structure 33
1.5.2 Constructors and Destructors 37
1.5.3 Classes and Memory Allocation 40
1.5.4 Class Friends and Class Members 43
1.5.5 The Standard Template Library 45
1.6 C++ Program and File Organization 47
1.6.1 An Example Program 48
1.7 Writing a C++ Program53
1.7.1 Design 54
1.7.2 Pseudo-Code 54
1.7.3 Coding 55
1.7.4 Testing and Debugging 57
1.8 Exercises 60
2 Object-Oriented Design 65
2.1 Goals, Principles, and Patterns 66
2.1.1 Object-Oriented Design Goals 66
2.1.2 Object-Oriented Design Principles 67
2.1.3 Design Patterns 70
2.2 Inheritance and Polymorphism 71
2.2.1 Inheritance in C++ 71
2.2.2 Polymorphism 78
2.2.3 Examples of Inheritance in C++ 79
2.2.4 Multiple Inheritance and Class Casting 84
2.2.5 Interfaces and Abstract Classes 87
2.3 Templates 90
2.3.1 Function Templates 90
2.3.2 Class Templates 91
2.4 Exceptions 93
2.4.1 Exception Objects 93
2.4.2 Throwing and Catching Exceptions 94
2.4.3 Exception Specification 96
2.5 Exercises 98
3 Arrays, Linked Lists, and Recursion 103
3.1 Using Arrays 104
3.1.1 Storing Game Entries in an Array 104
3.1.2 Sorting an Array 109
3.1.3 Two-Dimensional Arrays and Positional Games 111
3.2 Singly Linked Lists 117
3.2.1 Implementing a Singly Linked List 117
3.2.2 Insertion to the Front of a Singly Linked List 119
3.2.3 Removal from the Front of a Singly Linked List 119
3.2.4 Implementing a Generic Singly Linked List 121
3.3 Doubly Linked Lists 123
3.3.1 Insertion into a Doubly Linked List 123
3.3.2 Removal from a Doubly Linked List 124
3.3.3 A C++ Implementation 125
3.4 Circularly Linked Lists and List Reversal 129
3.4.1 Circularly Linked Lists 129
3.4.2 Reversing a Linked List 133
3.5 Recursion 134
3.5.1 Linear Recursion 140
3.5.2 Binary Recursion 144
3.5.3 Multiple Recursion 147
3.6 Exercises 149
4 Analysis Tools 153
4.1 The Seven Functions Used in This Book 154
4.1.1 The Constant Function 154
4.1.2 The Logarithm Function 154
4.1.3 The Linear Function 156
4.1.4 The N-Log-N Function 156
4.1.5 The Quadratic Function 156
4.1.6 The Cubic Function and Other Polynomials 158
4.1.7 The Exponential Function 159
4.1.8 Comparing Growth Rates 161
4.2 Analysis of Algorithms 162
4.2.1 Experimental Studies 163
4.2.2 Primitive Operations 164
4.2.3 Asymptotic Notation 166
4.2.4 Asymptotic Analysis 170
4.2.5 Using the Big-Oh Notation 172
4.2.6 A Recursive Algorithm for Computing Powers 176
4.2.7 Some More Examples of Algorithm Analysis 177
4.3 Simple Justification Techniques 181
4.3.1 By Example 181
4.3.2 The "Contra" Attack 181
4.3.3 Induction and Loop Invariants 182
4.4 Exercises 185
5 Stacks, Queues, and Deques 193
5.1 Stacks 194
5.1.1 The Stack Abstract Data Type 195
5.1.2 The STL Stack 196
5.1.3 A C++ Stack Interface 196
5.1.4 A Simple Array-Based Stack Implementation 198
5.1.5 Implementing a Stack with a Generic Linked List 202
5.1.6 Reversing a Vector Using a Stack 203
5.1.7 Matching Parentheses and HTML Tags 204
5.2 Queues 208
5.2.1 The Queue Abstract Data Type 208
5.2.2 The STL Queue 209
5.2.3 A C++ Queue Interface 210
5.2.4 A Simple Array-Based Implementation 211
5.2.5 Implementing a Queue with a Circularly Linked List 213
5.3 Double-Ended Queues 217
5.3.1 The Deque Abstract Data Type 217
5.3.2 The STL Deque 218
5.3.3 Implementing a Deque with a Doubly Linked List 218
5.3.4 Adapters and the Adapter Design Pattern 220
5.4 Exercises 223
6 List and Iterator ADTs 227
6.1 Vectors 228
6.1.1 The Vector Abstract Data Type 228
6.1.2 A Simple Array-Based Implementation 229
6.1.3 An Extendable Array Implementation 231
6.1.4 STL Vectors 236
6.2 Lists 238
6.2.1 Node-Based Operations and Iterators 238
6.2.2 The List Abstract Data Type 240
6.2.3 Doubly Linked List Implementation 242
6.2.4 STL Lists 247
6.2.5 STL Containers and Iterators 248
6.3 Sequences255
6.3.1 The Sequence Abstract Data Type 255
6.3.2 Implementing a Sequence with a Doubly Linked List .255
6.3.3 Implementing a Sequence with an Array 257
6.4 Case Study: Bubble-Sort on a Sequence 259
6.4.1 The Bubble-Sort Algorithm 259
6.4.2 A Sequence-Based Analysis of Bubble-Sort 260
6.5 Exercises 262
7 Trees 267
7.1 General Trees 268
7.1.1 Tree Definitions and Properties 269
7.1.2 Tree Functions 272
7.1.3 A C++ Tree Interface 273
7.1.4 A Linked Structure for General Trees 274
7.2 Tree Traversal Algorithms 275
7.2.1 Depth and Height 275
7.2.2 Preorder Traversal 278
7.2.3 Postorder Traversal 281
7.3 Binary Trees 284
7.3.1 The Binary Tree ADT 285
7.3.2 A C++ Binary Tree Interface 286
7.3.3 Properties of Binary Trees 287
7.3.4 A Linked Structure for Binary Trees 289
7.3.5 A Vector-Based Structure for Binary Trees 295
7.3.6 Traversals of a Binary Tree 297
7.3.7 The Template Function Pattern 303
7.3.8 Representing General Trees with Binary Trees 309
7.4 Exercises 310
8 Heaps and Priority Queues 321
8.1 The Priority Queue Abstract Data Type 322
8.1.1 Keys, Priorities, and Total Order Relations 322
8.1.2 Comparators 324
8.1.3 The Priority Queue ADT 327
8.1.4 A C++ Priority Queue Interface 328
8.1.5 Sorting with a Priority Queue 329
8.1.6 The STL priority queue Class 330
8.2 Implementing a Priority Queue with a List 331
8.2.1 A C++ Priority Queue Implementation using a List 333
8.2.2 Selection-Sort and Insertion-Sort 335
8.3 Heaps 337
8.3.1 The Heap Data Structure 337
8.3.2 Complete Binary Trees and Their Representation 340
8.3.3 Implementing a Priority Queue with a Heap 344
8.3.4 C++ Implementation 349
8.3.5 Heap-Sort 351
8.3.6 Bottom-Up Heap Construction ?353
8.4 Adaptable Priority Queues 357
8.4.1 A List-Based Implementation 358
8.4.2 Location-Aware Entries 360
8.5 Exercises 361
9 Hash Tables, Maps, and Skip Lists 367
9.1 Maps 368
9.1.1 The Map ADT 369
9.1.2 A C++ Map Interface 371
9.1.3 The STL map Class 372
9.1.4 A Simple List-Based Map Implementation 374
9.2 Hash Tables 375
9.2.1 Bucket Arrays 375
9.2.2 Hash Functions 376
9.2.3 Hash Codes 376
9.2.4 Compression Functions 380
9.2.5 Collision-Handling Schemes 382
9.2.6 Load Factors and Rehashing 386
9.2.7 A C++ Hash Table Implementation 387
9.3 Ordered Maps 394
9.3.1 Ordered Search Tables and Binary Search 395
9.3.2 Two Applications of Ordered Maps 399
9.4 Skip Lists 402
9.4.1 Search and Update Operations in a Skip List 404
9.4.2 A Probabilistic Analysis of Skip Lists ?408
9.5 Dictionaries 411
9.5.1 The Dictionary ADT 411
9.5.2 A C++ Dictionary Implementation 413
9.5.3 Implementations with Location-Aware Entries 415
9.6 Exercises 417
10 Search Trees 423
10.1 Binary Search Trees 424
10.1.1 Searching 426
10.1.2 Update Operations 428
10.1.3 C++ Implementation of a Binary Search Tree 432
10.2 AVL Trees438
10.2.1 Update Operations 440
10.2.2 C++ Implementation of an AVL Tree 446
10.3 Splay Trees 450
10.3.1 Splaying 450
10.3.2 When to Splay 454
10.3.3 Amortized Analysis of Splaying ?456
10.4 (2,4) Trees 461
10.4.1 Multi-Way Search Trees 461
10.4.2 Update Operations for (2,4) Trees 467
10.5 Red-Black Trees473
10.5.1 Update Operations 475
10.5.2 C++ Implementation of a Red-Black Tree 488
10.6 Exercises 492
11 Sorting, Sets, and Selection 499
11.1 Merge-Sort500
11.1.1 Divide-and-Conquer 500
11.1.2 Merging Arrays and Lists 505
11.1.3 The Running Time of Merge-Sort 508
11.1.4 C++ Implementations of Merge-Sort 509
11.1.5 Merge-Sort and Recurrence Equations ?511
11.2 Quick-Sort 513
11.2.1 Randomized Quick-Sort 521
11.2.2 C++ Implementations and Optimizations 523
11.3 Studying Sorting through an Algorithmic Lens 526
11.3.1 A Lower Bound for Sorting 526
11.3.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort 528
11.3.3 Comparing Sorting Algorithms 531
11.4 Sets and Union/Find Structures 533
11.4.1 The Set ADT 533
11.4.2 Mergable Sets and the Template Method Pattern 534
11.4.3 Partitions with Union-Find Operations 538
11.5 Selection 542
11.5.1 Prune-and-Search 542
11.5.2 Randomized Quick-Select 543
11.5.3 Analyzing Randomized Quick-Select 544
11.6 Exercises 545
12 Strings and Dynamic Programming 553
12.1 String Operations 554
12.1.1 The STL String Class 555
12.2 Dynamic Programming 557
12.2.1 Matrix Chain-Product 557
12.2.2 DNA and Text Sequence Alignment 560
12.3 Pattern Matching Algorithms 564
12.3.1 Brute Force 564
12.3.2 The Boyer-Moore Algorithm 566
12.3.3 The Knuth-Morris-Pratt Algorithm 570
12.4 Text Compression and the Greedy Method 575
12.4.1 The Huffman-Coding Algorithm 576
12.4.2 The Greedy Method 577
12.5 Tries 578
12.5.1 Standard Tries 578
12.5.2 Compressed Tries 582
12.5.3 Suffix Tries 584
12.5.4 Search Engines 586
12.6 Exercises 587
13 Graph Algorithms 593
13.1 Graphs 594
13.1.1 The Graph ADT 599
13.2 Data Structures for Graphs 600
13.2.1 The Edge List Structure 600
13.2.2 The Adjacency List Structure 603
13.2.3 The Adjacency Matrix Structure 605
13.3 Graph Traversals 607
13.3.1 Depth-First Search 607
13.3.2 Implementing Depth-First Search 611
13.3.3 A Generic DFS Implementation in C++ 613
13.3.4 Polymorphic Objects and Decorator Values ?621
13.3.5 Breadth-First Search 623
13.4 Directed Graphs 626
13.4.1 Traversing a Digraph 628
13.4.2 Transitive Closure 630
13.4.3 Directed Acyclic Graphs 633
13.5 Shortest Paths 637
13.5.1 Weighted Graphs 637
13.5.2 Dijkstra's Algorithm 639
13.6 Minimum Spanning Trees 645
13.6.1 Kruskal's Algorithm 647
13.6.2 The Prim-Jarn?ik Algorithm 651
13.7 Exercises 654
14 Memory Management and B-Trees 665
14.1 Memory Management 666
14.1.1 Memory Allocation in C++ 669
14.1.2 Garbage Collection 671
14.2 External Memory and Caching 673
14.2.1 The Memory Hierarchy 673
14.2.2 Caching Strategies 674
14.3 External Searching and B-Trees679
14.3.1 (a,b) Trees 680
14.3.2 B-Trees 682
14.4 External-Memory Sorting 683
14.4.1 Multi-Way Merging 684
14.5 Exercises 685
A Useful Mathematical Facts 689
Bibliography 697
Index 702
1.1 Basic C++ Programming Elements 2
1.1.1 A Simple C++ Program 2
1.1.2 Fundamental Types 4
1.1.3 Pointers, Arrays, and Structures 7
1.1.4 Named Constants, Scope, and Namespaces 13
1.2 Expressions 16
1.2.1 Changing Types through Casting 20
1.3 Control Flow 23
1.4 Functions 26
1.4.1 Argument Passing 28
1.4.2 Overloading and Inlining 30
1.5 Classes 32
1.5.1 Class Structure 33
1.5.2 Constructors and Destructors 37
1.5.3 Classes and Memory Allocation 40
1.5.4 Class Friends and Class Members 43
1.5.5 The Standard Template Library 45
1.6 C++ Program and File Organization 47
1.6.1 An Example Program 48
1.7 Writing a C++ Program53
1.7.1 Design 54
1.7.2 Pseudo-Code 54
1.7.3 Coding 55
1.7.4 Testing and Debugging 57
1.8 Exercises 60
2 Object-Oriented Design 65
2.1 Goals, Principles, and Patterns 66
2.1.1 Object-Oriented Design Goals 66
2.1.2 Object-Oriented Design Principles 67
2.1.3 Design Patterns 70
2.2 Inheritance and Polymorphism 71
2.2.1 Inheritance in C++ 71
2.2.2 Polymorphism 78
2.2.3 Examples of Inheritance in C++ 79
2.2.4 Multiple Inheritance and Class Casting 84
2.2.5 Interfaces and Abstract Classes 87
2.3 Templates 90
2.3.1 Function Templates 90
2.3.2 Class Templates 91
2.4 Exceptions 93
2.4.1 Exception Objects 93
2.4.2 Throwing and Catching Exceptions 94
2.4.3 Exception Specification 96
2.5 Exercises 98
3 Arrays, Linked Lists, and Recursion 103
3.1 Using Arrays 104
3.1.1 Storing Game Entries in an Array 104
3.1.2 Sorting an Array 109
3.1.3 Two-Dimensional Arrays and Positional Games 111
3.2 Singly Linked Lists 117
3.2.1 Implementing a Singly Linked List 117
3.2.2 Insertion to the Front of a Singly Linked List 119
3.2.3 Removal from the Front of a Singly Linked List 119
3.2.4 Implementing a Generic Singly Linked List 121
3.3 Doubly Linked Lists 123
3.3.1 Insertion into a Doubly Linked List 123
3.3.2 Removal from a Doubly Linked List 124
3.3.3 A C++ Implementation 125
3.4 Circularly Linked Lists and List Reversal 129
3.4.1 Circularly Linked Lists 129
3.4.2 Reversing a Linked List 133
3.5 Recursion 134
3.5.1 Linear Recursion 140
3.5.2 Binary Recursion 144
3.5.3 Multiple Recursion 147
3.6 Exercises 149
4 Analysis Tools 153
4.1 The Seven Functions Used in This Book 154
4.1.1 The Constant Function 154
4.1.2 The Logarithm Function 154
4.1.3 The Linear Function 156
4.1.4 The N-Log-N Function 156
4.1.5 The Quadratic Function 156
4.1.6 The Cubic Function and Other Polynomials 158
4.1.7 The Exponential Function 159
4.1.8 Comparing Growth Rates 161
4.2 Analysis of Algorithms 162
4.2.1 Experimental Studies 163
4.2.2 Primitive Operations 164
4.2.3 Asymptotic Notation 166
4.2.4 Asymptotic Analysis 170
4.2.5 Using the Big-Oh Notation 172
4.2.6 A Recursive Algorithm for Computing Powers 176
4.2.7 Some More Examples of Algorithm Analysis 177
4.3 Simple Justification Techniques 181
4.3.1 By Example 181
4.3.2 The "Contra" Attack 181
4.3.3 Induction and Loop Invariants 182
4.4 Exercises 185
5 Stacks, Queues, and Deques 193
5.1 Stacks 194
5.1.1 The Stack Abstract Data Type 195
5.1.2 The STL Stack 196
5.1.3 A C++ Stack Interface 196
5.1.4 A Simple Array-Based Stack Implementation 198
5.1.5 Implementing a Stack with a Generic Linked List 202
5.1.6 Reversing a Vector Using a Stack 203
5.1.7 Matching Parentheses and HTML Tags 204
5.2 Queues 208
5.2.1 The Queue Abstract Data Type 208
5.2.2 The STL Queue 209
5.2.3 A C++ Queue Interface 210
5.2.4 A Simple Array-Based Implementation 211
5.2.5 Implementing a Queue with a Circularly Linked List 213
5.3 Double-Ended Queues 217
5.3.1 The Deque Abstract Data Type 217
5.3.2 The STL Deque 218
5.3.3 Implementing a Deque with a Doubly Linked List 218
5.3.4 Adapters and the Adapter Design Pattern 220
5.4 Exercises 223
6 List and Iterator ADTs 227
6.1 Vectors 228
6.1.1 The Vector Abstract Data Type 228
6.1.2 A Simple Array-Based Implementation 229
6.1.3 An Extendable Array Implementation 231
6.1.4 STL Vectors 236
6.2 Lists 238
6.2.1 Node-Based Operations and Iterators 238
6.2.2 The List Abstract Data Type 240
6.2.3 Doubly Linked List Implementation 242
6.2.4 STL Lists 247
6.2.5 STL Containers and Iterators 248
6.3 Sequences 255
6.3.1 The Sequence Abstract Data Type 255
6.3.2 Implementing a Sequence with a Doubly Linked List .255
6.3.3 Implementing a Sequence with an Array 257
6.4 Case Study: Bubble-Sort on a Sequence 259
6.4.1 The Bubble-Sort Algorithm 259
6.4.2 A Sequence-Based Analysis of Bubble-Sort 260
6.5 Exercises 262
7 Trees 267
7.1 General Trees 268
7.1.1 Tree Definitions and Properties 269
7.1.2 Tree Functions 272
7.1.3 A C++ Tree Interface 273
7.1.4 A Linked Structure for General Trees 274
7.2 Tree Traversal Algorithms 275
7.2.1 Depth and Height 275
7.2.2 Preorder Traversal 278
7.2.3 Postorder Traversal 281
7.3 Binary Trees 284
7.3.1 The Binary Tree ADT 285
7.3.2 A C++ Binary Tree Interface 286
7.3.3 Properties of Binary Trees 287
7.3.4 A Linked Structure for Binary Trees 289
7.3.5 A Vector-Based Structure for Binary Trees 295
7.3.6 Traversals of a Binary Tree 297
7.3.7 The Template Function Pattern 303
7.3.8 Representing General Trees with Binary Trees 309
7.4 Exercises 310
8 Heaps and Priority Queues 321
8.1 The Priority Queue Abstract Data Type 322
8.1.1 Keys, Priorities, and Total Order Relations 322
8.1.2 Comparators 324
8.1.3 The Priority Queue ADT 327
8.1.4 A C++ Priority Queue Interface 328
8.1.5 Sorting with a Priority Queue 329
8.1.6 The STL priority queue Class 330
8.2 Implementing a Priority Queue with a List 331
8.2.1 A C++ Priority Queue Implementation using a List 333
8.2.2 Selection-Sort and Insertion-Sort 335
8.3 Heaps 337
8.3.1 The Heap Data Structure 337
8.3.2 Complete Binary Trees and Their Representation 340
8.3.3 Implementing a Priority Queue with a Heap 344
8.3.4 C++ Implementation 349
8.3.5 Heap-Sort 351
8.3.6 Bottom-Up Heap Construction ? 353
8.4 Adaptable Priority Queues 357
8.4.1 A List-Based Implementation 358
8.4.2 Location-Aware Entries 360
8.5 Exercises 361
9 Hash Tables, Maps, and Skip Lists 367
9.1 Maps 368
9.1.1 The Map ADT 369
9.1.2 A C++ Map Interface 371
9.1.3 The STL map Class 372
9.1.4 A Simple List-Based Map Implementation 374
9.2 Hash Tables 375
9.2.1 Bucket Arrays 375
9.2.2 Hash Functions 376
9.2.3 Hash Codes 376
9.2.4 Compression Functions 380
9.2.5 Collision-Handling Schemes 382
9.2.6 Load Factors and Rehashing 386
9.2.7 A C++ Hash Table Implementation 387
9.3 Ordered Maps 394
9.3.1 Ordered Search Tables and Binary Search 395
9.3.2 Two Applications of Ordered Maps 399
9.4 Skip Lists 402
9.4.1 Search and Update Operations in a Skip List 404
9.4.2 A Probabilistic Analysis of Skip Lists ? 408
9.5 Dictionaries 411
9.5.1 The Dictionary ADT 411
9.5.2 A C++ Dictionary Implementation 413
9.5.3 Implementations with Location-Aware Entries 415
9.6 Exercises 417
10 Search Trees 423
10.1 Binary Search Trees 424
10.1.1 Searching 426
10.1.2 Update Operations 428
10.1.3 C++ Implementation of a Binary Search Tree 432
10.2 AVL Trees438
10.2.1 Update Operations 440
10.2.2 C++ Implementation of an AVL Tree 446
10.3 Splay Trees 450
10.3.1 Splaying 450
10.3.2 When to Splay 454
10.3.3 Amortized Analysis of Splaying ?456
10.4 (2,4) Trees 461
10.4.1 Multi-Way Search Trees 461
10.4.2 Update Operations for (2,4) Trees 467
10.5 Red-Black Trees473
10.5.1 Update Operations 475
10.5.2 C++ Implementation of a Red-Black Tree 488
10.6 Exercises 492
11 Sorting, Sets, and Selection 499
11.1 Merge-Sort500
11.1.1 Divide-and-Conquer 500
11.1.2 Merging Arrays and Lists 505
11.1.3 The Running Time of Merge-Sort 508
11.1.4 C++ Implementations of Merge-Sort 509
11.1.5 Merge-Sort and Recurrence Equations ? 511
11.2 Quick-Sort 513
11.2.1 Randomized Quick-Sort 521
11.2.2 C++ Implementations and Optimizations 523
11.3 Studying Sorting through an Algorithmic Lens 526
11.3.1 A Lower Bound for Sorting 526
11.3.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort 528
11.3.3 Comparing Sorting Algorithms 531
11.4 Sets and Union/Find Structures 533
11.4.1 The Set ADT 533
11.4.2 Mergable Sets and the Template Method Pattern 534
11.4.3 Partitions with Union-Find Operations 538
11.5 Selection 542
11.5.1 Prune-and-Search 542
11.5.2 Randomized Quick-Select 543
11.5.3 Analyzing Randomized Quick-Select 544
11.6 Exercises 545
12 Strings and Dynamic Programming 553
12.1 String Operations 554
12.1.1 The STL String Class 555
12.2 Dynamic Programming 557
12.2.1 Matrix Chain-Product 557
12.2.2 DNA and Text Sequence Alignment 560
12.3 Pattern Matching Algorithms 564
12.3.1 Brute Force 564
12.3.2 The Boyer-Moore Algorithm 566
12.3.3 The Knuth-Morris-Pratt Algorithm 570
12.4 Text Compression and the Greedy Method 575
12.4.1 The Huffman-Coding Algorithm 576
12.4.2 The Greedy Method 577
12.5 Tries 578
12.5.1 Standard Tries 578
12.5.2 Compressed Tries 582
12.5.3 Suffix Tries 584
12.5.4 Search Engines 586
12.6 Exercises 587
13 Graph Algorithms 593
13.1 Graphs 594
13.1.1 The Graph ADT 599
13.2 Data Structures for Graphs 600
13.2.1 The Edge List Structure 600
13.2.2 The Adjacency List Structure 603
13.2.3 The Adjacency Matrix Structure 605
13.3 Graph Traversals 607
13.3.1 Depth-First Search 607
13.3.2 Implementing Depth-First Search 611
13.3.3 A Generic DFS Implementation in C++ 613
13.3.4 Polymorphic Objects and Decorator Values ? 621
13.3.5 Breadth-First Search 623
13.4 Directed Graphs 626
13.4.1 Traversing a Digraph 628
13.4.2 Transitive Closure 630
13.4.3 Directed Acyclic Graphs 633
13.5 Shortest Paths 637
13.5.1 Weighted Graphs 637
13.5.2 Dijkstra's Algorithm 639
13.6 Minimum Spanning Trees 645
13.6.1 Kruskal's Algorithm 647
13.6.2 The Prim-Jarn?ik Algorithm 651
13.7 Exercises 654
14 Memory Management and B-Trees 665
14.1 Memory Management 666
14.1.1 Memory Allocation in C++ 669
14.1.2 Garbage Collection 671
14.2 External Memory and Caching 673
14.2.1 The Memory Hierarchy 673
14.2.2 Caching Strategies 674
14.3 External Searching and B-Trees679
14.3.1 (a,b) Trees 680
14.3.2 B-Trees 682
14.4 External-Memory Sorting 683
14.4.1 Multi-Way Merging 684
14.5 Exercises 685
A Useful Mathematical Facts 689
Bibliography 697
Index 702
1 A C++ Primer 1
1.1 Basic C++ Programming Elements 2
1.1.1 A Simple C++ Program 2
1.1.2 Fundamental Types 4
1.1.3 Pointers, Arrays, and Structures 7
1.1.4 Named Constants, Scope, and Namespaces 13
1.2 Expressions 16
1.2.1 Changing Types through Casting 20
1.3 Control Flow 23
1.4 Functions 26
1.4.1 Argument Passing 28
1.4.2 Overloading and Inlining 30
1.5 Classes 32
1.5.1 Class Structure 33
1.5.2 Constructors and Destructors 37
1.5.3 Classes and Memory Allocation 40
1.5.4 Class Friends and Class Members 43
1.5.5 The Standard Template Library 45
1.6 C++ Program and File Organization 47
1.6.1 An Example Program 48
1.7 Writing a C++ Program53
1.7.1 Design 54
1.7.2 Pseudo-Code 54
1.7.3 Coding 55
1.7.4 Testing and Debugging 57
1.8 Exercises 60
2 Object-Oriented Design 65
2.1 Goals, Principles, and Patterns 66
2.1.1 Object-Oriented Design Goals 66
2.1.2 Object-Oriented Design Principles 67
2.1.3 Design Patterns 70
2.2 Inheritance and Polymorphism 71
2.2.1 Inheritance in C++ 71
2.2.2 Polymorphism 78
2.2.3 Examples of Inheritance in C++ 79
2.2.4 Multiple Inheritance and Class Casting 84
2.2.5 Interfaces and Abstract Classes 87
2.3 Templates 90
2.3.1 Function Templates 90
2.3.2 Class Templates 91
2.4 Exceptions 93
2.4.1 Exception Objects 93
2.4.2 Throwing and Catching Exceptions 94
2.4.3 Exception Specification 96
2.5 Exercises 98
3 Arrays, Linked Lists, and Recursion 103
3.1 Using Arrays 104
3.1.1 Storing Game Entries in an Array 104
3.1.2 Sorting an Array 109
3.1.3 Two-Dimensional Arrays and Positional Games 111
3.2 Singly Linked Lists 117
3.2.1 Implementing a Singly Linked List 117
3.2.2 Insertion to the Front of a Singly Linked List 119
3.2.3 Removal from the Front of a Singly Linked List 119
3.2.4 Implementing a Generic Singly Linked List 121
3.3 Doubly Linked Lists 123
3.3.1 Insertion into a Doubly Linked List 123
3.3.2 Removal from a Doubly Linked List 124
3.3.3 A C++ Implementation 125
3.4 Circularly Linked Lists and List Reversal 129
3.4.1 Circularly Linked Lists 129
3.4.2 Reversing a Linked List 133
3.5 Recursion 134
3.5.1 Linear Recursion 140
3.5.2 Binary Recursion 144
3.5.3 Multiple Recursion 147
3.6 Exercises 149
4 Analysis Tools 153
4.1 The Seven Functions Used in This Book 154
4.1.1 The Constant Function 154
4.1.2 The Logarithm Function 154
4.1.3 The Linear Function 156
4.1.4 The N-Log-N Function 156
4.1.5 The Quadratic Function 156
4.1.6 The Cubic Function and Other Polynomials 158
4.1.7 The Exponential Function 159
4.1.8 Comparing Growth Rates 161
4.2 Analysis of Algorithms 162
4.2.1 Experimental Studies 163
4.2.2 Primitive Operations 164
4.2.3 Asymptotic Notation 166
4.2.4 Asymptotic Analysis 170
4.2.5 Using the Big-Oh Notation 172
4.2.6 A Recursive Algorithm for Computing Powers 176
4.2.7 Some More Examples of Algorithm Analysis 177
4.3 Simple Justification Techniques 181
4.3.1 By Example 181
4.3.2 The "Contra" Attack 181
4.3.3 Induction and Loop Invariants 182
4.4 Exercises 185
5 Stacks, Queues, and Deques 193
5.1 Stacks 194
5.1.1 The Stack Abstract Data Type 195
5.1.2 The STL Stack 196
5.1.3 A C++ Stack Interface 196
5.1.4 A Simple Array-Based Stack Implementation 198
5.1.5 Implementing a Stack with a Generic Linked List 202
5.1.6 Reversing a Vector Using a Stack 203
5.1.7 Matching Parentheses and HTML Tags 204
5.2 Queues 208
5.2.1 The Queue Abstract Data Type 208
5.2.2 The STL Queue 209
5.2.3 A C++ Queue Interface 210
5.2.4 A Simple Array-Based Implementation 211
5.2.5 Implementing a Queue with a Circularly Linked List 213
5.3 Double-Ended Queues 217
5.3.1 The Deque Abstract Data Type 217
5.3.2 The STL Deque 218
5.3.3 Implementing a Deque with a Doubly Linked List 218
5.3.4 Adapters and the Adapter Design Pattern 220
5.4 Exercises 223
6 List and Iterator ADTs 227
6.1 Vectors 228
6.1.1 The Vector Abstract Data Type 228
6.1.2 A Simple Array-Based Implementation 229
6.1.3 An Extendable Array Implementation 231
6.1.4 STL Vectors 236
6.2 Lists 238
6.2.1 Node-Based Operations and Iterators 238
6.2.2 The List Abstract Data Type 240
6.2.3 Doubly Linked List Implementation 242
6.2.4 STL Lists 247
6.2.5 STL Containers and Iterators 248
6.3 Sequences255
6.3.1 The Sequence Abstract Data Type 255
6.3.2 Implementing a Sequence with a Doubly Linked List .255
6.3.3 Implementing a Sequence with an Array 257
6.4 Case Study: Bubble-Sort on a Sequence 259
6.4.1 The Bubble-Sort Algorithm 259
6.4.2 A Sequence-Based Analysis of Bubble-Sort 260
6.5 Exercises 262
7 Trees 267
7.1 General Trees 268
7.1.1 Tree Definitions and Properties 269
7.1.2 Tree Functions 272
7.1.3 A C++ Tree Interface 273
7.1.4 A Linked Structure for General Trees 274
7.2 Tree Traversal Algorithms 275
7.2.1 Depth and Height 275
7.2.2 Preorder Traversal 278
7.2.3 Postorder Traversal 281
7.3 Binary Trees 284
7.3.1 The Binary Tree ADT 285
7.3.2 A C++ Binary Tree Interface 286
7.3.3 Properties of Binary Trees 287
7.3.4 A Linked Structure for Binary Trees 289
7.3.5 A Vector-Based Structure for Binary Trees 295
7.3.6 Traversals of a Binary Tree 297
7.3.7 The Template Function Pattern 303
7.3.8 Representing General Trees with Binary Trees 309
7.4 Exercises 310
8 Heaps and Priority Queues 321
8.1 The Priority Queue Abstract Data Type 322
8.1.1 Keys, Priorities, and Total Order Relations 322
8.1.2 Comparators 324
8.1.3 The Priority Queue ADT 327
8.1.4 A C++ Priority Queue Interface 328
8.1.5 Sorting with a Priority Queue 329
8.1.6 The STL priority queue Class 330
8.2 Implementing a Priority Queue with a List 331
8.2.1 A C++ Priority Queue Implementation using a List 333
8.2.2 Selection-Sort and Insertion-Sort 335
8.3 Heaps 337
8.3.1 The Heap Data Structure 337
8.3.2 Complete Binary Trees and Their Representation 340
8.3.3 Implementing a Priority Queue with a Heap 344
8.3.4 C++ Implementation 349
8.3.5 Heap-Sort 351
8.3.6 Bottom-Up Heap Construction ?353
8.4 Adaptable Priority Queues 357
8.4.1 A List-Based Implementation 358
8.4.2 Location-Aware Entries 360
8.5 Exercises 361
9 Hash Tables, Maps, and Skip Lists 367
9.1 Maps 368
9.1.1 The Map ADT 369
9.1.2 A C++ Map Interface 371
9.1.3 The STL map Class 372
9.1.4 A Simple List-Based Map Implementation 374
9.2 Hash Tables 375
9.2.1 Bucket Arrays 375
9.2.2 Hash Functions 376
9.2.3 Hash Codes 376
9.2.4 Compression Functions 380
9.2.5 Collision-Handling Schemes 382
9.2.6 Load Factors and Rehashing 386
9.2.7 A C++ Hash Table Implementation 387
9.3 Ordered Maps 394
9.3.1 Ordered Search Tables and Binary Search 395
9.3.2 Two Applications of Ordered Maps 399
9.4 Skip Lists 402
9.4.1 Search and Update Operations in a Skip List 404
9.4.2 A Probabilistic Analysis of Skip Lists ?408
9.5 Dictionaries 411
9.5.1 The Dictionary ADT 411
9.5.2 A C++ Dictionary Implementation 413
9.5.3 Implementations with Location-Aware Entries 415
9.6 Exercises 417
10 Search Trees 423
10.1 Binary Search Trees 424
10.1.1 Searching 426
10.1.2 Update Operations 428
10.1.3 C++ Implementation of a Binary Search Tree 432
10.2 AVL Trees438
10.2.1 Update Operations 440
10.2.2 C++ Implementation of an AVL Tree 446
10.3 Splay Trees 450
10.3.1 Splaying 450
10.3.2 When to Splay 454
10.3.3 Amortized Analysis of Splaying ?456
10.4 (2,4) Trees 461
10.4.1 Multi-Way Search Trees 461
10.4.2 Update Operations for (2,4) Trees 467
10.5 Red-Black Trees473
10.5.1 Update Operations 475
10.5.2 C++ Implementation of a Red-Black Tree 488
10.6 Exercises 492
11 Sorting, Sets, and Selection 499
11.1 Merge-Sort500
11.1.1 Divide-and-Conquer 500
11.1.2 Merging Arrays and Lists 505
11.1.3 The Running Time of Merge-Sort 508
11.1.4 C++ Implementations of Merge-Sort 509
11.1.5 Merge-Sort and Recurrence Equations ?511
11.2 Quick-Sort 513
11.2.1 Randomized Quick-Sort 521
11.2.2 C++ Implementations and Optimizations 523
11.3 Studying Sorting through an Algorithmic Lens 526
11.3.1 A Lower Bound for Sorting 526
11.3.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort 528
11.3.3 Comparing Sorting Algorithms 531
11.4 Sets and Union/Find Structures 533
11.4.1 The Set ADT 533
11.4.2 Mergable Sets and the Template Method Pattern 534
11.4.3 Partitions with Union-Find Operations 538
11.5 Selection 542
11.5.1 Prune-and-Search 542
11.5.2 Randomized Quick-Select 543
11.5.3 Analyzing Randomized Quick-Select 544
11.6 Exercises 545
12 Strings and Dynamic Programming 553
12.1 String Operations 554
12.1.1 The STL String Class 555
12.2 Dynamic Programming 557
12.2.1 Matrix Chain-Product 557
12.2.2 DNA and Text Sequence Alignment 560
12.3 Pattern Matching Algorithms 564
12.3.1 Brute Force 564
12.3.2 The Boyer-Moore Algorithm 566
12.3.3 The Knuth-Morris-Pratt Algorithm 570
12.4 Text Compression and the Greedy Method 575
12.4.1 The Huffman-Coding Algorithm 576
12.4.2 The Greedy Method 577
12.5 Tries 578
12.5.1 Standard Tries 578
12.5.2 Compressed Tries 582
12.5.3 Suffix Tries 584
12.5.4 Search Engines 586
12.6 Exercises 587
13 Graph Algorithms 593
13.1 Graphs 594
13.1.1 The Graph ADT 599
13.2 Data Structures for Graphs 600
13.2.1 The Edge List Structure 600
13.2.2 The Adjacency List Structure 603
13.2.3 The Adjacency Matrix Structure 605
13.3 Graph Traversals 607
13.3.1 Depth-First Search 607
13.3.2 Implementing Depth-First Search 611
13.3.3 A Generic DFS Implementation in C++ 613
13.3.4 Polymorphic Objects and Decorator Values ?621
13.3.5 Breadth-First Search 623
13.4 Directed Graphs 626
13.4.1 Traversing a Digraph 628
13.4.2 Transitive Closure 630
13.4.3 Directed Acyclic Graphs 633
13.5 Shortest Paths 637
13.5.1 Weighted Graphs 637
13.5.2 Dijkstra's Algorithm 639
13.6 Minimum Spanning Trees 645
13.6.1 Kruskal's Algorithm 647
13.6.2 The Prim-Jarn?ik Algorithm 651
13.7 Exercises 654
14 Memory Management and B-Trees 665
14.1 Memory Management 666
14.1.1 Memory Allocation in C++ 669
14.1.2 Garbage Collection 671
14.2 External Memory and Caching 673
14.2.1 The Memory Hierarchy 673
14.2.2 Caching Strategies 674
14.3 External Searching and B-Trees679
14.3.1 (a,b) Trees 680
14.3.2 B-Trees 682
14.4 External-Memory Sorting 683
14.4.1 Multi-Way Merging 684
14.5 Exercises 685
A Useful Mathematical Facts 689
Bibliography 697
Index 702