Open Data Structures
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.
Description
Contents
Reviews
Language
Unknown
ISBN
Unknown
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
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
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
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
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
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
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
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
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
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.
