Data Structures and Algorithms in C++

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.

• 1 A C++ Primer 11.1 Basic C++ Programming Elements 21.1.1 A Simple C++ Program 21.1.2 Fundamental Types 41.1.3 Pointers, Arrays, and Structures 71.1.4 Named Constants, Scope, and Namespaces 131.2 Expressions 161.2.1 Changing Types through Casting 201.3 Control Flow 231.4 Functions 261.4.1 Argument Passing 281.4.2 Overloading and Inlining 301.5 Classes 321.5.1 Class Structure 331.5.2 Constructors and Destructors 371.5.3 Classes and Memory Allocation 401.5.4 Class Friends and Class Members 431.5.5 The Standard Template Library 451.6 C++ Program and File Organization 471.6.1 An Example Program 481.7 Writing a C++ Program531.7.1 Design 541.7.2 Pseudo-Code 541.7.3 Coding 551.7.4 Testing and Debugging 571.8 Exercises 602 Object-Oriented Design 652.1 Goals, Principles, and Patterns 662.1.1 Object-Oriented Design Goals 662.1.2 Object-Oriented Design Principles 672.1.3 Design Patterns 702.2 Inheritance and Polymorphism 712.2.1 Inheritance in C++ 712.2.2 Polymorphism 782.2.3 Examples of Inheritance in C++ 792.2.4 Multiple Inheritance and Class Casting 842.2.5 Interfaces and Abstract Classes 872.3 Templates 902.3.1 Function Templates 902.3.2 Class Templates 912.4 Exceptions 932.4.1 Exception Objects 932.4.2 Throwing and Catching Exceptions 942.4.3 Exception Specification 962.5 Exercises 983 Arrays, Linked Lists, and Recursion 1033.1 Using Arrays 1043.1.1 Storing Game Entries in an Array 1043.1.2 Sorting an Array 1093.1.3 Two-Dimensional Arrays and Positional Games 1113.2 Singly Linked Lists 1173.2.1 Implementing a Singly Linked List 1173.2.2 Insertion to the Front of a Singly Linked List 1193.2.3 Removal from the Front of a Singly Linked List 1193.2.4 Implementing a Generic Singly Linked List 1213.3 Doubly Linked Lists 1233.3.1 Insertion into a Doubly Linked List 1233.3.2 Removal from a Doubly Linked List 1243.3.3 A C++ Implementation 1253.4 Circularly Linked Lists and List Reversal 1293.4.1 Circularly Linked Lists 1293.4.2 Reversing a Linked List 1333.5 Recursion 1343.5.1 Linear Recursion 1403.5.2 Binary Recursion 1443.5.3 Multiple Recursion 1473.6 Exercises 1494 Analysis Tools 1534.1 The Seven Functions Used in This Book 1544.1.1 The Constant Function 1544.1.2 The Logarithm Function 1544.1.3 The Linear Function 1564.1.4 The N-Log-N Function 1564.1.5 The Quadratic Function 1564.1.6 The Cubic Function and Other Polynomials 1584.1.7 The Exponential Function 1594.1.8 Comparing Growth Rates 1614.2 Analysis of Algorithms 1624.2.1 Experimental Studies 1634.2.2 Primitive Operations 1644.2.3 Asymptotic Notation 1664.2.4 Asymptotic Analysis 1704.2.5 Using the Big-Oh Notation 1724.2.6 A Recursive Algorithm for Computing Powers 1764.2.7 Some More Examples of Algorithm Analysis 1774.3 Simple Justification Techniques 1814.3.1 By Example 1814.3.2 The “Contra” Attack 1814.3.3 Induction and Loop Invariants 1824.4 Exercises 1855 Stacks, Queues, and Deques 1935.1 Stacks 1945.1.1 The Stack Abstract Data Type 1955.1.2 The STL Stack 1965.1.3 A C++ Stack Interface 1965.1.4 A Simple Array-Based Stack Implementation 1985.1.5 Implementing a Stack with a Generic Linked List 2025.1.6 Reversing a Vector Using a Stack 2035.1.7 Matching Parentheses and HTML Tags 2045.2 Queues 2085.2.1 The Queue Abstract Data Type 2085.2.2 The STL Queue 2095.2.3 A C++ Queue Interface 2105.2.4 A Simple Array-Based Implementation 2115.2.5 Implementing a Queue with a Circularly Linked List 2135.3 Double-Ended Queues 2175.3.1 The Deque Abstract Data Type 2175.3.2 The STL Deque 2185.3.3 Implementing a Deque with a Doubly Linked List 2185.3.4 Adapters and the Adapter Design Pattern 2205.4 Exercises 2236 List and Iterator ADTs 2276.1 Vectors 2286.1.1 The Vector Abstract Data Type 2286.1.2 A Simple Array-Based Implementation 2296.1.3 An Extendable Array Implementation 2316.1.4 STL Vectors 2366.2 Lists 2386.2.1 Node-Based Operations and Iterators 2386.2.2 The List Abstract Data Type 2406.2.3 Doubly Linked List Implementation 2426.2.4 STL Lists 2476.2.5 STL Containers and Iterators 2486.3 Sequences 2556.3.1 The Sequence Abstract Data Type 2556.3.2 Implementing a Sequence with a Doubly Linked List .2556.3.3 Implementing a Sequence with an Array 2576.4 Case Study: Bubble-Sort on a Sequence 2596.4.1 The Bubble-Sort Algorithm 2596.4.2 A Sequence-Based Analysis of Bubble-Sort 2606.5 Exercises 2627 Trees 2677.1 General Trees 2687.1.1 Tree Definitions and Properties 2697.1.2 Tree Functions 2727.1.3 A C++ Tree Interface 2737.1.4 A Linked Structure for General Trees 2747.2 Tree Traversal Algorithms 2757.2.1 Depth and Height 2757.2.2 Preorder Traversal 2787.2.3 Postorder Traversal 2817.3 Binary Trees 2847.3.1 The Binary Tree ADT 2857.3.2 A C++ Binary Tree Interface 2867.3.3 Properties of Binary Trees 2877.3.4 A Linked Structure for Binary Trees 2897.3.5 A Vector-Based Structure for Binary Trees 2957.3.6 Traversals of a Binary Tree 2977.3.7 The Template Function Pattern 3037.3.8 Representing General Trees with Binary Trees 3097.4 Exercises 3108 Heaps and Priority Queues 3218.1 The Priority Queue Abstract Data Type 3228.1.1 Keys, Priorities, and Total Order Relations 3228.1.2 Comparators 3248.1.3 The Priority Queue ADT 3278.1.4 A C++ Priority Queue Interface 3288.1.5 Sorting with a Priority Queue 3298.1.6 The STL priority queue Class 3308.2 Implementing a Priority Queue with a List 3318.2.1 A C++ Priority Queue Implementation using a List 3338.2.2 Selection-Sort and Insertion-Sort 3358.3 Heaps 3378.3.1 The Heap Data Structure 3378.3.2 Complete Binary Trees and Their Representation 3408.3.3 Implementing a Priority Queue with a Heap 3448.3.4 C++ Implementation 3498.3.5 Heap-Sort 3518.3.6 Bottom-Up Heap Construction ⋆ 3538.4 Adaptable Priority Queues 3578.4.1 A List-Based Implementation 3588.4.2 Location-Aware Entries 3608.5 Exercises 3619 Hash Tables, Maps, and Skip Lists 3679.1 Maps 3689.1.1 The Map ADT 3699.1.2 A C++ Map Interface 3719.1.3 The STL map Class 3729.1.4 A Simple List-Based Map Implementation 3749.2 Hash Tables 3759.2.1 Bucket Arrays 3759.2.2 Hash Functions 3769.2.3 Hash Codes 3769.2.4 Compression Functions 3809.2.5 Collision-Handling Schemes 3829.2.6 Load Factors and Rehashing 3869.2.7 A C++ Hash Table Implementation 3879.3 Ordered Maps 3949.3.1 Ordered Search Tables and Binary Search 3959.3.2 Two Applications of Ordered Maps 3999.4 Skip Lists 4029.4.1 Search and Update Operations in a Skip List 4049.4.2 A Probabilistic Analysis of Skip Lists ⋆ 4089.5 Dictionaries 4119.5.1 The Dictionary ADT 4119.5.2 A C++ Dictionary Implementation 4139.5.3 Implementations with Location-Aware Entries 4159.6 Exercises 41710 Search Trees 42310.1 Binary Search Trees 42410.1.1 Searching 42610.1.2 Update Operations 42810.1.3 C++ Implementation of a Binary Search Tree 43210.2 AVL Trees43810.2.1 Update Operations 44010.2.2 C++ Implementation of an AVL Tree 44610.3 Splay Trees 45010.3.1 Splaying 45010.3.2 When to Splay 45410.3.3 Amortized Analysis of Splaying ⋆45610.4 (2,4) Trees 46110.4.1 Multi-Way Search Trees 46110.4.2 Update Operations for (2,4) Trees 46710.5 Red-Black Trees47310.5.1 Update Operations 47510.5.2 C++ Implementation of a Red-Black Tree 48810.6 Exercises 49211 Sorting, Sets, and Selection 49911.1 Merge-Sort50011.1.1 Divide-and-Conquer 50011.1.2 Merging Arrays and Lists 50511.1.3 The Running Time of Merge-Sort 50811.1.4 C++ Implementations of Merge-Sort 50911.1.5 Merge-Sort and Recurrence Equations ⋆ 51111.2 Quick-Sort 51311.2.1 Randomized Quick-Sort 52111.2.2 C++ Implementations and Optimizations 52311.3 Studying Sorting through an Algorithmic Lens 52611.3.1 A Lower Bound for Sorting 52611.3.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort 52811.3.3 Comparing Sorting Algorithms 53111.4 Sets and Union/Find Structures 53311.4.1 The Set ADT 53311.4.2 Mergable Sets and the Template Method Pattern 53411.4.3 Partitions with Union-Find Operations 53811.5 Selection 54211.5.1 Prune-and-Search 54211.5.2 Randomized Quick-Select 54311.5.3 Analyzing Randomized Quick-Select 54411.6 Exercises 54512 Strings and Dynamic Programming 55312.1 String Operations 55412.1.1 The STL String Class 55512.2 Dynamic Programming 55712.2.1 Matrix Chain-Product 55712.2.2 DNA and Text Sequence Alignment 56012.3 Pattern Matching Algorithms 56412.3.1 Brute Force 56412.3.2 The Boyer-Moore Algorithm 56612.3.3 The Knuth-Morris-Pratt Algorithm 57012.4 Text Compression and the Greedy Method 57512.4.1 The Huffman-Coding Algorithm 57612.4.2 The Greedy Method 57712.5 Tries 57812.5.1 Standard Tries 57812.5.2 Compressed Tries 58212.5.3 Suffix Tries 58412.5.4 Search Engines 58612.6 Exercises 58713 Graph Algorithms 59313.1 Graphs 59413.1.1 The Graph ADT 59913.2 Data Structures for Graphs 60013.2.1 The Edge List Structure 60013.2.2 The Adjacency List Structure 60313.2.3 The Adjacency Matrix Structure 60513.3 Graph Traversals 60713.3.1 Depth-First Search 60713.3.2 Implementing Depth-First Search 61113.3.3 A Generic DFS Implementation in C++ 61313.3.4 Polymorphic Objects and Decorator Values ⋆ 62113.3.5 Breadth-First Search 62313.4 Directed Graphs 62613.4.1 Traversing a Digraph 62813.4.2 Transitive Closure 63013.4.3 Directed Acyclic Graphs 63313.5 Shortest Paths 63713.5.1 Weighted Graphs 63713.5.2 Dijkstra’s Algorithm 63913.6 Minimum Spanning Trees 64513.6.1 Kruskal’s Algorithm 64713.6.2 The Prim-Jarn´ık Algorithm 65113.7 Exercises 65414 Memory Management and B-Trees 66514.1 Memory Management 66614.1.1 Memory Allocation in C++ 66914.1.2 Garbage Collection 67114.2 External Memory and Caching 67314.2.1 The Memory Hierarchy 67314.2.2 Caching Strategies 67414.3 External Searching and B-Trees67914.3.1 (a,b) Trees 68014.3.2 B-Trees 68214.4 External-Memory Sorting 68314.4.1 Multi-Way Merging 68414.5 Exercises 685A Useful Mathematical Facts 689Bibliography 697Index 7021 A C++ Primer 11.1 Basic C++ Programming Elements 21.1.1 A Simple C++ Program 21.1.2 Fundamental Types 41.1.3 Pointers, Arrays, and Structures 71.1.4 Named Constants, Scope, and Namespaces 131.2 Expressions 161.2.1 Changing Types through Casting 201.3 Control Flow 231.4 Functions 261.4.1 Argument Passing 281.4.2 Overloading and Inlining 301.5 Classes 321.5.1 Class Structure 331.5.2 Constructors and Destructors 371.5.3 Classes and Memory Allocation 401.5.4 Class Friends and Class Members 431.5.5 The Standard Template Library 451.6 C++ Program and File Organization 471.6.1 An Example Program 481.7 Writing a C++ Program531.7.1 Design 541.7.2 Pseudo-Code 541.7.3 Coding 551.7.4 Testing and Debugging 571.8 Exercises 602 Object-Oriented Design 652.1 Goals, Principles, and Patterns 662.1.1 Object-Oriented Design Goals 662.1.2 Object-Oriented Design Principles 672.1.3 Design Patterns 702.2 Inheritance and Polymorphism 712.2.1 Inheritance in C++ 712.2.2 Polymorphism 782.2.3 Examples of Inheritance in C++ 792.2.4 Multiple Inheritance and Class Casting 842.2.5 Interfaces and Abstract Classes 872.3 Templates 902.3.1 Function Templates 902.3.2 Class Templates 912.4 Exceptions 932.4.1 Exception Objects 932.4.2 Throwing and Catching Exceptions 942.4.3 Exception Specification 962.5 Exercises 983 Arrays, Linked Lists, and Recursion 1033.1 Using Arrays 1043.1.1 Storing Game Entries in an Array 1043.1.2 Sorting an Array 1093.1.3 Two-Dimensional Arrays and Positional Games 1113.2 Singly Linked Lists 1173.2.1 Implementing a Singly Linked List 1173.2.2 Insertion to the Front of a Singly Linked List 1193.2.3 Removal from the Front of a Singly Linked List 1193.2.4 Implementing a Generic Singly Linked List 1213.3 Doubly Linked Lists 1233.3.1 Insertion into a Doubly Linked List 1233.3.2 Removal from a Doubly Linked List 1243.3.3 A C++ Implementation 1253.4 Circularly Linked Lists and List Reversal 1293.4.1 Circularly Linked Lists 1293.4.2 Reversing a Linked List 1333.5 Recursion 1343.5.1 Linear Recursion 1403.5.2 Binary Recursion 1443.5.3 Multiple Recursion 1473.6 Exercises 1494 Analysis Tools 1534.1 The Seven Functions Used in This Book 1544.1.1 The Constant Function 1544.1.2 The Logarithm Function 1544.1.3 The Linear Function 1564.1.4 The N-Log-N Function 1564.1.5 The Quadratic Function 1564.1.6 The Cubic Function and Other Polynomials 1584.1.7 The Exponential Function 1594.1.8 Comparing Growth Rates 1614.2 Analysis of Algorithms 1624.2.1 Experimental Studies 1634.2.2 Primitive Operations 1644.2.3 Asymptotic Notation 1664.2.4 Asymptotic Analysis 1704.2.5 Using the Big-Oh Notation 1724.2.6 A Recursive Algorithm for Computing Powers 1764.2.7 Some More Examples of Algorithm Analysis 1774.3 Simple Justification Techniques 1814.3.1 By Example 1814.3.2 The “Contra” Attack 1814.3.3 Induction and Loop Invariants 1824.4 Exercises 1855 Stacks, Queues, and Deques 1935.1 Stacks 1945.1.1 The Stack Abstract Data Type 1955.1.2 The STL Stack 1965.1.3 A C++ Stack Interface 1965.1.4 A Simple Array-Based Stack Implementation 1985.1.5 Implementing a Stack with a Generic Linked List 2025.1.6 Reversing a Vector Using a Stack 2035.1.7 Matching Parentheses and HTML Tags 2045.2 Queues 2085.2.1 The Queue Abstract Data Type 2085.2.2 The STL Queue 2095.2.3 A C++ Queue Interface 2105.2.4 A Simple Array-Based Implementation 2115.2.5 Implementing a Queue with a Circularly Linked List 2135.3 Double-Ended Queues 2175.3.1 The Deque Abstract Data Type 2175.3.2 The STL Deque 2185.3.3 Implementing a Deque with a Doubly Linked List 2185.3.4 Adapters and the Adapter Design Pattern 2205.4 Exercises 2236 List and Iterator ADTs 2276.1 Vectors 2286.1.1 The Vector Abstract Data Type 2286.1.2 A Simple Array-Based Implementation 2296.1.3 An Extendable Array Implementation 2316.1.4 STL Vectors 2366.2 Lists 2386.2.1 Node-Based Operations and Iterators 2386.2.2 The List Abstract Data Type 2406.2.3 Doubly Linked List Implementation 2426.2.4 STL Lists 2476.2.5 STL Containers and Iterators 2486.3 Sequences2556.3.1 The Sequence Abstract Data Type 2556.3.2 Implementing a Sequence with a Doubly Linked List .2556.3.3 Implementing a Sequence with an Array 2576.4 Case Study: Bubble-Sort on a Sequence 2596.4.1 The Bubble-Sort Algorithm 2596.4.2 A Sequence-Based Analysis of Bubble-Sort 2606.5 Exercises 2627 Trees 2677.1 General Trees 2687.1.1 Tree Definitions and Properties 2697.1.2 Tree Functions 2727.1.3 A C++ Tree Interface 2737.1.4 A Linked Structure for General Trees 2747.2 Tree Traversal Algorithms 2757.2.1 Depth and Height 2757.2.2 Preorder Traversal 2787.2.3 Postorder Traversal 2817.3 Binary Trees 2847.3.1 The Binary Tree ADT 2857.3.2 A C++ Binary Tree Interface 2867.3.3 Properties of Binary Trees 2877.3.4 A Linked Structure for Binary Trees 2897.3.5 A Vector-Based Structure for Binary Trees 2957.3.6 Traversals of a Binary Tree 2977.3.7 The Template Function Pattern 3037.3.8 Representing General Trees with Binary Trees 3097.4 Exercises 3108 Heaps and Priority Queues 3218.1 The Priority Queue Abstract Data Type 3228.1.1 Keys, Priorities, and Total Order Relations 3228.1.2 Comparators 3248.1.3 The Priority Queue ADT 3278.1.4 A C++ Priority Queue Interface 3288.1.5 Sorting with a Priority Queue 3298.1.6 The STL priority queue Class 3308.2 Implementing a Priority Queue with a List 3318.2.1 A C++ Priority Queue Implementation using a List 3338.2.2 Selection-Sort and Insertion-Sort 3358.3 Heaps 3378.3.1 The Heap Data Structure 3378.3.2 Complete Binary Trees and Their Representation 3408.3.3 Implementing a Priority Queue with a Heap 3448.3.4 C++ Implementation 3498.3.5 Heap-Sort 3518.3.6 Bottom-Up Heap Construction ⋆3538.4 Adaptable Priority Queues 3578.4.1 A List-Based Implementation 3588.4.2 Location-Aware Entries 3608.5 Exercises 3619 Hash Tables, Maps, and Skip Lists 3679.1 Maps 3689.1.1 The Map ADT 3699.1.2 A C++ Map Interface 3719.1.3 The STL map Class 3729.1.4 A Simple List-Based Map Implementation 3749.2 Hash Tables 3759.2.1 Bucket Arrays 3759.2.2 Hash Functions 3769.2.3 Hash Codes 3769.2.4 Compression Functions 3809.2.5 Collision-Handling Schemes 3829.2.6 Load Factors and Rehashing 3869.2.7 A C++ Hash Table Implementation 3879.3 Ordered Maps 3949.3.1 Ordered Search Tables and Binary Search 3959.3.2 Two Applications of Ordered Maps 3999.4 Skip Lists 4029.4.1 Search and Update Operations in a Skip List 4049.4.2 A Probabilistic Analysis of Skip Lists ⋆4089.5 Dictionaries 4119.5.1 The Dictionary ADT 4119.5.2 A C++ Dictionary Implementation 4139.5.3 Implementations with Location-Aware Entries 4159.6 Exercises 41710 Search Trees 42310.1 Binary Search Trees 42410.1.1 Searching 42610.1.2 Update Operations 42810.1.3 C++ Implementation of a Binary Search Tree 43210.2 AVL Trees43810.2.1 Update Operations 44010.2.2 C++ Implementation of an AVL Tree 44610.3 Splay Trees 45010.3.1 Splaying 45010.3.2 When to Splay 45410.3.3 Amortized Analysis of Splaying ⋆45610.4 (2,4) Trees 46110.4.1 Multi-Way Search Trees 46110.4.2 Update Operations for (2,4) Trees 46710.5 Red-Black Trees47310.5.1 Update Operations 47510.5.2 C++ Implementation of a Red-Black Tree 48810.6 Exercises 49211 Sorting, Sets, and Selection 49911.1 Merge-Sort50011.1.1 Divide-and-Conquer 50011.1.2 Merging Arrays and Lists 50511.1.3 The Running Time of Merge-Sort 50811.1.4 C++ Implementations of Merge-Sort 50911.1.5 Merge-Sort and Recurrence Equations ⋆51111.2 Quick-Sort 51311.2.1 Randomized Quick-Sort 52111.2.2 C++ Implementations and Optimizations 52311.3 Studying Sorting through an Algorithmic Lens 52611.3.1 A Lower Bound for Sorting 52611.3.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort 52811.3.3 Comparing Sorting Algorithms 53111.4 Sets and Union/Find Structures 53311.4.1 The Set ADT 53311.4.2 Mergable Sets and the Template Method Pattern 53411.4.3 Partitions with Union-Find Operations 53811.5 Selection 54211.5.1 Prune-and-Search 54211.5.2 Randomized Quick-Select 54311.5.3 Analyzing Randomized Quick-Select 54411.6 Exercises 54512 Strings and Dynamic Programming 55312.1 String Operations 55412.1.1 The STL String Class 55512.2 Dynamic Programming 55712.2.1 Matrix Chain-Product 55712.2.2 DNA and Text Sequence Alignment 56012.3 Pattern Matching Algorithms 56412.3.1 Brute Force 56412.3.2 The Boyer-Moore Algorithm 56612.3.3 The Knuth-Morris-Pratt Algorithm 57012.4 Text Compression and the Greedy Method 57512.4.1 The Huffman-Coding Algorithm 57612.4.2 The Greedy Method 57712.5 Tries 57812.5.1 Standard Tries 57812.5.2 Compressed Tries 58212.5.3 Suffix Tries 58412.5.4 Search Engines 58612.6 Exercises 58713 Graph Algorithms 59313.1 Graphs 59413.1.1 The Graph ADT 59913.2 Data Structures for Graphs 60013.2.1 The Edge List Structure 60013.2.2 The Adjacency List Structure 60313.2.3 The Adjacency Matrix Structure 60513.3 Graph Traversals 60713.3.1 Depth-First Search 60713.3.2 Implementing Depth-First Search 61113.3.3 A Generic DFS Implementation in C++ 61313.3.4 Polymorphic Objects and Decorator Values ⋆62113.3.5 Breadth-First Search 62313.4 Directed Graphs 62613.4.1 Traversing a Digraph 62813.4.2 Transitive Closure 63013.4.3 Directed Acyclic Graphs 63313.5 Shortest Paths 63713.5.1 Weighted Graphs 63713.5.2 Dijkstra’s Algorithm 63913.6 Minimum Spanning Trees 64513.6.1 Kruskal’s Algorithm 64713.6.2 The Prim-Jarn´ık Algorithm 65113.7 Exercises 65414 Memory Management and B-Trees 66514.1 Memory Management 66614.1.1 Memory Allocation in C++ 66914.1.2 Garbage Collection 67114.2 External Memory and Caching 67314.2.1 The Memory Hierarchy 67314.2.2 Caching Strategies 67414.3 External Searching and B-Trees67914.3.1 (a,b) Trees 68014.3.2 B-Trees 68214.4 External-Memory Sorting 68314.4.1 Multi-Way Merging 68414.5 Exercises 685A Useful Mathematical Facts 689Bibliography 697Index 702