Modern AI and machine-learning systems depend not only on statistical models but also on efficient data organization. Priority queues support best-first search and scheduling; balanced search trees maintain ordered indexes; hashing enables near-constant-time lookup; disjoint-set structures support clustering and graph connectivity; tries represent symbolic sequences; Bloom filters reduce expensive membership checks; and persistent structures preserve historical versions of data. The central challenge is to select a representation whose operational costs remain acceptable as data volume, update frequency, and concurrency increase.

Worst-case analysis alone is sometimes too pessimistic for data structures whose occasional expensive operation is paid for by many inexpensive operations. Amortized analysis provides a rigorous alternative. It determines the average cost per operation over a sequence, without relying on probability. Three standard methods are the aggregate method, the accounting method, and the potential method.

Learning Objectives

1. Cost Models and Invariants

A data structure is an abstract data type together with a representation and algorithms that preserve representation invariants. An invariant is a property that must hold before and after every public operation. For example, a binary min-heap satisfies the heap-order invariant: every parent key is less than or equal to the keys of its children.

Complexity depends on the cost model. In the unit-cost RAM model, arithmetic on a machine word, pointer access, and comparison are treated as constant-time operations. This is useful for standard asymptotic analysis, but it can conceal costs such as cache misses, memory allocation, hashing long strings, or arithmetic on arbitrarily large integers.

A worst-case bound applies to every input of size n. An expected bound averages over a specified source of randomness, such as a randomized hash function. An amortized bound applies to a sequence of operations and does not require a probability distribution. These distinctions are essential: expected O(1) hashing is not the same claim as worst-case O(1), and amortized O(1) dynamic-array insertion does not mean every insertion costs O(1).

2. Heaps and Priority Queues

A priority queue supports insertion, inspection of the minimum or maximum, and removal of that extremal element. A binary heap is a complete binary tree represented compactly in an array. With zero-based indexing, the children of node i are at indices 2i+1 and 2i+2, while its parent is at index ⌊(i−1)/2⌋ for i > 0.

For a min-heap, the invariant is A[parent(i)] ≤ A[i]. The height is O(log n), so insertion and extract-min take O(log n); peek-min takes O(1). Building a heap from n arbitrary elements using bottom-up heap construction takes O(n), not O(n log n). The reason is that most nodes are near the leaves and require little downward movement.

A d-ary heap reduces height to O(log_d n), but each downward step may inspect up to d children. It can therefore be useful when fewer levels and improved locality are more important than the cost of selecting a child. Fibonacci heaps provide stronger amortized bounds for some graph algorithms: insert and decrease-key are O(1) amortized, while extract-min is O(log n) amortized. Their pointer-heavy implementation, however, may perform worse than binary heaps in practical systems.

For a min-heap, Dijkstra’s algorithm with a binary heap and adjacency lists runs in O((V + E) log V), where V is the number of vertices and E is the number of edges, assuming nonnegative edge weights. The data structure improves the algorithm by efficiently selecting the next smallest tentative distance.

3. Balanced Search Trees

A binary search tree maintains the ordering invariant that keys in the left subtree precede the node key and keys in the right subtree follow it. An unbalanced tree can degenerate into a chain, giving O(n) search, insertion, and deletion. Balanced trees limit height to O(log n).

AVL trees

where height is measured in edges. The invariant is BF(v) ∈ {−1,0,1}. Rotations restore balance after updates. Search, insertion, and deletion are O(log n) worst case. AVL trees usually provide tighter height than red–black trees, making them attractive for lookup-intensive workloads.

Red–black trees

A red–black tree colors each node red or black and maintains rules including: the root is black; red nodes cannot have red children; and every path from a node to a null leaf has the same black height. These rules imply height O(log n). Search, insertion, and deletion are O(log n) worst case. Red–black trees often require fewer rotations during updates and are common in standard libraries.

B-trees and external memory

For databases and file systems, the relevant cost is often block transfer rather than CPU comparison. A B-tree stores many keys in each node, reducing disk or SSD accesses. If branching factor is b and the tree contains n keys, its height is approximately O(log_b n). B+ trees store records or record pointers in linked leaves, supporting efficient range scans. The correct structure is therefore determined not only by asymptotic RAM complexity but also by the memory hierarchy.

