Data Structures and Algorithm Analysis in Java, 3rd Edition (Dr. Clifford A. Shaffer) (Z-Library)

Data Structures and Algorithm Analysis Edition 3.2 (Java Version) Clifford A. Shaffer Department of Computer Science Virginia Tech Blacksburg, VA 24061 September 15, 2011 Update 3.2.0.2 For a list of changes, see http://people.cs.vt.edu/˜shaffer/Book/errata.html Copyright © 2009-2011 by Clifford A. Shaffer. This document is made freely available in PDF form for educational and other non-commercial use. You may make copies of this file and redistribute in electronic form without charge. You may extract portions of this document provided that the front page, including the title, author, and this notice are included. Any commercial use of this document requires the written consent of the author. The author can be reached at shaffer@cs.vt.edu. If you wish to have a printed version of this document, print copies are published by Dover Publications (see http://store.doverpublications.com/0486485811.html). Further information about this text is available at http://people.cs.vt.edu/˜shaffer/Book/.

Contents Preface xiii I Preliminaries 1 1 Data Structures and Algorithms 3 1.1 A Philosophy of Data Structures 4 1.1.1 The Need for Data Structures 4 1.1.2 Costs and Benefits 6 1.2 Abstract Data Types and Data Structures 8 1.3 Design Patterns 12 1.3.1 Flyweight 13 1.3.2 Visitor 13 1.3.3 Composite 14 1.3.4 Strategy 15 1.4 Problems, Algorithms, and Programs 16 1.5 Further Reading 18 1.6 Exercises 20 2 Mathematical Preliminaries 23 2.1 Sets and Relations 23 2.2 Miscellaneous Notation 27 2.3 Logarithms 29 2.4 Summations and Recurrences 30 2.5 Recursion 34 2.6 Mathematical Proof Techniques 36 iii

iv Contents 2.6.1 Direct Proof 37 2.6.2 Proof by Contradiction 37 2.6.3 Proof by Mathematical Induction 38 2.7 Estimation 44 2.8 Further Reading 45 2.9 Exercises 46 3 Algorithm Analysis 53 3.1 Introduction 53 3.2 Best, Worst, and Average Cases 59 3.3 A Faster Computer, or a Faster Algorithm? 60 3.4 Asymptotic Analysis 63 3.4.1 Upper Bounds 63 3.4.2 Lower Bounds 65 3.4.3 Θ Notation 66 3.4.4 Simplifying Rules 67 3.4.5 Classifying Functions 68 3.5 Calculating the Running Time for a Program 69 3.6 Analyzing Problems 74 3.7 Common Misunderstandings 75 3.8 Multiple Parameters 77 3.9 Space Bounds 78 3.10 Speeding Up Your Programs 80 3.11 Empirical Analysis 83 3.12 Further Reading 84 3.13 Exercises 85 3.14 Projects 89 II Fundamental Data Structures 91 4 Lists, Stacks, and Queues 93 4.1 Lists 94 4.1.1 Array-Based List Implementation 97 4.1.2 Linked Lists 100 4.1.3 Comparison of List Implementations 108

Contents v 4.1.4 Element Implementations 111 4.1.5 Doubly Linked Lists 112 4.2 Stacks 117 4.2.1 Array-Based Stacks 117 4.2.2 Linked Stacks 120 4.2.3 Comparison of Array-Based and Linked Stacks 121 4.2.4 Implementing Recursion 121 4.3 Queues 125 4.3.1 Array-Based Queues 125 4.3.2 Linked Queues 128 4.3.3 Comparison of Array-Based and Linked Queues 131 4.4 Dictionaries 131 4.5 Further Reading 138 4.6 Exercises 138 4.7 Projects 141 5 Binary Trees 145 5.1 Definitions and Properties 145 5.1.1 The Full Binary Tree Theorem 147 5.1.2 A Binary Tree Node ADT 149 5.2 Binary Tree Traversals 149 5.3 Binary Tree Node Implementations 154 5.3.1 Pointer-Based Node Implementations 154 5.3.2 Space Requirements 160 5.3.3 Array Implementation for Complete Binary Trees 161 5.4 Binary Search Trees 163 5.5 Heaps and Priority Queues 170 5.6 Huffman Coding Trees 178 5.6.1 Building Huffman Coding Trees 179 5.6.2 Assigning and Using Huffman Codes 185 5.6.3 Search in Huffman Trees 188 5.7 Further Reading 188 5.8 Exercises 189 5.9 Projects 192 6 Non-Binary Trees 195

