Open Data Structures

1 Open data Structures (in Java)Edition MorinContentsAcknowledgmentsixWhy This Book?xi1 The Need for Efficiency .. Interfaces .. ,Stack, andDequeInterfaces .. : Linear Sequences .. : Unordered Sets .. : Sorted Sets .. Mathematical Background .. and Logarithms .. Notation .. and Probability .. The Model of Computation .. Correctness, Time Complexity, and Space Complexity .. Code Samples .. List of data Structures .. Discussion and Exercises.

2 262 Array-Based : Fast Stack Operations Using an Array .. Basics .. and Shrinking .. : An Optimized ArrayStack .. : An Array-Based Queue .. : Fast Deque Operations Using an Array .. : Building a Deque from Two Stacks .. : A Space-Efficient Array Stack .. of Growing and Shrinking .. Usage .. Square Roots .. Discussion and Exercises .. 593 Linked : A Singly-Linked List .. Operations .. : A Doubly-Linked List .. and Removing.

3 : A Space-Efficient Linked List .. Requirements .. Elements .. an Element .. an Element .. Analysis of Spreading and Gathering .. Discussion and Exercises .. 824 The Basic Structure .. : An EfficientSSet.. : An Efficient Random-AccessList.. Analysis of Skiplists .. Discussion and Exercises .. 1025 Hash : Hashing with Chaining .. Hashing .. : Linear Probing .. of Linear Probing .. Hashing .. Hash Codes.

4 Codes for Primitive data Types .. Codes for Compound Objects .. Codes for Arrays and Strings .. Discussion and Exercises .. 1286 Binary : A Basic Binary Tree .. Algorithms .. Binary Trees .. : An Unbalanced Binary Search Tree .. Discussion and Exercises .. 1477 Random Binary Search Random Binary Search Trees .. of Lemma .. : A Randomized Binary Search Tree .. Discussion and Exercises .. 168vContents8 Scapegoat : A Binary Search Tree with Partial Rebuild-ing.

5 Of Correctness and Running-Time .. Discussion and Exercises .. 1819 Red-Black 2-4 Trees .. a Leaf .. a Leaf .. : A Simulated 2-4 Tree .. Trees and 2-4 Trees .. Red-Black Trees .. Summary .. Discussion and Exercises .. 20610 : An Implicit Binary Tree .. Summary .. : A Randomized Meldable Heap .. Analysis ofmerge(h1,h2) .. Summary .. Discussion and Exercises .. 22211 Sorting Comparison-Based Sorting .. Merge-Sort.

6 Quicksort .. Heap-sort .. A Lower-Bound for Comparison-Based Sorting .. Counting Sort and Radix Sort .. Counting Sort .. Radix-Sort .. Discussion and Exercises .. 24312 : Representing a Graph by a Matrix .. : A Graph as a Collection of Lists .. Graph Traversal .. Breadth-First Search .. Depth-First Search .. Discussion and Exercises .. 26113 data Structures for : A digital search tree .. : Searching in Doubly-Logarithmic Time .. : A Doubly-Logarithmic TimeSSet.

7 Discussion and Exercises .. 28014 External Memory The Block Store .. B-Trees .. Searching .. Addition .. Removal .. Amortized Analysis ofB-Trees .. Discussion and Exercises .. 304 Bibliography309 Index317viiAcknowledgmentsI am grateful to Nima Hoda, who spent a summer tirelessly proofread-ing many of the chapters in this book; to the students in the Fall 2011offering of COMP2402/2002, who put up with the first draft of this bookand spotted many typographic, grammatical, and factual errors; and toMorgan Tunzelmann at Athabasca University Press, for patiently editingseveral near-final This Book?

8 There are plenty of books that teach introductory data Structures . Someof them are very good. Most of them cost money, and the vast majorityof computer science undergraduate students will shell out at least somecash on a data Structures free data Structures books are available online. Some are verygood, but most of them are getting old. The majority of these books be-came free when their authors and/or publishers decided to stop updat-ing them. Updating these books is usually not possible, for two reasons:(1) The copyright belongs to the author and/or publisher, either of whommay not allow it.

9 (2) Thesource codefor these books is often not avail-able. That is, the Word, WordPerfect, FrameMaker, or LATEX source forthe book is not available, and even the version of the software that han-dles this source may not be goal of this project is to free undergraduate computer science stu-dents from having to pay for an introductory data Structures book. I havedecided to implement this goal by treating this book like an Open Sourcesoftware project. The LATEX source, Java source, and build scripts for thebook are available to download from the author s website1and also, moreimportantly, on a reliable source code management source code available there is released under a Creative CommonsAttribution license, meaning that anyone is free toshare: to copy, dis-tribute and transmit the work; and toremix: to adapt the work, includingthe right to make commercial use of the work.

10 The only condition onthese rights isattribution: you must acknowledge that the derived workcontains code and/or text This Book?Anyone can contribute corrections/fixes using thegitsource-codemanagement system. Anyone can also fork the book s sources to developa separate version (for example, in another programming language). Myhope is that, by doing things this way, this book will continue to be a use-ful textbook long after my interest in the project, or my pulse, (whichevercomes first) has 1 IntroductionEvery computer science curriculum in the world includes a course on datastructures and algorithms.