Data structures and Program Design in C++

Navigating the Disk......Page 1 Hints for Page Navigation......Page 2 Synopsis......Page 12 Course Structure......Page 14 Supplementary Materials......Page 15 Acknowledgments......Page 16 1.1 Introduction......Page 18 1.2.1 Rules for the Game of Life......Page 21 1.2.2 Examples......Page 22 1.2.3 The Solution: Classes, Objects, and Methods......Page 24 1.2.4 Life: The Main Program......Page 25 1.3.1 Names......Page 27 1.3.2 Documentation and Format......Page 30 1.3.3 Refinement and Modularity......Page 32 1.4.1 Stubs......Page 37 1.4.2 Definition of the Class Life......Page 39 1.4.3 Counting Neighbors......Page 40 1.4.4 Updating the Grid......Page 41 1.4.5 Input and Output......Page 42 1.4.6 Drivers......Page 44 1.4.7 Program Tracing......Page 45 1.4.8 Principles of Program Testing......Page 46 1.5.1 Program Evaluation......Page 51 1.5.2 Review of the Life Program......Page 52 1.5.3 Program Revision and Redevelopment......Page 55 1.6.1 Software Engineering......Page 56 1.6.2 Problem Analysis......Page 57 1.6.4 Coding......Page 58 Pointers and Pitfalls......Page 62 Review Questions......Page 63 The Game of Life......Page 64 Software Engineering......Page 65 2.1 Stack Specifications......Page 66 2.1.2 Stacks......Page 67 2.1.3 First Example: Reversing a List......Page 68 2.1.4 Information Hiding......Page 71 2.1.5 The Standard Template Library......Page 72 2.2.1 Specification of Methods for Stacks......Page 74 2.2.2 The Class Specification......Page 77 2.2.3 Pushing, Popping, and Other Methods......Page 78 2.2.4 Encapsulation......Page 80 2.3 Application: A Desk Calculator......Page 83 2.4 Application: Bracket Matching......Page 86 2.5.1 Introduction......Page 88 2.5.2 General Definitions......Page 90 2.5.3 Refinement of Data Specification......Page 91 Review Questions......Page 93 References for Further Study......Page 94 3.1 Definitions......Page 95 3.1.1 Queue Operations......Page 96 3.1.2 Extended Queue Operations......Page 98 3.2 Implementations of Queues......Page 101 3.3 Circular Implementation of Queues in C++......Page 106 3.4 Demonstration and Testing......Page 110 3.5.2 Simulation of an Airport......Page 113 3.5.4 The Runway Class Specification......Page 116 3.5.5 The Plane Class Specification......Page 117 3.5.6 Functions and Methods of the Simulation......Page 118 3.5.7 Sample Results......Page 124 Review Questions......Page 127 References for Further Study......Page 128 4.1 Pointers and Linked Structures......Page 129 4.1.1 Introduction and Survey......Page 130 4.1.2 Pointers and Dynamic Memory in C++......Page 133 4.1.3 The Basics of Linked Structures......Page 139 4.2 Linked Stacks......Page 144 4.3.1 The Destructor......Page 148 4.3.2 Overloading the Assignment Operator......Page 149 4.3.3 The Copy Constructor......Page 152 4.3.4 The Modified Linked-Stack Specification......Page 153 4.4.1 Basic Declarations......Page 154 4.4.2 Extended Linked Queues......Page 156 4.5.2 The Main Program......Page 158 4.5.3 The Polynomial Data Structure......Page 161 4.5.4 Reading and Writing Polynomials......Page 164 4.5.5 Addition of Polynomials......Page 165 4.5.6 Completing the Project......Page 167 4.6 Abstract Data Types and Their Implementations......Page 169 Pointers and Pitfalls......Page 171 Review Questions......Page 172 5.1 Introduction to Recursion......Page 174 5.1.1 Stack Frames for Subprograms......Page 175 5.1.2 Tree of Subprogram Calls......Page 176 5.1.3 Factorials: A Recursive Definition......Page 177 5.1.4 Divide and Conquer: The Towers of Hanoi......Page 180 5.2.1 Designing Recursive Algorithms......Page 187 5.2.2 How Recursion Works......Page 188 5.2.3 Tail Recursion......Page 191 5.2.4 When Not to Use Recursion......Page 193 5.2.5 Guidelines and Conclusions......Page 197 5.3.1 Solving the Eight-Queens Puzzle......Page 200 5.3.2 Example: Four Queens......Page 201 5.3.3 Backtracking......Page 202 5.3.4 Overall Outline......Page 203 5.3.5 Refinement: The First Data Structure and Its Methods......Page 205 5.3.6 Review and Refinement......Page 208 5.3.7 Analysis of Backtracking......Page 211 5.4.1 Game Trees......Page 215 5.4.2 The Minimax Method......Page 216 5.4.3 Algorithm Development......Page 218 5.4.4 Refinement......Page 220 5.4.5 Tic-Tac-Toe......Page 221 Pointers and Pitfalls......Page 226 Review Questions......Page 227 References for Further Study......Page 228 6.1 List Definition......Page 229 6.1.1 Method Specifications......Page 231 6.2 Implementation of Lists......Page 234 6.2.1 Class Templates......Page 235 6.2.2 Contiguous Implementation......Page 236 6.2.3 Simply Linked Implementation......Page 238 6.2.4 Variation: Keeping the Current Position......Page 242 6.2.5 Doubly Linked Lists......Page 244 6.2.6 Comparison of Implementations......Page 247 6.3.1 Strings in C++......Page 250 6.3.2 Implementation of Strings......Page 251 6.3.3 Further String Operations......Page 255 6.4.1 Specifications......Page 259 6.4.2 Implementation......Page 260 6.5 Linked Lists in Arrays......Page 268 6.6 Application: par penalty -500 Generating Permutations......Page 277 Pointers and Pitfalls......Page 282 Review Questions......Page 283 References for Further Study......Page 284 7.1 Searching: Introduction and Notation......Page 285 7.2 Sequential Search......Page 288 7.3.1 Ordered Lists......Page 295 7.3.2 Algorithm Development......Page 297 7.3.3 The Forgetful Version......Page 298 7.3.4 Recognizing Equality......Page 301 7.4 Comparison Trees......Page 303 7.4.1 Analysis for $n = 10$......Page 304 7.4.2 Generalization......Page 307 7.4.3 Comparison of Methods......Page 311 7.4.4 A General Relationship......Page 313 7.5 Lower Bounds......Page 314 7.6.1 Introduction......Page 319 7.6.2 Orders of Magnitude......Page 321 7.6.3 The Big-O and Related Notations......Page 327 7.6.4 Keeping the Dominant Term......Page 328 Pointers and Pitfalls......Page 331 Review Questions......Page 332 References for Further Study......Page 333 8.1 Introduction and Notation......Page 334 8.1.1 Sortable Lists......Page 336 8.2.1 Ordered Insertion......Page 337 8.2.2 Sorting by Insertion......Page 338 8.2.3 Linked Version......Page 340 8.2.4 Analysis......Page 342 8.3.1 The Algorithm......Page 346 8.3.2 Contiguous Implementation......Page 347 8.3.3 Analysis......Page 348 8.3.4 Comparisons......Page 349 8.4 Shell Sort......Page 350 8.5 Lower Bounds......Page 353 8.6.1 The Main Ideas......Page 356 8.6.2 An Example......Page 357 8.7 Mergesort for Linked Lists......Page 361 8.7.1 The Functions......Page 362 8.7.2 Analysis of Mergesort......Page 365 8.8.1 The Main Function......Page 369 8.8.2 Partitioning the List......Page 370 8.8.3 Analysis of Quicksort......Page 373 8.8.4 Average-Case Analysis of Quicksort......Page 375 8.8.5 Comparison with Mergesort......Page 377 8.9.1 Two-Way Trees as Lists......Page 380 8.9.2 Development of Heapsort......Page 382 8.9.3 Analysis of Heapsort......Page 385 8.9.4 Priority Queues......Page 386 8.10 Review: Comparison of Methods......Page 389 Pointers and Pitfalls......Page 392 Review Questions......Page 393 References for Further Study......Page 394 9.1 Introduction: Breaking the lowercase {lg n} Barrier......Page 396 9.2 Rectangular Tables......Page 398 9.3.1 Triangular Tables......Page 400 9.3.2 Jagged Tables......Page 402 9.3.3 Inverted Tables......Page 403 9.4 Tables: A New Abstract Data Type......Page 405 9.5 Application: Radix Sort......Page 408 9.5.1 The Idea......Page 409 9.5.2 Implementation......Page 410 9.5.3 Analysis......Page 413 9.6.1 Sparse Tables......Page 414 9.6.2 Choosing a Hash Function......Page 416 9.6.3 Collision Resolution with Open Addressing......Page 418 9.6.4 Collision Resolution by Chaining......Page 423 9.7 Analysis of Hashing......Page 428 9.8 Conclusions: Comparison of Methods......Page 434 9.9.1 Choice of Algorithm......Page 435 9.9.2 Specification of Data Structures......Page 436 9.9.4 The Life Functions......Page 438 Pointers and Pitfalls......Page 443 Review Questions......Page 444 References for Further Study......Page 445 10.1 Binary Trees......Page 446 10.1.1 Definitions......Page 447 10.1.2 Traversal of Binary Trees......Page 449 10.1.3 Linked Implementation of Binary Trees......Page 454 10.2 Binary Search Trees......Page 461 10.2.1 Ordered Lists and Implementations......Page 463 10.2.2 Tree Search......Page 464 10.2.3 Insertion into a Binary Search Tree......Page 468 10.2.4 Treesort......Page 470 10.2.5 Removal from a Binary Search Tree......Page 472 10.3 Building a Binary Search Tree......Page 480 10.3.1 Getting Started......Page 481 10.3.2 Declarations and the Main Function......Page 482 10.3.3 Inserting a Node......Page 483 10.3.4 Finishing the Task......Page 484 10.3.5 Evaluation......Page 486 10.3.6 Random Search Trees and Optimality......Page 487 10.4.1 Definition......Page 490 10.4.2 Insertion of a Node......Page 494 10.4.3 Removal of a Node......Page 501 10.4.4 The Height of an AVL Tree......Page 502 10.5.1 Introduction......Page 507 10.5.2 Splaying Steps......Page 508 10.5.3 Algorithm Development......Page 512 10.5.4 Amortized Algorithm Analysis: Introduction......Page 522 10.5.5 Amortized Analysis of Splaying......Page 526 Pointers and Pitfalls......Page 532 Review Questions......Page 533 References for Further Study......Page 535 11.1 Orchards, Trees, and Binary Trees......Page 537 11.1.1 On the Classification of Species......Page 538 11.1.2 Ordered Trees......Page 539 11.1.3 Forests and Orchards......Page 541 11.1.4 The Formal Correspondence......Page 543 11.1.6 Summary......Page 544 11.2.2 Searching for a Key......Page 547 11.2.3 C++ Algorithm......Page 548 11.2.4 Searching a Trie......Page 549 11.2.6 Deletion from a Trie......Page 550 11.2.7 Assessment of Tries......Page 551 11.3.2 Multiway Search Trees......Page 552 11.3.3 Balanced Multiway Trees......Page 553 11.3.4 Insertion into a B-Tree......Page 554 11.3.5 C++ Algorithms: Searching and Insertion......Page 556 11.3.6 Deletion from a B-Tree......Page 564 11.4.1 Introduction......Page 573 11.4.2 Definition and Analysis......Page 574 11.4.3 Red-Black Tree Specification......Page 576 11.4.4 Insertion......Page 577 11.4.5 Insertion Method Implementation......Page 578 11.4.6 Removal of a Node......Page 582 Pointers and Pitfalls......Page 583 Review Questions......Page 584 References for Further Study......Page 585 12.1 Mathematical Background......Page 586 12.1.1 Definitions and Examples......Page 587 12.1.3 Directed Graphs......Page 588 12.2.1 The Set Representation......Page 589 12.2.2 Adjacency Lists......Page 591 12.3.1 Methods......Page 592 12.3.2 Depth-First Algorithm......Page 594 12.3.3 Breadth-First Algorithm......Page 595 12.4.1 The Problem......Page 596 12.4.2 Depth-First Algorithm......Page 597 12.4.3 Breadth-First Algorithm......Page 598 12.5.1 The Problem......Page 600 12.5.2 Method......Page 601 12.5.3 Example......Page 602 12.5.4 Implementation......Page 603 12.6.1 The Problem......Page 604 12.6.2 Method......Page 606 12.6.3 Implementation......Page 607 12.6.4 Verification of Prim's Algorithm......Page 610 12.7 Graphs as Data Structures......Page 611 Pointers and Pitfalls......Page 613 References for Further Study......Page 614 13.1 The Problem......Page 615 13.1.1 The Quadratic Formula......Page 616 13.2.1 Expression Trees......Page 618 13.2.2 Polish Notation......Page 620 13.3 Evaluation of Polish Expressions......Page 621 13.3.1 Evaluation of an Expression in Prefix Form......Page 622 13.3.2 C++ Conventions......Page 623 13.3.3 C++ Function for Prefix Evaluation......Page 624 13.3.4 Evaluation of Postfix Expressions......Page 625 13.3.5 Proof of the Program: Counting Stack Entries......Page 626 13.3.6 Recursive Evaluation of Postfix Expressions......Page 629 13.4 Translation from Infix Form to Polish Form......Page 634 13.5.1 Overall Structure......Page 640 13.5.2 Representation of the Data: Class Specifications......Page 642 13.5.3 Tokens......Page 646 13.5.4 The Lexicon......Page 648 13.5.5 Expressions: Token Lists......Page 651 13.5.6 Auxiliary Evaluation Functions......Page 656 13.5.7 Graphing the Expression: The Class Plot......Page 657 13.5.8 A Graphics-Enhanced Plot Class......Page 660 References for Further Study......Page 662 A.1 Sums of Powers of Integers......Page 664 A.2 Logarithms......Page 667 A.2.2 Simple Properties......Page 668 A.2.4 Natural Logarithms......Page 669 A.2.5 Notation......Page 670 A.2.7 Logarithmic Graphs......Page 671 A.2.8 Harmonic Numbers......Page 673 A.3.2 Combinations......Page 674 A.3.3 Factorials......Page 675 A.4 Fibonacci Numbers......Page 676 A.5.1 The Main Result......Page 678 A.5.2 The Proof by One-to-One Correspondences......Page 679 A.5.3 History......Page 681 References for Further Study......Page 682 B.1 Introduction......Page 684 B.2 Strategy......Page 685 B.3 Program Development......Page 686 References for Further Study......Page 690 C.1 Packages and C++ Translation Units......Page 691 C.2 Packages in the Text......Page 693 C.3 The Utility Package......Page 695 C.4 Timing Methods......Page 696 D.1.2 Lists......Page 698 D.1.5 Tables......Page 699 D.1.6 Binary Trees......Page 700 D.1.8 Graphs......Page 701 D.2 Recursion......Page 702 D.3 Design of Data Structures......Page 703 D.4 Algorithm Design and Analysis......Page 704 D.5 Programming......Page 705 D.6 Programming with Pointer Objects......Page 706 D.8 Maintenance......Page 707 A......Page 710 B......Page 712 C......Page 713 D......Page 715 E......Page 716 G......Page 718 H......Page 719 I......Page 720 L......Page 721 N......Page 723 P......Page 724 Q......Page 726 R......Page 727 S......Page 728 T......Page 731 W......Page 733 Z......Page 734 Navigating the Disk 1 Hints for Page Navigation 2 Synopsis 12 Course Structure 14 Supplementary Materials 15 Book Production 16 Acknowledgments 16 1 Programming Principles 18 1.1 Introduction 18 1.2 The Game of Life 21 1.2.1 Rules for the Game of Life 21 1.2.2 Examples 22 1.2.3 The Solution: Classes, Objects, and Methods 24 1.2.4 Life: The Main Program 25 1.3 Programming Style 27 1.3.1 Names 27 1.3.2 Documentation and Format 30 1.3.3 Refinement and Modularity 32 1.4 Coding, Testing, and Further Refinement 37 1.4.1 Stubs 37 1.4.2 Definition of the Class Life 39 1.4.3 Counting Neighbors 40 1.4.4 Updating the Grid 41 1.4.5 Input and Output 42 1.4.6 Drivers 44 1.4.7 Program Tracing 45 1.4.8 Principles of Program Testing 46 1.5 Program Maintenance 51 1.5.1 Program Evaluation 51 1.5.2 Review of the Life Program 52 1.5.3 Program Revision and Redevelopment 55 1.6 Conclusions and Preview 56 1.6.1 Software Engineering 56 1.6.2 Problem Analysis 57 1.6.3 Requirements Specification 58 1.6.4 Coding 58 Pointers and Pitfalls 62 Review Questions 63 References for Further Study 64 C++ 64 Programming Principles 64 The Game of Life 64 Software Engineering 65 2 Introduction to Stacks 66 2.1 Stack Specifications 66 2.1.1 Lists and Arrays 67 2.1.2 Stacks 67 2.1.3 First Example: Reversing a List 68 2.1.4 Information Hiding 71 2.1.5 The Standard Template Library 72 2.2 Implementation of Stacks 74 2.2.1 Specification of Methods for Stacks 74 2.2.2 The Class Specification 77 2.2.3 Pushing, Popping, and Other Methods 78 2.2.4 Encapsulation 80 2.3 Application: A Desk Calculator 83 2.4 Application: Bracket Matching 86 2.5 Abstract Data Types and Their Implementations 88 2.5.1 Introduction 88 2.5.2 General Definitions 90 2.5.3 Refinement of Data Specification 91 Pointers and Pitfalls 93 Review Questions 93 References for Further Study 94 3 Queues 95 3.1 Definitions 95 3.1.1 Queue Operations 96 3.1.2 Extended Queue Operations 98 3.2 Implementations of Queues 101 3.3 Circular Implementation of Queues in C++ 106 3.4 Demonstration and Testing 110 3.5 Application of Queues: Simulation 113 3.5.1 Introduction 113 3.5.2 Simulation of an Airport 113 3.5.3 Random Numbers 116 3.5.4 The Runway Class Specification 116 3.5.5 The Plane Class Specification 117 3.5.6 Functions and Methods of the Simulation 118 3.5.7 Sample Results 124 Pointers and Pitfalls 127 Review Questions 127 References for Further Study 128 4 Linked Stacks and Queues 129 4.1 Pointers and Linked Structures 129 4.1.1 Introduction and Survey 130 4.1.2 Pointers and Dynamic Memory in C++ 133 4.1.3 The Basics of Linked Structures 139 4.2 Linked Stacks 144 4.3 Linked Stacks with Safeguards 148 4.3.1 The Destructor 148 4.3.2 Overloading the Assignment Operator 149 4.3.3 The Copy Constructor 152 4.3.4 The Modified Linked-Stack Specification 153 4.4 Linked Queues 154 4.4.1 Basic Declarations 154 4.4.2 Extended Linked Queues 156 4.5 Application: Polynomial Arithmetic 158 4.5.1 Purpose of the Project 158 4.5.2 The Main Program 158 4.5.3 The Polynomial Data Structure 161 4.5.4 Reading and Writing Polynomials 164 4.5.5 Addition of Polynomials 165 4.5.6 Completing the Project 167 4.6 Abstract Data Types and Their Implementations 169 Pointers and Pitfalls 171 Review Questions 172 5 Recursion 174 5.1 Introduction to Recursion 174 5.1.1 Stack Frames for Subprograms 175 5.1.2 Tree of Subprogram Calls 176 5.1.3 Factorials: A Recursive Definition 177 5.1.4 Divide and Conquer: The Towers of Hanoi 180 5.2 Principles of Recursion 187 5.2.1 Designing Recursive Algorithms 187 5.2.2 How Recursion Works 188 5.2.3 Tail Recursion 191 5.2.4 When Not to Use Recursion 193 5.2.5 Guidelines and Conclusions 197 5.3 Backtracking: Postponing the Work 200 5.3.1 Solving the Eight-Queens Puzzle 200 5.3.2 Example: Four Queens 201 5.3.3 Backtracking 202 5.3.4 Overall Outline 203 5.3.5 Refinement: The First Data Structure and Its Methods 205 5.3.6 Review and Refinement 208 5.3.7 Analysis of Backtracking 211 5.4 Tree-Structured Programs: Look-Ahead in Games 215 5.4.1 Game Trees 215 5.4.2 The Minimax Method 216 5.4.3 Algorithm Development 218 5.4.4 Refinement 220 5.4.5 Tic-Tac-Toe 221 Pointers and Pitfalls 226 Review Questions 227 References for Further Study 228 6 Lists and Strings 229 6.1 List Definition 229 6.1.1 Method Specifications 231 6.2 Implementation of Lists 234 6.2.1 Class Templates 235 6.2.2 Contiguous Implementation 236 6.2.3 Simply Linked Implementation 238 6.2.4 Variation: Keeping the Current Position 242 6.2.5 Doubly Linked Lists 244 6.2.6 Comparison of Implementations 247 6.3 Strings 250 6.3.1 Strings in C++ 250 6.3.2 Implementation of Strings 251 6.3.3 Further String Operations 255 6.4 Application: A Text Editor 259 6.4.1 Specifications 259 6.4.2 Implementation 260 6.5 Linked Lists in Arrays 268 6.6 Application: par penalty -500 Generating Permutations 277 Pointers and Pitfalls 282 Review Questions 283 References for Further Study 284 7 Searching 285 7.1 Searching: Introduction and Notation 285 7.2 Sequential Search 288 7.3 Binary Search 295 7.3.1 Ordered Lists 295 7.3.2 Algorithm Development 297 7.3.3 The Forgetful Version 298 7.3.4 Recognizing Equality 301 7.4 Comparison Trees 303 7.4.1 Analysis for $n = 10$ 304 7.4.2 Generalization 307 7.4.3 Comparison of Methods 311 7.4.4 A General Relationship 313 7.5 Lower Bounds 314 7.6 Asymptotics 319 7.6.1 Introduction 319 7.6.2 Orders of Magnitude 321 7.6.3 The Big-O and Related Notations 327 7.6.4 Keeping the Dominant Term 328 Pointers and Pitfalls 331 Review Questions 332 References for Further Study 333 8 Sorting 334 8.1 Introduction and Notation 334 8.1.1 Sortable Lists 336 8.2 Insertion Sort 337 8.2.1 Ordered Insertion 337 8.2.2 Sorting by Insertion 338 8.2.3 Linked Version 340 8.2.4 Analysis 342 8.3 Selection Sort 346 8.3.1 The Algorithm 346 8.3.2 Contiguous Implementation 347 8.3.3 Analysis 348 8.3.4 Comparisons 349 8.4 Shell Sort 350 8.5 Lower Bounds 353 8.6 Divide-and-Conquer Sorting 356 8.6.1 The Main Ideas 356 8.6.2 An Example 357 8.7 Mergesort for Linked Lists 361 8.7.1 The Functions 362 8.7.2 Analysis of Mergesort 365 8.8 Quicksort for Contiguous Lists 369 8.8.1 The Main Function 369 8.8.2 Partitioning the List 370 8.8.3 Analysis of Quicksort 373 8.8.4 Average-Case Analysis of Quicksort 375 8.8.5 Comparison with Mergesort 377 8.9 Heaps and Heapsort 380 8.9.1 Two-Way Trees as Lists 380 8.9.2 Development of Heapsort 382 8.9.3 Analysis of Heapsort 385 8.9.4 Priority Queues 386 8.10 Review: Comparison of Methods 389 Pointers and Pitfalls 392 Review Questions 393 References for Further Study 394 9 Tables and Information Retrieval 396 9.1 Introduction: Breaking the lowercase {lg n} Barrier 396 9.2 Rectangular Tables 398 9.3 Tables of Various Shapes 400 9.3.1 Triangular Tables 400 9.3.2 Jagged Tables 402 9.3.3 Inverted Tables 403 9.4 Tables: A New Abstract Data Type 405 9.5 Application: Radix Sort 408 9.5.1 The Idea 409 9.5.2 Implementation 410 9.5.3 Analysis 413 9.6 Hashing 414 9.6.1 Sparse Tables 414 9.6.2 Choosing a Hash Function 416 9.6.3 Collision Resolution with Open Addressing 418 9.6.4 Collision Resolution by Chaining 423 9.7 Analysis of Hashing 428 9.8 Conclusions: Comparison of Methods 434 9.9 Application: The Life Game Revisited 435 9.9.1 Choice of Algorithm 435 9.9.2 Specification of Data Structures 436 9.9.3 The Life Class 438 9.9.4 The Life Functions 438 Pointers and Pitfalls 443 Review Questions 444 References for Further Study 445 10 Binary Trees 446 10.1 Binary Trees 446 10.1.1 Definitions 447 10.1.2 Traversal of Binary Trees 449 10.1.3 Linked Implementation of Binary Trees 454 10.2 Binary Search Trees 461 10.2.1 Ordered Lists and Implementations 463 10.2.2 Tree Search 464 10.2.3 Insertion into a Binary Search Tree 468 10.2.4 Treesort 470 10.2.5 Removal from a Binary Search Tree 472 10.3 Building a Binary Search Tree 480 10.3.1 Getting Started 481 10.3.2 Declarations and the Main Function 482 10.3.3 Inserting a Node 483 10.3.4 Finishing the Task 484 10.3.5 Evaluation 486 10.3.6 Random Search Trees and Optimality 487 10.4 Height Balance: AVL Trees 490 10.4.1 Definition 490 10.4.2 Insertion of a Node 494 10.4.3 Removal of a Node 501 10.4.4 The Height of an AVL Tree 502 10.5 Splay Trees: A Self-Adjusting Data Structure 507 10.5.1 Introduction 507 10.5.2 Splaying Steps 508 10.5.3 Algorithm Development 512 10.5.4 Amortized Algorithm Analysis: Introduction 522 10.5.5 Amortized Analysis of Splaying 526 Pointers and Pitfalls 532 Review Questions 533 References for Further Study 535 11 Multiway Trees 537 11.1 Orchards, Trees, and Binary Trees 537 11.1.1 On the Classification of Species 538 11.1.2 Ordered Trees 539 11.1.3 Forests and Orchards 541 11.1.4 The Formal Correspondence 543 11.1.5 Rotations 544 11.1.6 Summary 544 11.2 Lexicographic Search Trees: Tries 547 11.2.1 Tries 547 11.2.2 Searching for a Key 547 11.2.3 C++ Algorithm 548 11.2.4 Searching a Trie 549 11.2.5 Insertion into a Trie 550 11.2.6 Deletion from a Trie 550 11.2.7 Assessment of Tries 551 11.3 External Searching: B-Trees 552 11.3.1 Access Time 552 11.3.2 Multiway Search Trees 552 11.3.3 Balanced Multiway Trees 553 11.3.4 Insertion into a B-Tree 554 11.3.5 C++ Algorithms: Searching and Insertion 556 11.3.6 Deletion from a B-Tree 564 11.4 Red-Black Trees 573 11.4.1 Introduction 573 11.4.2 Definition and Analysis 574 11.4.3 Red-Black Tree Specification 576 11.4.4 Insertion 577 11.4.5 Insertion Method Implementation 578 11.4.6 Removal of a Node 582 Pointers and Pitfalls 583 Review Questions 584 References for Further Study 585 12 Graphs 586 12.1 Mathematical Background 586 12.1.1 Definitions and Examples 587 12.1.2 Undirected Graphs 588 12.1.3 Directed Graphs 588 12.2 Computer Representation 589 12.2.1 The Set Representation 589 12.2.2 Adjacency Lists 591 12.2.3 Information Fields 592 12.3 Graph Traversal 592 12.3.1 Methods 592 12.3.2 Depth-First Algorithm 594 12.3.3 Breadth-First Algorithm 595 12.4 Topological Sorting 596 12.4.1 The Problem 596 12.4.2 Depth-First Algorithm 597 12.4.3 Breadth-First Algorithm 598 12.5 A Greedy Algorithm: Shortest Paths 600 12.5.1 The Problem 600 12.5.2 Method 601 12.5.3 Example 602 12.5.4 Implementation 603 12.6 Minimal Spanning Trees 604 12.6.1 The Problem 604 12.6.2 Method 606 12.6.3 Implementation 607 12.6.4 Verification of Prim's Algorithm 610 12.7 Graphs as Data Structures 611 Pointers and Pitfalls 613 Review Questions 614 References for Further Study 614 13 Case Study: The Polish Notation 615 13.1 The Problem 615 13.1.1 The Quadratic Formula 616 13.2 The Idea 618 13.2.1 Expression Trees 618 13.2.2 Polish Notation 620 13.3 Evaluation of Polish Expressions 621 13.3.1 Evaluation of an Expression in Prefix Form 622 13.3.2 C++ Conventions 623 13.3.3 C++ Function for Prefix Evaluation 624 13.3.4 Evaluation of Postfix Expressions 625 13.3.5 Proof of the Program: Counting Stack Entries 626 13.3.6 Recursive Evaluation of Postfix Expressions 629 13.4 Translation from Infix Form to Polish Form 634 13.5 An Interactive Expression Evaluator 640 13.5.1 Overall Structure 640 13.5.2 Representation of the Data: Class Specifications 642 13.5.3 Tokens 646 13.5.4 The Lexicon 648 13.5.5 Expressions: Token Lists 651 13.5.6 Auxiliary Evaluation Functions 656 13.5.7 Graphing the Expression: The Class Plot 657 13.5.8 A Graphics-Enhanced Plot Class 660 References for Further Study 662 A Mathematical Methods 664 A.1 Sums of Powers of Integers 664 A.2 Logarithms 667 A.2.1 Definition of Logarithms 668 A.2.2 Simple Properties 668 A.2.3 Choice of Base 669 A.2.4 Natural Logarithms 669 A.2.5 Notation 670 A.2.6 Change of Base 671 A.2.7 Logarithmic Graphs 671 A.2.8 Harmonic Numbers 673 A.3 Permutations, Combinations, Factorials 674 A.3.1 Permutations 674 A.3.2 Combinations 674 A.3.3 Factorials 675 A.4 Fibonacci Numbers 676 A.5 Catalan Numbers 678 A.5.1 The Main Result 678 A.5.2 The Proof by One-to-One Correspondences 679 A.5.3 History 681 A.5.4 Numerical Results 682 References for Further Study 682 B Random Numbers 684 B.1 Introduction 684 B.2 Strategy 685 B.3 Program Development 686 References for Further Study 690 C Packages and Utility Functions 691 C.1 Packages and C++ Translation Units 691 C.2 Packages in the Text 693 C.3 The Utility Package 695 C.4 Timing Methods 696 D Programming Precepts, Pointers, and Pitfalls 698 D.1 Choice of Data Structures and Algorithms 698 D.1.1 Stacks 698 D.1.2 Lists 698 D.1.3 Searching Methods 699 D.1.4 Sorting Methods 699 D.1.5 Tables 699 D.1.6 Binary Trees 700 D.1.7 General Trees 701 D.1.8 Graphs 701 D.2 Recursion 702 D.3 Design of Data Structures 703 D.4 Algorithm Design and Analysis 704 D.5 Programming 705 D.6 Programming with Pointer Objects 706 D.7 Debugging and Testing 707 D.8 Maintenance 707 Index 710 A 710 B 712 C 713 D 715 E 716 F 718 G 718 H 719 I 720 J 721 K 721 L 721 M 723 N 723 O 724 P 724 Q 726 R 727 S 728 T 731 U 733 V 733 W 733 Y 734 Z 734