vi Contents 6.1 General Tree Definitions and Terminology 195 6.1.1 An ADT for General Tree Nodes 196 6.1.2 General Tree Traversals 197 6.2 The Parent Pointer Implementation 199 6.3 General Tree Implementations 206 6.3.1 List of Children 206 6.3.2 The Left-Child/Right-Sibling Implementation 206 6.3.3 Dynamic Node Implementations 207 6.3.4 Dynamic “Left-Child/Right-Sibling” Implementation 210 6.4 K-ary Trees 210 6.5 Sequential Tree Implementations 212 6.6 Further Reading 215 6.7 Exercises 215 6.8 Projects 218 III Sorting and Searching 221 7 Internal Sorting 223 7.1 Sorting Terminology and Notation 224 7.2 Three Θ(n2) Sorting Algorithms 225 7.2.1 Insertion Sort 225 7.2.2 Bubble Sort 227 7.2.3 Selection Sort 229 7.2.4 The Cost of Exchange Sorting 230 7.3 Shellsort 231 7.4 Mergesort 233 7.5 Quicksort 236 7.6 Heapsort 243 7.7 Binsort and Radix Sort 244 7.8 An Empirical Comparison of Sorting Algorithms 251 7.9 Lower Bounds for Sorting 253 7.10 Further Reading 257 7.11 Exercises 257 7.12 Projects 261

Contents vii 8 File Processing and External Sorting 265 8.1 Primary versus Secondary Storage 265 8.2 Disk Drives 268 8.2.1 Disk Drive Architecture 268 8.2.2 Disk Access Costs 272 8.3 Buffers and Buffer Pools 274 8.4 The Programmer’s View of Files 282 8.5 External Sorting 283 8.5.1 Simple Approaches to External Sorting 285 8.5.2 Replacement Selection 288 8.5.3 Multiway Merging 290 8.6 Further Reading 295 8.7 Exercises 295 8.8 Projects 299 9 Searching 301 9.1 Searching Unsorted and Sorted Arrays 302 9.2 Self-Organizing Lists 307 9.3 Bit Vectors for Representing Sets 313 9.4 Hashing 314 9.4.1 Hash Functions 315 9.4.2 Open Hashing 320 9.4.3 Closed Hashing 321 9.4.4 Analysis of Closed Hashing 331 9.4.5 Deletion 334 9.5 Further Reading 335 9.6 Exercises 336 9.7 Projects 338 10 Indexing 341 10.1 Linear Indexing 343 10.2 ISAM 346 10.3 Tree-based Indexing 348 10.4 2-3 Trees 350 10.5 B-Trees 355 10.5.1 B+-Trees 358

viii Contents 10.5.2 B-Tree Analysis 364 10.6 Further Reading 365 10.7 Exercises 365 10.8 Projects 367 IV Advanced Data Structures 369 11 Graphs 371 11.1 Terminology and Representations 372 11.2 Graph Implementations 376 11.3 Graph Traversals 380 11.3.1 Depth-First Search 383 11.3.2 Breadth-First Search 384 11.3.3 Topological Sort 384 11.4 Shortest-Paths Problems 388 11.4.1 Single-Source Shortest Paths 389 11.5 Minimum-Cost Spanning Trees 393 11.5.1 Prim’s Algorithm 393 11.5.2 Kruskal’s Algorithm 397 11.6 Further Reading 399 11.7 Exercises 399 11.8 Projects 402 12 Lists and Arrays Revisited 405 12.1 Multilists 405 12.2 Matrix Representations 408 12.3 Memory Management 412 12.3.1 Dynamic Storage Allocation 414 12.3.2 Failure Policies and Garbage Collection 421 12.4 Further Reading 425 12.5 Exercises 426 12.6 Projects 427 13 Advanced Tree Structures 429 13.1 Tries 429