4. Hashing

A hash table maps a key to an array position using a hash function h. Collisions are unavoidable when the key universe is larger than the table. Separate chaining stores a collection of entries per slot. Open addressing stores all entries in the table and probes alternative positions.

where n is the number of stored entries and m is the number of slots. Under simple uniform hashing, expected chain length is α, and expected search cost is O(1 + α). Maintaining α below a chosen threshold through resizing gives expected O(1) insertion and lookup. These are expected or amortized claims, not unconditional worst-case guarantees.

In open addressing, linear probing examines consecutive slots. It has excellent cache locality but suffers primary clustering. Quadratic probing reduces some clustering but requires careful parameters to ensure adequate coverage. Double hashing uses a second hash function to determine the probe step.

Hash tables are vulnerable to adversarial collision attacks if attackers can predict the hash function. Defenses include keyed or randomized hashing, conservative load limits, collision-resistant designs where appropriate, and request-rate controls. Hashing is unsuitable when sorted order or efficient range queries are required.

5. Disjoint-Set Union

The disjoint-set union (DSU), or union–find structure, maintains a partition of elements into nonoverlapping sets. Its operations are Make-Set, Find(x), which returns a representative, and Union(x,y), which merges two sets.

A forest representation uses parent pointers. Union by rank or size attaches the smaller tree below the larger. Path compression changes each visited node’s parent to the representative during Find. With both heuristics, a sequence of m operations on n elements has total time O(m α(n)), where α is the inverse Ackermann function. For all practical machine-sized inputs, α(n) is less than a small constant, but it should not be casually replaced by a mathematical constant in formal analysis.

DSU is central to Kruskal’s minimum-spanning-tree algorithm. Edges are processed in nondecreasing weight order; an edge is accepted if its endpoints belong to different sets, then their sets are united. Sorting costs O(E log E), while all DSU operations contribute O(E α(V)).

DSU does not naturally support splitting a set, reporting all members efficiently after arbitrary updates, or maintaining rich aggregate information unless additional metadata and update rules are designed.

6. Tries and String Indexing

A trie represents strings by paths from a root, with one edge or transition per symbol. A terminal marker distinguishes a complete word from a prefix. For a string of length L, search, insertion, and deletion take O(L), independent of the number of stored strings, assuming transition access is O(1).

A full array of transitions at every node gives fast access but can waste memory, especially with a large alphabet. Sparse maps reduce memory but add lookup overhead. Radix trees compress chains of single-child nodes; ternary search tries trade alphabet-array space for comparison-based navigation. Tries support autocomplete, prefix filtering, routing tables, and token dictionaries.

In natural-language processing, trie design must account for normalization, Unicode, case folding, tokenization, and adversarially long inputs. A trie storing raw user strings can also reveal sensitive prefixes, so access control and privacy-aware logging remain necessary.

7. Bloom Filters

A Bloom filter is a compact probabilistic structure for testing set membership. It consists of m bits and k hash functions. To insert an element, the k corresponding bits are set to 1. A query returning a zero bit proves nonmembership; a query finding all bits set may be a false positive.

Under the standard assumptions of independent, uniformly distributed hash locations and n inserted elements, the probability that a particular bit remains zero is approximately

where p is false-positive probability, m is the number of bits, n is the number of inserted items, and k is the number of hash functions. The value of k minimizing this approximation is

The filter has no false negatives for correctly inserted items, but it cannot normally delete items because clearing a shared bit could invalidate another item. Counting Bloom filters replace bits with small counters, increasing memory and introducing counter overflow considerations.

Bloom filters are useful before expensive database lookups, in distributed caches, and for duplicate suppression. They must never be used as proof that an item exists. They also reveal approximate membership information and may be exploitable if hash functions or inserted data are predictable.

8. Persistent Data Structures

A persistent data structure preserves prior versions after an update. In a partially persistent structure, updates are allowed only to the newest version; in a fully persistent structure, any version may be updated to create a new version. Confluent persistence additionally permits combining versions.

