Open Data Structures
Free
Description
Contents
Reviews
Language
English
ISBN
Unknown
Acknowledgments
Why This Book?
Introduction
The Need for Efficiency
Interfaces
The Queue, Stack, and Deque Interfaces
The List Interface: Linear Sequences
The USet Interface: Unordered Sets
The SSet Interface: Sorted Sets
Mathematical Background
Exponentials and Logarithms
Factorials
Asymptotic Notation
Randomization and Probability
The Model of Computation
Correctness, Time Complexity, and Space Complexity
Code Samples
List of Data Structures
Discussion and Exercises
Array-Based Lists
ArrayStack: Fast Stack Operations Using an Array
The Basics
Growing and Shrinking
Summary
FastArrayStack: An Optimized ArrayStack
ArrayQueue: An Array-Based Queue
Summary
ArrayDeque: Fast Deque Operations Using an Array
Summary
DualArrayDeque: Building a Deque from Two Stacks
Balancing
Summary
RootishArrayStack: A Space-Efficient Array Stack
Analysis of Growing and Shrinking
Space Usage
Summary
Computing Square Roots
Discussion and Exercises
Linked Lists
SLList: A Singly-Linked List
Queue Operations
Summary
DLList: A Doubly-Linked List
Adding and Removing
Summary
SEList: A Space-Efficient Linked List
Space Requirements
Finding Elements
Adding an Element
Removing an Element
Amortized Analysis of Spreading and Gathering
Summary
Discussion and Exercises
Skiplists
The Basic Structure
SkiplistSSet: An Efficient SSet
Summary
SkiplistList: An Efficient Random-Access List
Summary
Analysis of Skiplists
Discussion and Exercises
Hash Tables
ChainedHashTable: Hashing with Chaining
Multiplicative Hashing
Summary
LinearHashTable: Linear Probing
Analysis of Linear Probing
Summary
Tabulation Hashing
Hash Codes
Hash Codes for Primitive Data Types
Hash Codes for Compound Objects
Hash Codes for Arrays and Strings
Discussion and Exercises
Binary Trees
BinaryTree: A Basic Binary Tree
Recursive Algorithms
Traversing Binary Trees
BinarySearchTree: An Unbalanced Binary Search Tree
Searching
Addition
Removal
Summary
Discussion and Exercises
Random Binary Search Trees
Random Binary Search Trees
Proof of Lemma 7.1
Summary
Treap: A Randomized Binary Search Tree
Summary
Discussion and Exercises
Scapegoat Trees
ScapegoatTree: A Binary Search Tree with Partial Rebuilding
Analysis of Correctness and Running-Time
Summary
Discussion and Exercises
Red-Black Trees
2-4 Trees
Adding a Leaf
Removing a Leaf
RedBlackTree: A Simulated 2-4 Tree
Red-Black Trees and 2-4 Trees
Left-Leaning Red-Black Trees
Addition
Removal
Summary
Discussion and Exercises
Heaps
BinaryHeap: An Implicit Binary Tree
Summary
MeldableHeap: A Randomized Meldable Heap
Analysis of merge(varh1,varh2)
Summary
Discussion and Exercises
Sorting Algorithms
Comparison-Based Sorting
Merge-Sort
Quicksort
Heap-sort
A Lower-Bound for Comparison-Based Sorting
Counting Sort and Radix Sort
Counting Sort
Radix-Sort
Discussion and Exercises
Graphs
AdjacencyMatrix: Representing a Graph by a Matrix
AdjacencyLists: A Graph as a Collection of Lists
Graph Traversal
Breadth-First Search
Depth-First Search
Discussion and Exercises
Data Structures for Integers
BinaryTrie: A digital search tree
XFastTrie: Searching in Doubly-Logarithmic Time
YFastTrie: A Doubly-Logarithmic Time SSet
Discussion and Exercises
External Memory Searching
The Block Store
B-Trees
Searching
Addition
Removal
Amortized Analysis of B-Trees
Discussion and Exercises
Bibliography
Index
The book hasn't received reviews yet.