Contents ix 13.2 Balanced Trees 434 13.2.1 The AVL Tree 435 13.2.2 The Splay Tree 437 13.3 Spatial Data Structures 440 13.3.1 The K-D Tree 442 13.3.2 The PR quadtree 447 13.3.3 Other Point Data Structures 451 13.3.4 Other Spatial Data Structures 453 13.4 Further Reading 453 13.5 Exercises 454 13.6 Projects 455 V Theory of Algorithms 459 14 Analysis Techniques 461 14.1 Summation Techniques 462 14.2 Recurrence Relations 467 14.2.1 Estimating Upper and Lower Bounds 467 14.2.2 Expanding Recurrences 470 14.2.3 Divide and Conquer Recurrences 472 14.2.4 Average-Case Analysis of Quicksort 474 14.3 Amortized Analysis 476 14.4 Further Reading 479 14.5 Exercises 479 14.6 Projects 483 15 Lower Bounds 485 15.1 Introduction to Lower Bounds Proofs 486 15.2 Lower Bounds on Searching Lists 488 15.2.1 Searching in Unsorted Lists 488 15.2.2 Searching in Sorted Lists 490 15.3 Finding the Maximum Value 491 15.4 Adversarial Lower Bounds Proofs 493 15.5 State Space Lower Bounds Proofs 496 15.6 Finding the ith Best Element 499

x Contents 15.7 Optimal Sorting 501 15.8 Further Reading 504 15.9 Exercises 504 15.10Projects 507 16 Patterns of Algorithms 509 16.1 Dynamic Programming 509 16.1.1 The Knapsack Problem 511 16.1.2 All-Pairs Shortest Paths 513 16.2 Randomized Algorithms 515 16.2.1 Randomized algorithms for finding large values 515 16.2.2 Skip Lists 516 16.3 Numerical Algorithms 522 16.3.1 Exponentiation 523 16.3.2 Largest Common Factor 523 16.3.3 Matrix Multiplication 524 16.3.4 Random Numbers 526 16.3.5 The Fast Fourier Transform 527 16.4 Further Reading 532 16.5 Exercises 532 16.6 Projects 533 17 Limits to Computation 535 17.1 Reductions 536 17.2 Hard Problems 541 17.2.1 The Theory of NP-Completeness 543 17.2.2 NP-Completeness Proofs 547 17.2.3 Coping with NP-Complete Problems 552 17.3 Impossible Problems 555 17.3.1 Uncountability 556 17.3.2 The Halting Problem Is Unsolvable 559 17.4 Further Reading 561 17.5 Exercises 562 17.6 Projects 564 Bibliography 567

Contents xi Index 573

Preface We study data structures so that we can learn to write more efficient programs. But why must programs be efficient when new computers are faster every year? The reason is that our ambitions grow with our capabilities. Instead of rendering efficiency needs obsolete, the modern revolution in computing power and storage capability merely raises the efficiency stakes as we attempt more complex tasks. The quest for program efficiency need not and should not conflict with sound design and clear coding. Creating efficient programs has little to do with “program- ming tricks” but rather is based on good organization of information and good al- gorithms. A programmer who has not mastered the basic principles of clear design is not likely to write efficient programs. Conversely, concerns related to develop- ment costs and maintainability should not be used as an excuse to justify inefficient performance. Generality in design can and should be achieved without sacrificing performance, but this can only be done if the designer understands how to measure performance and does so as an integral part of the design and implementation pro- cess. Most computer science curricula recognize that good programming skills be- gin with a strong emphasis on fundamental software engineering principles. Then, once a programmer has learned the principles of clear program design and imple- mentation, the next step is to study the effects of data organization and algorithms on program efficiency. Approach: This book describes many techniques for representing data. These techniques are presented within the context of the following principles: 1. Each data structure and each algorithm has costs and benefits. Practitioners need a thorough understanding of how to assess costs and benefits to be able to adapt to new design challenges. This requires an understanding of the principles of algorithm analysis, and also an appreciation for the significant effects of the physical medium employed (e.g., data stored on disk versus main memory). 2. Related to costs and benefits is the notion of tradeoffs. For example, it is quite common to reduce time requirements at the expense of an increase in space requirements, or vice versa. Programmers face tradeoff issues regularly in all xiii

