
Free
Open Data Structures
By Pat Morin
Free
The publisher has enabled DRM protection, which means that you need to use the BookFusion iOS, Android or Web app to read this eBook. This eBook cannot be used outside of the BookFusion platform.
Book Description
Table of Contents
- Front Matter
- Contents
- Acknowledgments
- Why This Book?
- 1. Introduction
- 1.1 The Need for Efficiency
- 1.2 Interfaces
- 1.2.1 The Queue, Stack, and Deque Interfaces
- 1.2.2 The List Interface: Linear Sequences
- 1.2.3 The USet Interface: Unordered Sets
- 1.2.4 The SSet Interface: Sorted Sets
- 1.3 Mathematical Background
- 1.3.1 Exponentials and Logarithms
- 1.3.2 Factorials
- 1.3.3 Asymptotic Notation
- 1.3.4 Randomization and Probability
- 1.4 The Model of Computation
- 1.5 Correctness, Time Complexity, and Space Complexity
- 1.6 Code Samples
- 1.7 List of Data Structures
- 1.8 Discussion and Exercises
- 2. Array-Based Lists
- 2.1 ArrayStack: Fast Stack Operations Using an Array
- The Basics
- Growing and Shrinking
- Summary
- 2.2 FastArrayStack: An Optimized ArrayStack
- 2.3 ArrayQueue: An Array-Based Queue
- 2.3.1 Summary
- 2.4 ArrayDeque: Fast Deque Operations Using an Array
- 2.4.1 Summary
- 2.5 DualArrayDeque: Building a Deque from Two Stacks
- 2.5.1 Balancing
- 2.5.2 Summary
- 2.6 RootishArrayStack: A Space-Efficient Array Stack
- 2.6.1 Analysis of Growing and Shrinking
- 2.6.2 Space Usage
- 2.6.3 Summary
- 2.6.4 Computing Square Roots
- 2.7 Discussion and Exercises
- 2.1 ArrayStack: Fast Stack Operations Using an Array
- 3. Linked Lists
- 3.1 SLList: A Singly-Linked List
- 3.1.1 Queue Operations
- 3.1.2 Summary
- 3.2 DLList: A Doubly-Linked List
- 3.2.1 Adding and Removing
- 3.2.2 Summary
- 3.3 SEList: A Space-Efficient Linked List
- 3.3.1 Space Requirements
- 3.3.2 Finding Elements
- 3.3.3 Adding an Element
- 3.3.4 Removing an Element
- 3.3.5 Amortized Analysis of Spreading and Gathering
- 3.3.6 Summary
- 3.4 Discussion and Exercises
- 3.1 SLList: A Singly-Linked List
- 4. Skiplists
- 4.1 The Basic Structure
- 4.2 SkiplistSSet: An Efficient SSet
- 4.2.1 Summary
- 4.3 SkiplistList: An Efficient Random-Access List
- 4.3.1 Summary
- 4.4 Analysis of Skiplists
- 4.5 Discussion and Exercises
- 5. Hash Tables
- 5.1 ChainedHashTable: Hashing with Chaining
- 5.1.1 Multiplicative Hashing
- 5.1.2 Summary
- 5.2 LinearHashTable: Linear Probing
- 5.2.1 Analysis of Linear Probing
- 5.2.2 Summary
- 5.2.3 Tabulation Hashing
- 5.3 Hash Codes
- 5.3.1 Hash Codes for Primitive Data Types
- 5.3.2 Hash Codes for Compound Objects
- 5.3.3 Hash Codes for Arrays and Strings
- 5.4 Discussion and Exercises
- 5.1 ChainedHashTable: Hashing with Chaining
- 6. Binary Trees
- 6.1 BinaryTree: A Basic Binary Tree
- 6.1.1 Recursive Algorithms
- 6.1.2 Traversing Binary Trees
- 6.2 BinarySearchTree: An Unbalanced Binary Search Tree
- 6.2.1 Searching
- 6.2.2 Addition
- 6.2.3 Removal
- 6.2.4 Summary
- 6.3 Discussion and Exercises
- 6.1 BinaryTree: A Basic Binary Tree
- 7. Random Binary Search Trees
- 7.1 Random Binary Search Trees
- 7.1.1 Proof of Lemma 7.1
- 7.1.2 Summary
- 7.2 Treap: A Randomized Binary Search Tree
- 7.2.1 Summary
- 7.3 Discussion and Exercises
- 7.1 Random Binary Search Trees
- 8. Scapegoat Trees
- 8.1 ScapegoatTree: A Binary Search Tree with Partial Rebuilding
- 8.1.1 Analysis of Correctness and Running-Time
- 8.1.2 Summary
- 8.2 Discussion and Exercises
- 8.1 ScapegoatTree: A Binary Search Tree with Partial Rebuilding
- 9. Red-Black Trees
- 9.1 2-4 Trees
- 9.1.1 Adding a Leaf
- 9.1.2 Removing a Leaf
- 9.2 RedBlackTree: A Simulated 2-4 Tree
- 9.2.1 Red-Black Trees and 2-4 Trees
- 9.2.2 Left-Leaning Red-Black Trees
- 9.2.3 Addition
- 9.2.4 Removal
- 9.3 Summary
- 9.4 Discussion and Exercises
- 9.1 2-4 Trees
- 10. Heaps
- 10.1 BinaryHeap: An Implicit Binary Tree
- 10.1.1 Summary
- 10.2 MeldableHeap: A Randomized Meldable Heap
- 10.2.1 Analysis of merge(varh1,varh2)
- 10.2.2 Summary
- 10.3 Discussion and Exercises
- 10.1 BinaryHeap: An Implicit Binary Tree
- 11. Sorting Algorithms
- 11.1 Comparison-Based Sorting
- 11.1.1 Merge-Sort
- 11.1.2 Quicksort
- 11.1.3 Heap-sort
- 11.1.4 A Lower-Bound for Comparison-Based Sorting
- 11.2 Counting Sort and Radix Sort
- 11.2.1 Counting Sort
- 11.2.2 Radix-Sort
- 11.3 Discussion and Exercises
- 11.1 Comparison-Based Sorting
- 12. Graphs
- 12.1 AdjacencyMatrix: Representing a Graph by a Matrix
- 12.2 AdjacencyLists: A Graph as a Collection of Lists
- 12.3 Graph Traversal
- 12.3.1 Breadth-First Search
- 12.3.3 Depth-First Search
- 12.4 Discussion and Exercises
- 13. Data Structures for Integers
- 13.1 BinaryTrie: A digital search tree
- 13.2 XFastTrie: Searching in Doubly-Logarithmic Time
- 13.3 YFastTrie: A Doubly-Logarithmic Time SSet
- 13.4 Discussion and Exercises
- 14. External Memory Searching
- 14.1 The Block Store
- 14.2 B-Trees
- 14.2.1 Searching
- 14.2.2 Addition
- 14.2.3 Removal
- 14.2.4 Amortized Analysis of B-Trees
- 14.3 Discussion and Exercises
- Bibliography
- Index
The book hasn't received reviews yet.
You May Also Like
Transactions of the American Society of Civil Engineers, vol. LXX, Dec. 1910 Federal Investigations of Mine Accidents, Structural Materials and Fuels. Paper No. 1171
By Herbert M. (Herbert Michael) Wilson
Transactions of the American Society of Civil Engineers, Vol. LXX, Dec. 1910 Address at the 42d Annual Convention, Chicago, Illinois, June 21st, 1910, Paper No. 1178
By J. A. (John Anderson) Bensel
The Mechanical Properties of Wood Including a Discussion of the Factors Affecting the Mechanical Properties, and Methods of Timber Testing
By Samuel J. (Samuel James) Record
Samuel F. B. Morse, His Letters and Journals In Two Volumes, Volume II
By Samuel Finley Breese Morse