CONTENTS

PREFACE xi

CHAPTER 1 BASIC CONCEPTS 1

1.1 Overview; System Life Cycle 1
1.2 Algorithm Specification 4
1.2.1 Introduction 4
1.2.2 Recursive Algorithms 10
1.3 Data Abstraction 14
1.4 Performance Analysis 18
1.4.1 Space Complexity 19
1.4.2 Time Complexity 21
1.4.3 Asymptotic Notation 30
1.4.4 Practical Complexities 37
1.5 Performance Measurement 38
1.6 References And Selected Readings 47

CHAPTER 2 ARRAYS AND STRUCTURES 49

2.1 The Array As An Abstract Data Type 49
2.2 Structures and Unions 53
2.2.1 Structures 53
2.2.2 Unions 56
2.2.3 Internal Implementation Of Structures 57

V
vi Contents

2.2.4 Self-Referential Structures 57

2.3 The Polynomial Abstract Data Type 59
2.4 The Sparse Matrix Abstract Data Type 66
2.4.1 Introduction 66
2.4.2 Transposing A Matrix 69
2.4.3 Matrix Multiplication 73
2.5 The Representation Of Multidimensional Arrays 78
2.6 The String Abstract Data Type 80
2.6.1 Introduction 80
2.6.2 Pattern Matching 84
2.7 References And Selected Readings 92
2.8 Additional Exercises 92

CHAPTER 3 STACKS AND QUEUES 101

3.1 The Stack Abstract Data Type 101
3.2 The Queue Abstract Data Type 105
3.3 A Mazing Problem 112
3.4 Evaluation of Expressions 116
3.4.1 Introduction 116
3.4.2 Evaluatng Postfix Expressions 118
3.4.3 Infix to Postfix 121
3.5 Multiple Stacks And Queues 128
3.6 Selected Readings And References 131
3.7 Additional Exercises 132

CHAPTER 4 LISTS 135

4.1 Pointers 135
4.1.1 Pointer Can Be Dangerous 137
4.1.2 Using Dynamically Allocated Storage 138
4.2 Singly Linked Lists 139
4.3 Dynamically Linked Stacks And Queues 147
4.4 Polynomials 150
4.4.1 Representing Polynomials As Singly Linked Lists 150
4.4.2 Adding Polynomials 152
4.4.3 Erasing Polynomials 156
4.4.4 Polynomials As Circularly Linked Lists 157
4.4.5 Summary 161
4.5 Additional List Operations 163
4.5.1 Operations For Chains 163
4.5.2 Operations For Circularly Linked Lists 163
4.6 Equivalence Relations 166
4.7 Sparse Matrices 171
4.8 Doubly Linked Lists 179
 Contents vii

4.9 References And Selected Readings 182

4.10 Additional Exercises 183

CHAPTERS TREES 186

5.1 Introduction 186
5.1.1 Terminology 186
5.1.2 Representation Of Trees 189
5.2 Binary Trees 191
5.2.1 The Abstract Data Type 191
5.2.2 Properties Of Binary Trees 193
5.2.3 Binary Tree Representations 196
5.3 Binary Tree Traversals 200
5.4 Additional Binary Tree Operations 206
5.5 Threaded Binary Trees 211
5.6 Heaps 217
5.6.1 The Heap Abstract Data Type 218
5.6.2 Priority Queues 219
5.6.3 Insertion Into A Max Heap 221
5.6.4 Deletion From A Max Heap 223
5.7 Binary Search Trees 226
5.7.1 Introduction 226
5.7.2 Searching A Binary Search Tree 227
5.7.3 Inserting Into A Binary Search Tree 228
5.7.4 Deletion From A Binary Search Tree 230
5.7.5 Height Of A Binary Search Tree 231
5.8 Selection Trees 232
5.9 Forests 236
5.9.1 Transforming A Forest Into A Binary Search Tree 236
5.9.2 Forest Traversals 237
5.10 Set Representation 238
5.10.1 Union And Find Operations 239
5.10.2 Equivalence Relations 247
5.11 Counting Binary Trees 247
5.11.1 Distinct Binary Trees 247
5.11.2 Stack Permutations 249
5.11.3 Matrix Multiplication 251
5.11.4 Number Of Distinct Binary Trees 253
5.12 References And Selected Readings 254
5.13 Additional Exercises 254

CHAPTER 6 GRAPHS 257

6.1 The Graph Abstract Data Type 257
6.1.1 Introduction 257
viii Contents

6.1.2 Definitions 259