The principal technique is path copying. When updating a tree, copy the nodes on the root-to-updated-leaf path and share all unaffected subtrees. A balanced tree update then uses O(log n) new nodes and O(log n) time while preserving the old version. Structural sharing reduces duplication, but memory reclamation becomes more complex because an object remains live while any version references it.

Persistent structures support experiment tracking, audit trails, temporal queries, undo operations, reproducible machine-learning pipelines, and versioned feature dictionaries. They are not automatically thread-safe, and immutable interfaces do not eliminate confidentiality risks: old versions may retain data that a deletion policy intended to remove.

9. Amortized Analysis

For operations c₁, c₂, …, c_m, the total actual cost is ∑ᵢ cᵢ. An amortized bound assigns a cost to each operation such that the total assigned cost upper-bounds the total actual cost for every valid sequence.

Aggregate method

The aggregate method bounds the total cost of a sequence of m operations and divides by m. Consider a dynamic array that doubles its capacity when full. During m append operations, copying costs occur at capacities 1, 2, 4, … . The total number of copied elements is less than

Adding at most m direct writes gives total cost less than 3m, so the amortized cost per append is O(1). The bound assumes geometric growth and that copying one element costs O(1).

Accounting method

The accounting method charges an amortized price âᵢ to operation i. The difference âᵢ − cᵢ is stored as credit, which must never become negative. For the doubling array, charge 3 units per append: one pays for the current write and two are saved to pay for future copying. Since enough credit accumulates before each resize, total amortized charge is O(m).

Potential method

Let Φ(Dᵢ) be a nonnegative potential of the data structure after operation i, with initial potential Φ(D₀) = 0 or otherwise known. Define amortized cost

If Φ(D_m) ≥ 0 and Φ(D₀) = 0, total actual cost is at most total amortized cost. For a dynamic array with size s and capacity q, one possible potential during the growth phase is Φ = 2s − q, provided the chosen phase and resizing policy make it nonnegative. The potential rises during ordinary appends and drops when copying occurs, paying for the expensive operation.

A potential function is not unique. A valid choice must reflect stored work and preserve the required nonnegativity or initial-potential conditions. Poorly chosen potentials can produce invalid or unhelpful bounds.

Amortized analysis also applies to splay trees, where a sequence of operations has logarithmic amortized behavior under suitable access lemmas, and to union–find, although its sharp inverse-Ackermann analysis requires more sophisticated arguments than elementary potential functions.

10. Comparative Design Guidance

Structure	Typical strength	Main bound	Important limitation
Binary heap	Extremal priority access	O(log n) update	No efficient arbitrary search
AVL/red–black tree	Ordered lookup and updates	O(log n) worst case	More pointer and balancing overhead
Hash table	Exact key lookup	Expected O(1)	No natural ordering; collision attacks
DSU	Dynamic connectivity merging	O(α(n)) amortized per operation	Poor support for splits
Trie	Prefix and string queries	O(L)	Potentially high memory use
Bloom filter	Compact approximate membership	O(k) query	False positives; usually no deletion
Persistent tree	Versioned access	Often O(log n) update	Extra memory and reclamation complexity

Selection should begin with workload requirements: ordering, prefix operations, deletion, persistence, adversarial exposure, external storage, and latency variance. A theoretically superior structure can lose in practice through cache behavior, allocation cost, contention, or poor constant factors.

Applied Case: Feature-Store Admission Filtering

Background

Consider an illustrative online recommendation service. Each request proposes a feature key that may require an expensive lookup in a distributed feature store. The service must reject obviously unknown keys quickly while retaining exact correctness.

Problem

A direct lookup for every key creates network traffic and latency. A hash table is exact but must be replicated and may consume substantial memory. A Bloom filter can provide a compact preliminary test, but false positives must be safe.

Approach

The engineering team builds a Bloom filter from the current valid-key set. A query returning “definitely absent” is rejected locally. A query returning “possibly present” proceeds to the authoritative feature store. The filter is rebuilt periodically and versioned with the feature catalog. Because new valid keys may appear between rebuilds, the system uses a conservative policy: a false negative caused by a stale filter must not become a final rejection. A secondary exact path handles catalog updates.