xiv Preface phases of software design and implementation, so the concept must become deeply ingrained. 3. Programmers should know enough about common practice to avoid rein- venting the wheel. Thus, programmers need to learn the commonly used data structures, their related algorithms, and the most frequently encountered design patterns found in programming. 4. Data structures follow needs. Programmers must learn to assess application needs first, then find a data structure with matching capabilities. To do this requires competence in Principles 1, 2, and 3. As I have taught data structures through the years, I have found that design issues have played an ever greater role in my courses. This can be traced through the various editions of this textbook by the increasing coverage for design patterns and generic interfaces. The first edition had no mention of design patterns. The second edition had limited coverage of a few example patterns, and introduced the dictionary ADT. With the third edition, there is explicit coverage of some design patterns that are encountered when programming the basic data structures and algorithms covered in the book. Using the Book in Class: Data structures and algorithms textbooks tend to fall into one of two categories: teaching texts or encyclopedias. Books that attempt to do both usually fail at both. This book is intended as a teaching text. I believe it is more important for a practitioner to understand the principles required to select or design the data structure that will best solve some problem than it is to memorize a lot of textbook implementations. Hence, I have designed this as a teaching text that covers most standard data structures, but not all. A few data structures that are not widely adopted are included to illustrate important principles. Some relatively new data structures that should become widely used in the future are included. Within an undergraduate program, this textbook is designed for use in either an advanced lower division (sophomore or junior level) data structures course, or for a senior level algorithms course. New material has been added in the third edition to support its use in an algorithms course. Normally, this text would be used in a course beyond the standard freshman level “CS2” course that often serves as the initial introduction to data structures. Readers of this book should typically have two semesters of the equivalent of programming experience, including at least some exposure to Java. Readers who are already familiar with recursion will have an advantage. Students of data structures will also benefit from having first completed a good course in Discrete Mathematics. Nonetheless, Chapter 2 attempts to give a reasonably complete survey of the prerequisite mathematical topics at the level necessary to understand their use in this book. Readers may wish to refer back to the appropriate sections as needed when encountering unfamiliar mathematical material.

Preface xv A sophomore-level class where students have only a little background in basic data structures or analysis (that is, background equivalent to what would be had from a traditional CS2 course) might cover Chapters 1-11 in detail, as well as se- lected topics from Chapter 13. That is how I use the book for my own sophomore- level class. Students with greater background might cover Chapter 1, skip most of Chapter 2 except for reference, briefly cover Chapters 3 and 4, and then cover chapters 5-12 in detail. Again, only certain topics from Chapter 13 might be cov- ered, depending on the programming assignments selected by the instructor. A senior-level algorithms course would focus on Chapters 11 and 14-17. Chapter 13 is intended in part as a source for larger programming exercises. I recommend that all students taking a data structures course be required to im- plement some advanced tree structure, or another dynamic structure of comparable difficulty such as the skip list or sparse matrix representations of Chapter 12. None of these data structures are significantly more difficult to implement than the binary search tree, and any of them should be within a student’s ability after completing Chapter 5. While I have attempted to arrange the presentation in an order that makes sense, instructors should feel free to rearrange the topics as they see fit. The book has been written so that once the reader has mastered Chapters 1-6, the remaining material has relatively few dependencies. Clearly, external sorting depends on understand- ing internal sorting and disk files. Section 6.2 on the UNION/FIND algorithm is used in Kruskal’s Minimum-Cost Spanning Tree algorithm. Section 9.2 on self- organizing lists mentions the buffer replacement schemes covered in Section 8.3. Chapter 14 draws on examples from throughout the book. Section 17.2 relies on knowledge of graphs. Otherwise, most topics depend only on material presented earlier within the same chapter. Most chapters end with a section entitled “Further Reading.” These sections are not comprehensive lists of references on the topics presented. Rather, I include books and articles that, in my opinion, may prove exceptionally informative or entertaining to the reader. In some cases I include references to works that should become familiar to any well-rounded computer scientist. Use of Java: The programming examples are written in Java, but I do not wish to discourage those unfamiliar with Java from reading this book. I have attempted to make the examples as clear as possible while maintaining the advantages of Java. Java is used here strictly as a tool to illustrate data structures concepts. In particular, I make use of Java’s support for hiding implementation details, including features such as classes, private class members, and interfaces. These features of the language support the crucial concept of separating logical design, as embodied in the abstract data type, from physical implementation as embodied in the data structure.