6.1.3 Graph Representations 263
6.2 Elementary Graph Operations 272
6.2.1 Depth First Search 272
6.2.2 Breadth First Search 273
6.2.3 Connected Components 276
6.2.4 Spanning Trees 276
6.2.4 Biconnected Components And Articulation Points 278
6.3 Minimum Cost Spanning Trees 284
6.4 Shortest Paths And Transitive Closure 292
6.4.1 Single Source All Destination 292
6.4.2 All Pairs Shortest Paths 295
6.4.3 Transitive Closure 300
6.5 Activity Networks 303
6.5.1 Activity On Vertex (AOV) Networks 303
6.5.2 Activity On Edge (AOE) Networks 309
6.6 References And Selected Readings 316
6.7 Additional Exercises 318

CHAPTER? SORTING 319

7.1 Searching And List Verification 319
7.1.1 Introduction 319
7.1.2 Sequential Search 320
7.1.3 Binary Search 321
7.1.4 List Verification 322
7.2 Definitions 326
7.3 Insertion Sort 326
7.4 Quick Sort 329
7.5 Optimal Sorting Time 333
7.6 Merge Sort 335
7.6.1 Merging 335
7.6.2 Iterative Merge Sort 340
7.6.3 Recursive Merge Sort 340
7.7 Heap Sort 347
7.8 Radix Sort 350
7.9 List And Table Sorts 357
7.10 Summary Of Internal Sorting 366
7.11 External Sorting 372
7.11.1 Introduction 372
7.11.2 A;-way Merging 376
7.11.3 Buffer Handling For Parallel Operation 378
7.11.4 Run Generation 385
7.11.5 Optimal Merging Of Runs 389
 Contents ix

7.12 References And Selected Readings 393

7.13 Additional Exercises 393

CHAPTERS HASHING 395

8.1 The Symbol Table Abstract Data Type 395
8.2 Static Hashing 397
8.2.1 Hash Tables 397
8.2.2 Hashing Functions 398
8.2.3 Overflow Handling 401
8.2.4 Theoretical Evaluation Of Overflow Techniques 409
8.3 Dynamic Hashing 413
8.3.1 Dynamic Hashing Using Directories 414
8.3.2 Analysis Of Directory Dynamic Hashing 421
8.3.3 Directory less Dynamic Hashing 424
8.4 References And Selected Readings 428

CHAPTER 9 HEAP STRUCTURES 430

9.1 Min-Max Heaps 430
9.1.1 Definition 430
9.1.2 Insertion Into A Min-Max Heap 431
9.1.3 Deletion Of Min Element 434
9.2 Deaps 439
9.2.1 Definition 439
9.2.2 Insertion Into A Deap 440
9.2.3 Deletion Of Min Element 442
9.3 Leftist Trees 446
9.4 Binomial Heaps 453
9.4.1 Cost Amortization 453
9.4.2 Definition Of Binomial Heaps 454
9.4.3 Insertion Into A Binomial Heap 455
9.4.4 Combine 455
9.4.5 Deletion Of Min Element 456
9.4.6 Analysis 458
9.5 Fibonacci Heaps 461
9.5.1 Definition 461
9.5.2 Deletion From An F-heap 462
9.5.3 Decrease Key 463
9.5.4 Cascading Cut 463
9.5.5 Analysis 464
9.5.6 Application Of F-heaps 466
9.6 References And Selected Readings 469
X Contents

CHAPTER 10 SEARCH STRUCTURES 470

10.1 Optimal Binary Search Trees 470
10.2 AVL Trees 470
10.3 2-3 Trees 496
10.3.1 Definition And Properties 496
10.3.2 Searching A 2-3 Tree 498
10.3.3 Insertion Into A 2-3 Tree 499
10.3.4 Deletion From A 2-3 Tree 502
10.4 2-3-4 Trees 509
10.4.1 Definition And Properties 509
10.4.2 Insertion Into A 2-3-4 Tree 511
10.4.3 Deletion From A 2-3-4 Tree 515
10.5 Red-Black Trees 518
10.5.1 Definition And Properties 518
10.5.2 Searching A Red-Black Tree 521
10,5.3 Top Down Insertion 521
10.5.4 Bottom Up Insertion 524
10.5.5 Deletion From A Red-Black Tree 525
10.6 B-Trees 528
10.6.1 Definition Of m-way Search Trees 528
10.6.2 Searching An m-way Search Tree 530
10.6.3 Definition And Properties Of A B-tree 530
10.6.4 Insertion Into A B-tree 533
10.6.5 Deletion From A B-tree 535
10.6.6 Variable Size Key Values 538
10.7 Splay Trees 542
10.8 Digital Search Trees 548
10.8.1 Digital Search Tree 548
10.8.2 Binary Tries 549
10.8.3 Patricia 550
10.9 Tries 557
10.9.1 Definition 557
10.9.2 Searching A Trie 558
10.9.3 Sampling Strategies 558
10.9.4 Insertion Into A Trie 561
10.9.5 Deletion From A Trie 561
10.10 Differential Files 563
10.11 References And Selected Readings 567

APPENDIX ANSI C AND K & R C 570

INDEX 579