Suppose n = 1,000,000 keys and the design allocates 10,000,000 bits, so m/n = 10. The approximately optimal number of hash functions is

Thus k = 7 is a reasonable integer choice. The approximate false-positive rate is

or about 0.82%, under the standard independence assumptions. The calculation is a planning estimate; production measurements must account for hash correlation, key distribution, filter aging, and workload changes.

Outcome and learning points

The filter reduces unnecessary remote requests while preserving correctness through authoritative confirmation. The case illustrates a general principle: probabilistic structures may optimize a safe prefilter, but they should not replace a source of truth when false positives or stale state matter. Versioning, observability, privacy review, and rebuild policies are part of the data-structure design, not afterthoughts.

Challenges, Governance, and Contemporary Directions

Advanced structures create operational risks. Hash tables require defenses against denial-of-service collision patterns. Bloom filters can leak information about membership and should not be treated as privacy mechanisms. Persistent versions may conflict with deletion, retention, and “right to erasure” requirements. Tries and logs can expose personally identifiable strings. AI systems must document whether approximate membership decisions affect individuals and provide an exact fallback where errors have material consequences.

Contemporary systems increasingly combine structures: a B+ tree for durable ordered storage, a Bloom filter for negative caching, a hash table for hot entries, and a persistent log for reproducibility. Learned indexes use models to predict record positions, but they require fallback mechanisms and careful analysis under distribution shift. Hardware-conscious and concurrent variants emphasize cache locality, lock-free access, NUMA placement, and memory reclamation. These developments do not eliminate classical invariants; they make them more important because correctness must survive optimization and changing workloads.

Best Practices

Chapter Summary

Heaps provide efficient priority-queue operations and support graph algorithms. AVL and red–black trees preserve logarithmic ordered access, while B-trees are designed for block-oriented storage. Hash tables offer expected constant-time exact lookup when load and hashing assumptions are controlled. Disjoint-set union supports incremental connectivity with near-constant amortized cost through union by size or rank and path compression. Tries support length-sensitive prefix operations, and Bloom filters provide compact membership prefilters with false positives but no ordinary false negatives. Persistent structures preserve historical versions through structural sharing.

Amortized analysis evaluates operation sequences rather than isolated worst cases. The aggregate method bounds total cost directly; the accounting method stores prepaid credit; and the potential method represents stored work mathematically. Correct use requires explicit assumptions and a valid potential or credit argument. In professional AI and data systems, choosing a structure requires balancing asymptotic complexity with memory hierarchy, adversarial behavior, concurrency, privacy, reproducibility, and regulatory obligations.

Key Terms

Abstract data type: A specification of supported operations and their behavior, independent of representation.

Amortized analysis: Analysis of average cost over every operation sequence, without requiring probability.

Bloom filter: A compact probabilistic membership structure with possible false positives.

B-tree: A multiway balanced search tree optimized for block or external-memory access.

Disjoint-set union: A structure supporting partition merging and representative queries.

Heap invariant: The condition that each parent has priority no greater than its children in a min-heap.

Path compression: A union–find technique that makes visited nodes point directly to a representative.

Persistent data structure: A structure that preserves access to previous versions after updates.

Potential function: A nonnegative measure of stored work used in potential-method analysis.

Structural sharing: Reuse of unchanged components between data-structure versions.

Union by rank: A union–find heuristic attaching a lower-rank tree below a higher-rank tree.

Review Questions

Short Answer Questions

Long Answer Questions

Analytical / Application Questions

Multiple Choice Questions with Answers

Question 1

Question 2

Question 3

Under standard assumptions, what does a Bloom filter query returning a zero bit prove?

Question 4

Question 5

Question 6

What is the amortized cost of append in a dynamic array that doubles capacity when full?

Question 7

Question 8

Question 9

Question 10

For a Bloom filter with m = 10n bits, the approximately optimal number of hash functions is closest to:

Chapter 2 Advanced Data Structures and Amortized Analysis

Advanced Data Structures and Amortized Analysis

Introduction