xvi Preface As with any programming language, Java has both advantages and disadvan- tages. Java is a small language. There usually is only one language feature to do something, and this has the happy tendency of encouraging a programmer toward clarity when used correctly. In this respect, it is superior to C or C++. Java serves nicely for defining and using most traditional data structures such as lists and trees. On the other hand, Java is quite poor when used to do file processing, being both cumbersome and inefficient. It is also a poor language when fine control of memory is required. As an example, applications requiring memory management, such as those discussed in Section 12.3, are difficult to write in Java. Since I wish to stick to a single language throughout the text, like any programmer I must take the bad along with the good. The most important issue is to get the ideas across, whether or not those ideas are natural to a particular language of discourse. Most program- mers will use a variety of programming languages throughout their career, and the concepts described in this book should prove useful in a variety of circumstances. Inheritance, a key feature of object-oriented programming, is used sparingly in the code examples. Inheritance is an important tool that helps programmers avoid duplication, and thus minimize bugs. From a pedagogical standpoint, how- ever, inheritance often makes code examples harder to understand since it tends to spread the description for one logical unit among several classes. Thus, my class definitions only use inheritance where inheritance is explicitly relevant to the point illustrated (e.g., Section 5.3.1). This does not mean that a programmer should do likewise. Avoiding code duplication and minimizing errors are important goals. Treat the programming examples as illustrations of data structure principles, but do not copy them directly into your own programs. One painful decision I had to make was whether to use generics in the code examples. Generics were not used in the first edition of this book. But in the years since then, Java has matured and its use in computer science curricula has greatly expanded. I now assume that readers of the text will be familiar with generic syntax. Thus, generics are now used extensively in the code examples. My implementations are meant to provide concrete illustrations of data struc- ture principles, as an aid to the textual exposition. Code examples should not be read or used in isolation from the associated text because the bulk of each exam- ple’s documentation is contained in the text, not the code. The code complements the text, not the other way around. They are not meant to be a series of commercial- quality class implementations. If you are looking for a complete implementation of a standard data structure for use in your own code, you would do well to do an Internet search. For instance, the code examples provide less parameter checking than is sound programming practice, since including such checking would obscure rather than illuminate the text. Some parameter checking and testing for other constraints (e.g., whether a value is being removed from an empty container) is included in

Preface xvii the form ofcalls to methods in class Assert. Method Assert.notFalse takes a Boolean expression. If this expression evaluates to false, then a message is printed and the program terminates immediately. Method Assert.notNull takes a reference to class Object, and terminates the program if the value of the reference is null. (To be precise, they throw an IllegalArgument- Exception, which will terminate the program unless the programmer takes ac- tion to handle the exception.) Terminating a program when a function receives a bad parameter is generally considered undesirable in real programs, but is quite adequate for understanding how a data structure is meant to operate. In real pro- gramming applications, Java’s exception handling features should be used to deal with input data errors. However, assertions provide a simpler mechanism for indi- cating required conditions in a way that is both adequate for clarifying how a data structure is meant to operate, and is easily modified into true exception handling. I make a distinction in the text between “Java implementations” and “pseu- docode.” Code labeled as a Java implementation has actually been compiled and tested on one or more Java compilers. Pseudocode examples often conform closely to Java syntax, but typically contain one or more lines of higher-level description. Pseudocode is used where I perceived a greater pedagogical advantage to a simpler, but less precise, description. Exercises and Projects: Proper implementation and analysis of data structures cannot be learned simply by reading a book. You must practice by implementing real programs, constantly comparing different techniques to see what really works best in a given situation. One of the most important aspects of a course in data structures is that it is where students really learn to program using pointers and dynamic memory al- location, by implementing data structures such as linked lists and trees. It is often where students truly learn recursion. In our curriculum, this is the first course where students do significant design, because it often requires real data structures to mo- tivate significant design exercises. Finally, the fundamental differences between memory-based and disk-based data access cannot be appreciated without practical programming experience. For all of these reasons, a data structures course cannot succeed without a significant programming component. In our department, the data structures course is one of the most difficult programming course in the curriculum. Students should also work problems to develop their analytical abilities. I pro- vide over 450 exercises and suggestions for programming projects. I urge readers to take advantage of them. Contacting the Author and Supplementary Materials: A book such as this is sure to contain errors and have room for improvement. I welcome bug reports and constructive criticism. I can be reached by electronic mail via the Internet at shaffer@vt.edu. Alternatively, comments can be mailed to

