Open Data Structures: An Introduction

About this book

Pat Morin’s Open Data Structures explains how representations support operations and how their costs can be proved. The fourteen-chapter text compares array-based and linked structures, hashing, search trees, heaps, sorting, graphs, integer structures, and external-memory searching. This guide emphasizes invariants and tradeoffs. A data structure is evaluated against the operations an application needs, not ranked as universally best from a single complexity figure.

Chapter and section guide

1. Introduction

Interfaces specify required behavior, while implementations determine how that behavior is achieved. The chapter introduces computational models, asymptotic analysis, and amortized reasoning. Students should distinguish worst-case, expected, and amortized cost, which describe different guarantees. A representation invariant explains what must remain true after every operation. These ideas make later comparisons meaningful rather than reducing them to memorized tables.

Study application: Define a small list interface and separate its behavior from two possible representations. State which operation costs you would compare.

2. Array-Based Lists

Arrays support direct indexed access, while insertion, removal, and resizing can require moving elements. Circular and multiple-array arrangements alter those tradeoffs. A resize may be expensive in one operation while remaining manageable across a sequence through amortized analysis. Students should trace where data moves and distinguish capacity from current size.

Study application: Trace insertions that trigger a resize and count the copied elements. Explain why the most expensive single insertion differs from the amortized cost.

3. Linked Lists

Linked structures make connections explicit through references rather than contiguous positions. Some local updates are inexpensive when the relevant node is known, but finding a position can require traversal. Students should distinguish access to a node from access by index and account for pointer maintenance. A missing update can preserve output briefly while corrupting the structure for later operations.

Study application: Trace a removal at the beginning, middle, and end of a small list. State every link that changes and the invariant each update preserves.

4. Skiplists

Skiplists use multiple levels of links to accelerate search through an ordered collection. Randomization supports expected performance, while the base level retains the full order. Students should understand the search path and distinguish an expected guarantee from a deterministic bound for every arrangement. Updates must maintain links at the levels assigned to an element.

Study application: Draw a small skiplist and trace a search and insertion. Explain how an unfavorable level assignment could affect one operation without invalidating the structure’s correctness.

5. Hash Tables

Hashing maps keys into a representation designed for efficient lookup and updates. Collisions are normal possibilities requiring a strategy, not evidence that hashing has failed. Load factor, hash assumptions, and resizing affect performance. Students should distinguish equality of keys from equality of hash values and state what happens when a collision occurs.

Study application: Construct a small collision example and trace the source’s handling strategy. Explain why a good average result does not eliminate the need to analyze adversarial or unfavorable inputs.

6. Binary Trees

Binary-tree structure supports recursive traversal and search organization. A tree’s height influences the cost of following a path, and a plain binary search tree can become highly unbalanced. Students should distinguish the binary-tree shape from the ordering invariant of a search tree. Correct insertion preserves order but does not automatically preserve low height.

Study application: Insert sorted values into an ordinary binary search tree and compare the resulting height with a balanced shape. Explain the consequence for search.

7. Random Binary Search Trees

Randomized search-tree methods use probabilistic structure to obtain expected performance. The chapter connects the distribution of shapes with efficient operations. Students should identify where randomness enters and what property remains deterministic, such as the search-order invariant. Correctness is separate from the expectation used in analyzing running time.

Study application: Trace a small randomized tree operation and verify the ordering property. Explain which part of the performance argument depends on random choices.

8. Scapegoat Trees

Scapegoat trees maintain useful balance through occasional rebuilding of a subtree. Some operations can therefore cost more than a simple local update, while the sequence can have a controlled amortized cost. Students should follow both the trigger for rebuilding and the invariant restored by it. This provides a concrete example of paying for rare expensive work across many operations.

Study application: Describe a sequence that eventually triggers rebuilding. Explain what is rebuilt, why correctness is preserved, and why one expensive operation does not alone settle the sequence’s amortized complexity.

9. Red-Black Trees

Red-black conditions constrain a search tree’s shape through local rules, with rotations and recoloring used to restore them after updates. The color labels matter through the invariants they express. Students should verify ordering and balance conditions separately. A rotation changes local structure while preserving the order in which keys appear. Understanding that preservation is essential before memorizing update cases.

Study application: Perform one rotation on a labeled small tree and list the keys in order before and after. Then explain which additional color or balance condition the update addresses.

10. Heaps

A heap supports priority-oriented operations rather than arbitrary sorted access. Its ordering invariant ensures that an extreme element is available in a designated place without making the entire representation sorted. Array layout can encode a tree implicitly. Students should distinguish a priority queue interface from a specific heap implementation and trace the repair path after an update.

Study application: Insert a new priority and remove the minimum in a small heap. Explain why examining the underlying array as a sorted list would be incorrect.

11. Sorting Algorithms

Sorting methods differ in assumptions, comparisons, movement, memory use, and guarantees. Comparison-based lower bounds apply within a specified model and do not automatically constrain methods using additional key structure. Students should connect an algorithm’s steps with its invariant and distinguish stability from correctness of ordering. A benchmark should state the input family and what work is measured.

Study application: Compare two sorting methods on small ordered and reverse-ordered inputs. Explain the relevant guarantee and whether equal-key order is preserved.

12. Graphs

Graph representations encode vertices and edges with different space and access tradeoffs. Traversal algorithms maintain information about what has been discovered and explored. Students should choose a representation suited to the graph’s density and operations. A traversal’s result depends on conventions such as the starting vertex and neighbor order, while reachability conclusions follow from the algorithm’s logic.

Study application: Represent one graph with an adjacency matrix and adjacency lists. Compare space and the work needed to enumerate one vertex’s neighbors.

13. Integer Data Structures

Integer keys provide additional structure that algorithms can exploit beyond generic comparisons. Bit-level representation and the computational model become central to the performance claim. Students should state word-size assumptions and the key universe rather than treat an integer-specific bound as applying to arbitrary objects. The chapter demonstrates that a different model can create different algorithmic possibilities.

Study application: Explain how a fixed-width integer key offers information unavailable to a comparison-only interface. Identify the assumptions that would need revisiting for unbounded or noninteger keys.

14. External-Memory Searching

When data exceed fast memory, transferring blocks can dominate cost. External-memory structures organize information to reduce those transfers rather than optimize only CPU comparisons. A node may hold many keys to match the block model. Students should identify the unit of cost and distinguish an in-memory pointer traversal from a disk-oriented access pattern. The representation is chosen to suit the hardware model’s relevant constraint.

Study application: Compare a binary search tree with a block-oriented search structure conceptually. Explain why fewer comparisons need not mean fewer expensive block transfers.

Study instructions

1. Define the required operations and representation invariant before implementing a structure.
2. Trace small updates by hand, including empty, singleton, boundary, and duplicate-key cases where relevant.
3. Label every complexity claim as worst-case, expected, or amortized and state its assumptions.
4. Compare structures using a workload rather than one operation in isolation.
5. Use tests to expose implementation errors and a separate argument to justify general correctness or cost.

Practice and review task

Choose a fictional application with a clear workload. Compare an array-based list, hash table, and ordered tree for its needs, then justify a choice using operations, memory, ordering requirements, and guarantee type.

Questions for reflection

Why is constant-time indexed access different from constant-time insertion? How can changing the unit of cost from comparisons to memory blocks change the preferred structure?

Sources and coverage

This original study guide follows Athabasca University Press edition, 2013. It draws on the source contents, chapter introductions, selected explanations and examples, and review material. It condenses the resource rather than replacing the full text; study applications are original exercises.

Reviewed source text; Book and cover catalog record.