xviii Preface Cliff Shaffer Department of Computer Science Virginia Tech Blacksburg, VA 24061 The electronic posting of this book, along with a set of lecture notes for use in class can be obtained at http://www.cs.vt.edu/˜shaffer/book.html. The code examples used in the book are available at the same site. Online Web pages for Virginia Tech’s sophomore-level data structures class can be found at http://courses.cs.vt.edu/˜cs3114. This book was typeset by the author using LATEX. The bibliography was pre- pared using BIBTEX. The index was prepared using makeindex. The figures were mostly drawn with Xfig. Figures 3.1 and 9.10 were partially created using Math- ematica. Acknowledgments: It takes a lot of help from a lot of people to make a book. I wish to acknowledge a few of those who helped to make this book possible. I apologize for the inevitable omissions. Virginia Tech helped make this whole thing possible through sabbatical re- search leave during Fall 1994, enabling me to get the project off the ground. My de- partment heads during the time I have written the various editions of this book, Den- nis Kafura and Jack Carroll, provided unwavering moral support for this project. Mike Keenan, Lenny Heath, and Jeff Shaffer provided valuable input on early ver- sions of the chapters. I also wish to thank Lenny Heath for many years of stimulat- ing discussions about algorithms and analysis (and how to teach both to students). Steve Edwards deserves special thanks for spending so much time helping me on various redesigns of the C++ and Java code versions for the second and third edi- tions, and many hours of discussion on the principles of program design. Thanks to Layne Watson for his help with Mathematica, and to Bo Begole, Philip Isenhour, Jeff Nielsen, and Craig Struble for much technical assistance. Thanks to Bill Mc- Quain, Mark Abrams and Dennis Kafura for answering lots of silly questions about C++ and Java. I am truly indebted to the many reviewers of the various editions of this manu- script. For the first edition these reviewers included J. David Bezek (University of Evansville), Douglas Campbell (Brigham Young University), Karen Davis (Univer- sity of Cincinnati), Vijay Kumar Garg (University of Texas – Austin), Jim Miller (University of Kansas), Bruce Maxim (University of Michigan – Dearborn), Jeff Parker (Agile Networks/Harvard), Dana Richards (George Mason University), Jack Tan (University of Houston), and Lixin Tao (Concordia University). Without their help, this book would contain many more technical errors and many fewer insights.

Preface xix For the second edition, I wish to thank these reviewers: Gurdip Singh (Kansas State University), Peter Allen (Columbia University), Robin Hill (University of Wyoming), Norman Jacobson (University of California – Irvine), Ben Keller (East- ern Michigan University), and Ken Bosworth (Idaho State University). In addition, I wish to thank Neil Stewart and Frank J. Thesen for their comments and ideas for improvement. Third edition reviewers included Randall Lechlitner (University of Houstin, Clear Lake) and Brian C. Hipp (York Technical College). I thank them for their comments. Prentice Hall was the original print publisher for the first and second editions. Without the hard work of many people there, none of this would be possible. Au- thors simply do not create printer-ready books on their own. Foremost thanks go to Kate Hargett, Petra Rector, Laura Steele, and Alan Apt, my editors over the years. My production editors, Irwin Zucker for the second edition, Kathleen Caren for the original C++ version, and Ed DeFelippis for the Java version, kept everything moving smoothly during that horrible rush at the end. Thanks to Bill Zobrist and Bruce Gregory (I think) for getting me into this in the first place. Others at Prentice Hall who helped me along the way include Truly Donovan, Linda Behrens, and Phyllis Bregman. Thanks to Tracy Dunkelberger for her help in returning the copy- right to me, thus enabling the electronic future of this work. I am sure I owe thanks to many others at Prentice Hall for their help in ways that I am not even aware of. I am thankful to Shelley Kronzek at Dover publications for her faith in taking on the print publication of this third edition. Much expanded, with both Java and C++ versions, and many inconsistencies corrected, I am confident that this is the best edition yet. But none of us really knows whether students will prefer a free online textbook or a low-cost, printed bound version. In the end, we believe that the two formats will be mutually supporting by offering more choices. Production editor James Miller and design manager Marie Zaczkiewicz have worked hard to ensure that the production is of the highest quality. I wish to express my appreciation to Hanan Samet for teaching me about data structures. I learned much of the philosophy presented here from him as well, though he is not responsible for any problems with the result. Thanks to my wife Terry, for her love and support, and to my daughters Irena and Kate for pleasant diversions from working too hard. Finally, and most importantly, to all of the data structures students over the years who have taught me what is important and what should be skipped in a data structures course, and the many new insights they have provided. This book is dedicated to them. Cliff Shaffer Blacksburg, Virginia

PART I Preliminaries 1