Everything Data Structures

A complete course on data structures: from asymptotic analysis to the storage engines behind Spanner and Kafka.

Five volumes · 31 chapters · 4 appendices · ~55,000 words · Python, C, C++, Java, and Go

By Ngoc Anh Khoa Doan, with the editorial help of Claude.

Start here

You do not have to read this front to back. Pick the track that matches what you’re doing:

The full syllabus with chapter-by-chapter reading lists is in the repository README.

What makes this different

It doesn’t stop at red-black trees. Most treatments end where the undergraduate syllabus ends. This one continues through competitive-programming machinery (link-cut trees, wavelet trees, Mo’s algorithm)into research-grade structures like FM-indexes and succinct trees, and then out the other side into distributed systems.

Volume V argues something specific. That network topologies and system designs are data structures, composed at scale. A routing table is a trie. Consistent hashing is a hash ring. A message queue is a persistent FIFO with durability guarantees. Once you see systems this way, system design stops being a separate discipline you memorize and starts being a subject you can reason about from first principles.

Every chapter answers the same questions. What is the idea? What invariant holds? What do the operations cost, and why? What does the code look like? Where is this actually used? Who invented it, and what problem forced them to?

Tradeoffs are stated plainly. Fibonacci heaps have the best asymptotic bounds on the page and lose to binary heaps in practice, and this book says so, and explains why. Asymptotic superiority is a claim about a limit, and the limit may sit far beyond any input you will ever see.

The five volumes

Volume I: Foundations and Fundamentals Complexity analysis, memory and pointers, arrays, linked lists, stacks, queues, trees, binary search trees, self-balancing trees, heaps, and B-trees. Everything a working programmer must know.

Volume II: Advanced Structures and Algorithms Graphs and their algorithms, hash tables in depth, and string structures: tries, suffix trees, suffix arrays.

Volume III: Specialized and Modern Structures Probabilistic structures, spatial indexes, external-memory and cache-oblivious design, persistence, concurrency, emerging structures, design patterns, and the practical business of choosing and debugging.

Volume IV: Competitive Programming and Research-Grade Structures The contest arsenal and the research frontier: segment trees with lazy propagation, heavy-light decomposition, link-cut trees, suffix automata, wavelet trees, succinct representations, FM-indexes, and fractional cascading.

Volume V: Network and System Design Data Structures Distributed hash tables, consistent hashing, CRDTs, consensus, routing tables, storage engines, rate limiters, inverted indexes, and case studies of Spanner, Dynamo, Kafka, Delta Lake, and Cloudflare’s edge.

Using this book

Every page has a search (press s), a print/PDF view (the printer icon), and an edit link to its source on GitHub. Corrections are welcome: see the contributing guide.

The prose is CC BY 4.0 and the code is MIT. Use it in your class, your study group, or your blog.

Start with the Preface, or jump straight to Chapter 1.

Preface

Everything Data Structures, by Ngoc Anh Khoa Doan, with the editorial help of Claude.

This book represents a monumental effort to document every significant data structure known to computer science, from the most elementary building blocks to the most sophisticated, specialized, and esoteric structures employed in cutting-edge research and industrial applications. The study of data structures is not merely an academic exercise, it is the foundation upon which all efficient software is built.

The history of data structures mirrors the evolution of computing itself. When John von Neumann conceived the stored-program computer in the 1940s, programmers worked directly with raw memory addresses. As programs grew more complex, the need for organization became apparent. The 1960s and 1970s saw the emergence of fundamental structures, arrays, linked lists, trees, alongside the theoretical frameworks to analyze them. The work of Donald Knuth in “The Art of Computer Programming” codified these structures and established the mathematical rigor that remains the standard today.

The subsequent decades brought new challenges: massive databases requiring disk-optimized structures, distributed systems demanding new approaches to consistency, and probabilistic methods that traded absolute correctness for space efficiency. Each chapter of this book tells the story of how data structures evolved to meet these challenges.

This book is organized into five volumes. Volume I establishes the mathematical foundations and covers the fundamental structures every programmer must master. Volume II explores graphs, hash tables, and string structures. Volume III examines modern developments including probabilistic, spatial, persistent, and concurrent structures. Volume IV covers competitive-programming and research-grade structures. Volume V shows how network topologies and system designs are themselves data structures composed at scale.

Whether you are a student encountering data structures for the first time, a practitioner seeking to optimize a production system, or a researcher exploring the frontiers of the field, this book aims to be your definitive reference.

Ngoc Anh Khoa Doan

Volume I: Foundations and Fundamentals

Part 1: Mathematical Foundations

• Chapter 1: The Philosophy and Mathematics of Data Structures
• Chapter 2: Primitive Types and Memory Organization

Part 2: Fundamental Linear Structures

• Chapter 3: Arrays—The Foundation of Contiguous Storage
• Chapter 4: Linked Lists—The Art of Distributed Storage
• Chapter 5: Stacks and Queues—Ordered Access Patterns

Part 3: Hierarchical Structures, Trees

• Chapter 6: Tree Fundamentals and Binary Trees
• Chapter 7: Binary Search Trees
• Chapter 8: Self-Balancing Trees
• Chapter 9: Heaps and Priority Queues
• Chapter 10: Multiway Search Trees and B-Trees

Chapter 1: The Philosophy and Mathematics of Data Structures

1.1 What Data Structures Really Are

A data structure is a systematic organization of data that enables efficient access and modification. But this dry definition obscures what data structures truly represent: the art of translating abstract relationships into concrete, manipulable forms. Every program is a model of some reality, and data structures are the vocabulary of that model.

Consider the challenge of representing a family tree. You could use an array, storing each person and a numeric index indicating their parent. This works, but querying becomes cumbersome, what is the average age of all grandchildren of a particular person? The structure constrains the operations you can perform efficiently.

Now consider representing the same family tree as a tree structure, where each node contains a person’s data and pointers to their children. Suddenly, the query becomes trivial: traverse from the given person to their children, then to their grandchildren, computing ages along the way. The data structure has made the problem tractable.

This relationship between structure and operation lies at the heart of data structure design. There is no universally “best” data structure; there are only structures that are better or worse for particular access patterns, modification patterns, and constraints.

1.2 The Abrahamic Truth: No Free Lunch

The No Free Lunch Theorem, originally formulated in optimization, has profound implications for data structure design. Simply stated: no data structure can excel at all operations. If you want fast search, you sacrifice fast insertion (or vice versa). If you want minimal memory, you sacrifice speed. If you want deterministic worst-case performance, you sacrifice average-case performance.

This fundamental trade-off is why we have so many data structures. Each structure represents a different point in the multi-dimensional space of possible trade-offs. The practitioner’s art lies in understanding which trade-offs matter for their specific application.

Let us enumerate the dimensions of this trade-off space:

Time Complexity Dimensions:

• Search time (point queries)
• Insertion time
• Deletion time
• Range query time
• Successor/predecessor time
• Maximum/minimum access time
• Traversal time

Space Complexity Dimensions:

• Raw space usage
• Overhead per element
• Space amplification under modification
• Fragmentation behavior

Operational Dimensions:

• Sequential access patterns
• Random access patterns
• Bulk operations
• Persistence and versioning

Implementation Dimensions:

• Complexity of implementation
• Debugging difficulty
• Cache behavior
• Thread safety

1.3 Asymptotic Analysis: The Language of Efficiency

Computer scientists use asymptotic notation to describe the behavior of algorithms and data structures as input sizes grow arbitrarily large. This approach abstracts away machine-specific constants and focuses on the fundamental growth rate.

Big-O Notation: Upper Bounds

O(f(n)) describes an upper bound on running time. f(n) = O(g(n)) means that f grows no faster than some constant multiple of g for sufficiently large n. Formally:

∃ c > 0, ∃ n₀ > 0, such that ∀ n ≥ n₀: 0 ≤ f(n) ≤ c·g(n)

When we say a hash table has O(1) lookup, we mean the lookup time is bounded by a constant, regardless of how many elements are stored. This is an upper bound, we’re saying lookup will never be worse than constant time.

Big-Omega Notation: Lower Bounds

Ω(f(n)) describes a lower bound. f(n) = Ω(g(n)) means f grows at least as fast as g for sufficiently large n. Formally:

∃ c > 0, ∃ n₀ > 0, such that ∀ n ≥ n₀: 0 ≤ c·g(n) ≤ f(n)

When we say comparison-based sorting requires Ω(n log n), we’re establishing that no comparison sort can do better in the worst case. This is a fundamental lower bound.

Theta Notation: Tight Bounds

Θ(f(n)) indicates both upper and lower bounds. f(n) = Θ(g(n)) means f grows asymptotically the same rate as g. Formally:

∃ c₁ > 0, ∃ c₂ > 0, ∃ n₀ > 0, such that ∀ n ≥ n₀: c₁·g(n) ≤ f(n) ≤ c₂·g(n)

When we say mergesort is Θ(n log n), we mean this is both an upper bound (it won’t be slower) and a lower bound (you can’t do better).

Little-o and Little-Omega: Asymptotic Inequalities

o(f(n)) means “grows strictly slower than f(n)”: lim(n→∞) g(n)/f(n) = 0

ω(f(n)) means “grows strictly faster than f(n)”: lim(n→∞) g(n)/f(n) = ∞

1.4 Common Complexity Classes

Understanding the practical implications of different complexity classes is essential:

Constant Time: O(1)

• Array indexed access
• Hash table lookup (with good hash function)
• Bit operations
• Stack push/pop
• Queue enqueue/dequeue

The signature of O(1) is “doesn’t depend on n.” Whether you have 10 elements or 10 million, the operation takes the same time.

Logarithmic Time: O(log n)

• Binary search in sorted array
• Balanced tree operations (BST, AVL, Red-Black, B-Tree)
• Skip list operations
• Binary search in balanced tree
• van Emde Boas tree operations

Logarithmic growth is remarkably slow. Even at n = 1 billion, log₂(n) ≈ 30. This means an O(log n) operation takes at most about 30 steps for a billion elements.

Linear Time: O(n)

• Sequential scan of array
• Linked list traversal
• Breadth-first or depth-first graph search
• Counting sort (under constraints)
• Hash table operations with poor hash function

Linearithmic Time: O(n log n)

• Comparison-based sorting (merge sort, heap sort, quicksort average case)
• Building a heap
• Balanced tree operations if rebuilding required

Polynomial Time: O(n^k)

• Simple matrix operations
• Naive string matching (O(nm))
• Certain dynamic programming solutions

Exponential Time: O(2^n)

• Generating all subsets
• Naive solutions to NP-complete problems
• Recursive Fibonacci without memoization

Factorial Time: O(n!)

• Generating all permutations
• Traveling salesman brute force
• Certain combinatorial problems

1.5 Amortized Analysis: Averaging the Worst

Sometimes we care less about individual operation cost and more about total cost over a sequence of operations. Amortized analysis computes the average cost per operation over a worst-case sequence.

Consider a dynamic array (like Python’s list or Java’s ArrayList). When it fills, it doubles its capacity and copies all elements. This copy costs O(n), which seems expensive. However, this expensive operation happens only rarely, specifically, when the array size is a power of 2.

Over n insert operations, the total cost is: n + 1 + 2 + 4 + 8 + … + n ≤ 2n

So the amortized cost per insert is O(2n/n) = O(1). Each individual insert is O(1) on average, even though occasional inserts are O(n).

Three techniques for amortized analysis exist:

Aggregate Analysis: Simply sum the costs of all operations and divide by n. If the total cost of any sequence of n operations is T(n), the amortized cost is T(n)/n.

Accounting Method: Assign different charges to different operations. Some operations are charged more than they cost; the excess is stored as “credit” and used to pay for operations that cost more than they were charged. The total credit never goes negative.

For dynamic arrays, we might charge 3 units for each insert: 1 unit for the immediate insert, 1 unit for future copying, and 1 unit for the eventual deallocation.

Potential Method: Define a potential function Φ that maps data structure states to non-negative numbers. The amortized cost of an operation is the real cost plus the change in potential:

amortized_cost = real_cost + ΔΦ

If Φ is always non-negative and Φ(start) = 0, the total amortized cost is an upper bound on total real cost.

For a dynamic array, define Φ = 2n - m, where n is the current size and m is the capacity. When the array is full, Φ = 0. When half-full, Φ = n (maximum).

1.6 The RAM Model and Real Costs

Theoretical analysis assumes the Random Access Machine (RAM) model, where:

• All operations (arithmetic, memory access) take constant time
• Memory is unbounded
• No cache effects

Reality is more complex. Modern computers have hierarchical memory:

• L1 cache: ~32KB, ~1ns access
• L2 cache: ~256KB, ~4ns access
• L3 cache: ~8MB, ~15ns access
• Main memory: ~64GB, ~100ns access
• SSD: ~100GB, ~100μs access
• Hard disk: ~TB, ~10ms access

A structure that minimizes main memory accesses may perform better than one with theoretically superior asymptotic complexity. This is why:

• Arrays often outperform linked lists (cache-friendly sequential access)
• B-trees outperform binary trees for database indexes (fewer disk accesses)
• Cache-oblivious structures adapt to all levels automatically

1.7 Lower Bounds: How Low Can You Go?

A lower bound establishes that no algorithm can do better than a certain complexity. Proving lower bounds is often more difficult than proving upper bounds.

Comparison-Based Sorting: Ω(n log n) The proof uses a decision tree argument. Any comparison sort can be represented as a binary decision tree, where each internal node represents a comparison and each leaf represents a final ordering. A binary tree with L leaves must have height at least log₂ L. Since there are n! possible orderings, the tree needs at least n! leaves, requiring height at least log₂(n!) = Ω(n log n).

Static Dictionary: Ω(log n) For static sets (no insertions or deletions), the cell probe model proves that any data structure answering membership queries needs Ω(log n) time if it uses O(n) space. This is why balanced binary trees are optimal for static ordered sets.

Dynamic Dictionary: Ω(1) Surprisingly, with amortization or randomization, we can achieve O(1) expected time for dynamic sets. Hash tables achieve this, though at the cost of potential false positives and worst-case degradation.

1.8 References for Further Study

The mathematical foundations of data structures draw from several disciplines:

• Combinatorics: Counting arguments in decision tree lower bounds
• Information Theory: Entropy bounds on compression and encoding
• Algebra: Group theory in symmetric structures, polynomial methods
• Probability: Randomization in skip lists, hashing, and probabilistic data structures
• Algebraic Topology: Recent connections to persistent homology and spatial data structures

Where this connects

• Chapter 22: Practical Considerations. How these bounds translate into actual decisions
• Chapter 16: External Memory and Cache-Oblivious Structures. Why the RAM model this chapter assumes is not how real hardware behaves

Chapter 2: Primitive Types and Memory Organization

2.1 The Building Blocks: Primitive Data Types

Every data structure ultimately decomposes into primitive types, fundamental units that the hardware directly supports. Understanding these types, their properties, and their cost is essential for effective data structure design.

Boolean Type

The boolean type represents truth values. While conceptually just two states (true and false), implementation varies:

• C/C++: Typically stored as one byte, with 0 representing false and 1 representing true
• Java: Strictly one bit conceptually, but one byte in arrays
• Python: Full objects with True/False keywords
• Hardware: Boolean operations are fundamental CPU operations

Boolean operations (AND, OR, NOT, XOR) are typically constant-time hardware operations. However, boolean arrays (bitsets) can be significantly more space-efficient than boolean objects.

Integer Types

Integer types represent whole numbers with various ranges:

The “long” type illustrates how naming varies across languages:

• Java: long is always 64 bits
• C/C++: long may be 32 or 64 bits depending on platform
• Python: integers are arbitrary precision (bignums)

Integer overflow is a subtle source of bugs. In two’s complement representation (virtually universal), adding 1 to the maximum value wraps to the minimum value. This has caused real-world bugs:

• Ariane 5 rocket explosion (1996): 64-bit to 16-bit conversion overflow
• Xbox 360 “red ring of death”: Integer overflow in timer
• Knights of the Round Table bug: Division by zero from overflow

Floating-Point Types

Floating-point numbers represent real numbers with limited precision:

IEEE 754 standardizes floating-point representation:

• 1 bit: sign
• 8 bits: exponent (biased)
• 23 bits: mantissa (fraction)

This gives the familiar scientific notation: (-1)^sign × 1.mantissa × 2^exponent

Key considerations for data structures:

• Floating-point equality is problematic (0.1 + 0.2 ≠ 0.3)
• NaN (Not a Number) propagates through operations
• Infinity arithmetic has special rules
• Denormalized numbers provide gradual underflow

Character Types

Characters represent text elements:

• ASCII: 7 bits (128 characters), includes control characters and basic Latin
• Extended ASCII: 8 bits (256 characters), various ISO-8859 pages
• Unicode: Variable-width, includes virtually all writing systems
• UTF-8: Variable 1-4 bytes, ASCII-compatible, dominant on the web
• UTF-16: 2 or 4 bytes, used in Java, Windows, JavaScript strings

The choice of character encoding affects string data structure design significantly.

2.2 Memory Organization and Addressing

Understanding how memory is organized helps in designing efficient data structures.

Byte-Addressable Memory

Modern computers are byte-addressable: each byte has a unique address. Larger types (ints, floats) occupy multiple consecutive bytes.

The endianness question: which byte is stored at the lowest address?

• Little-endian (Intel, ARM): Least significant byte first
  • Value 0x01234567 stored as 67 45 23 01 at addresses 0,1,2,3
• Big-endian (Network order, some RISC): Most significant byte first
  • Value 0x01234567 stored as 01 23 45 67 at addresses 0,1,2,3

Mixed-endian architectures exist but are rare. The choice affects:

• Network protocol compatibility
• Binary file formats
• Debugging (hex dumps appear “reversed” on little-endian)
• Type punning through memory

Alignment and Padding

Modern CPUs are optimized to access memory at aligned addresses. A 4-byte int should be at an address divisible by 4; an 8-byte double should be at an address divisible by 8.

When structures contain multiple types, compilers insert padding to maintain alignment:

struct Example {
    char a;      // 1 byte, offset 0
    // 3 bytes padding
    int b;       // 4 bytes, offset 4
    char c;      // 1 byte, offset 8
    // 7 bytes padding (typically)
};
// sizeof(Example) = 16 (on 64-bit system)

The #pragma pack directive and attribute((packed)) can eliminate padding, but at a cost: unaligned accesses may be slower or even cause hardware exceptions on some architectures.

Stack vs. Heap Memory

Two primary memory regions exist for dynamic data:

Stack:

• Automatic memory management
• Fast allocation (just move stack pointer)
• Automatic deallocation (scope-based)
• Limited size (typically 1-8MB)
• Perfect for small, short-lived objects
• Local variables, function parameters, return addresses

Heap:

• Manual management (malloc/free, new/delete)
• Slower allocation (search for free block)
• Manual or garbage-collected deallocation
• Large size (limited by physical + virtual memory)
• Good for large or long-lived objects
• Dynamic data structures

The stack’s speed comes from its simplicity: allocation is decrementing a pointer, deallocation is incrementing. However, the stack cannot grow indefinitely, and objects must have known lifetimes.

2.3 Pointers and References

Pointers are variables that store memory addresses. They are the fundamental mechanism for building dynamic, linked data structures.

Pointer Basics

int x = 42;
int *p = &x;     // p stores address of x
int y = *p;      // y = 42 (dereference p)
*p = 100;        // x = 100 (modify through pointer)

The pointer-to-pointer pattern allows modification of pointers themselves:

void insert(Node **head, int value) {
    Node *new = malloc(sizeof(Node));
    new->data = value;
    new->next = *head;
    *head = new;
}

Pointer Arithmetic

In C and C++, pointers can be incremented and decremented:

int arr[5] = {10, 20, 30, 40, 50};
int *p = arr;        // Points to arr[0]
p++;                 // Points to arr[1]
int val = *(p + 2); // Value at arr[3] = 40

This arithmetic is scaled by the size of the pointed-to type. p++ moves by sizeof(*p) bytes.

Null Pointers

The null pointer represents “points to nothing.” Its representation is implementation-defined but is typically address 0. Dereferencing null causes undefined behavior (usually a crash).

Modern C++ prefers nullptr over NULL (which is just 0, potentially ambiguous with integer 0). Java and Python use null or None for reference types.

Reference Types

References (C++, and analogous concepts in other languages) are aliases to existing objects:

int x = 42;
int &r = x;  // r is another name for x
r = 100;     // x = 100

Unlike pointers:

• References must be initialized
• References cannot be reseated
• References cannot be null
• Access syntax is cleaner (no dereference operator)

References provide the safety of not being null while maintaining the efficiency of pointer-based indirection.

2.4 Records and Structures

Records (called structs in C, classes in object-oriented languages) group related fields:

struct Student {
    char name[50];
    int id;
    float gpa;
    struct Student *advisor;  // Pointer for linked structures
};

Memory Layout

Structures are laid out sequentially in memory, with padding as needed for alignment. The programmer can control layout with pragmas or attributes:

// Force tight packing (no padding)
struct PackedStudent {
    char name[50];
    int id;
    float gpa;
} __attribute__((packed));

Bit Fields

C and C++ allow specifying field widths in bits:

struct Flags {
    unsigned int is_signed : 1;
    unsigned int is_array  : 1;
    unsigned int size      : 6;  // 0-63
};

Bit fields pack multiple boolean or small-integer fields into single bytes. However, they have drawbacks:

• No addressable pointer to a bit field
• Layout is implementation-defined
• May be slower to access than full bytes

2.5 Type Systems and Generic Programming

Modern languages provide mechanisms for writing data structures that work with arbitrary types.

Templates (C++)

template<typename T>
class Stack {
    std::vector<T> data;
public:
    void push(const T& item) { data.push_back(item); }
    T pop() { T item = data.back(); data.pop_back(); return item; }
};

Templates are resolved at compile-time, producing zero runtime overhead for type checking.

Generics (Java, C#)

public class Stack<T> {
    private ArrayList<T> data = new ArrayList<>();
    public void push(T item) { data.add(item); }
    public T pop() { return data.remove(data.size() - 1); }
}

Java generics use type erasure, they exist only at compile time, with runtime types being just Object.

Python Duck Typing

Python uses dynamic typing with duck typing (“if it walks like a duck…”):

class Stack:
    def __init__(self):
        self.data = []
    def push(self, item):
        self.data.append(item)
    def pop(self):
        return self.data.pop()

Any object with append() and pop() works with this Stack. This flexibility comes at the cost of runtime type checking.

Where this connects

• Chapter 3: Arrays—The Foundation of Contiguous Storage. The first structure built directly on this memory model
• Chapter 16: External Memory and Cache-Oblivious Structures. What the memory hierarchy does to these assumptions

Chapter 3: Arrays—The Foundation of Contiguous Storage

3.1 The Array Concept

An array is a contiguous block of memory containing elements of identical type. This simplicity is its power: given the address of the first element and an index, we can compute the address of any element in constant time.

The address formula: address(arr[i]) = base_address + i × element_size

This direct addressing is why arrays provide O(1) indexed access. No traversal, no searching, the location is known.

3.2 One-Dimensional Arrays

The simplest array form stores elements in a single row:

Memory Layout for int array[5] = {10, 20, 30, 40, 50}:

Address:  0x1000  0x1004  0x1008  0x100C  0x1010
         ┌───────┬───────┬───────┬───────┬───────┐
Index:   │   0   │   1   │   2   │   3   │   4   │
         ├───────┼───────┼───────┼───────┼───────┤
Value:   │  10   │  20   │  30   │  40   │  50   │
         └───────┴───────┴───────┴───────┴───────┘
         ↑
       base_address = 0x1000

The power of this layout is cache prefetching. When you access arr[0], the CPU typically loads not just that element but a cache line (often 64 bytes). This means arr[1], arr[2], arr[3]… are likely already in cache. Sequential array access is extremely fast.

3.3 Multi-Dimensional Arrays

Multi-dimensional arrays store data in grid or higher-dimensional tensor form.

Row-Major Order (C, C++, Python)

Elements stored row-by-row:

int matrix[3][4] = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12}
};

Address formula: address(matrix[i][j]) = base + (i × 4 + j) × element_size

Column-Major Order (Fortran, MATLAB, R)

Elements stored column-by-column:

Address formula: address(matrix[i][j]) = base + (j × 3 + i) × element_size

Arrays of Arrays (Jagged Arrays)

Instead of contiguous memory, each row/column is a separate array:

vector<vector<int>> matrix(3);
for (int i = 0; i < 3; i++)
    matrix[i] = vector<int>(4);  // Each row independently allocated

This allows irregular shapes but loses cache locality and complicates memory management.

3.4 Dynamic Arrays

Fixed-size arrays require size at compile time. Dynamic arrays resize as needed.

The Resize Strategy

When capacity is exhausted:

1. Allocate new, larger array (typically 2× current size)
2. Copy all elements to new array
3. Deallocate old array

Initial array (capacity 4):
┌────┬────┬────┬────┐
│ 1  │ 2  │ 3  │ 4  │
└────┴────┴────┴────┘

After inserting 5 (capacity exceeded):
┌────┬────┬────┬────┬────┬────┬────┬────┐
│ 1  │ 2  │ 3  │ 4  │ 5  │    │    │    │
└────┴────┴────┴────┴────┴────┴────┴────┘
      (old array, now freed)

Amortized Analysis of Dynamic Arrays

With capacity doubling:

• Insert 1: Copy 1 element
• Insert 2: Copy 2 elements
• Insert 4: Copy 4 elements
• Insert 8: Copy 8 elements
• …
• Insert 2^k: Copy 2^k elements

Total copies for n insertions: 1 + 2 + 4 + … + 2^k where 2^k ≥ n ≤ 2 × 2^k (geometric series) ≤ 2n (since 2^k ≤ 2n)

Amortized per insertion: O(2n/n) = O(1)

Implementation in Various Languages

C++ vector:

vector<int> v;
for (int i = 0; i < 1000; i++) {
    v.push_back(i);  // Amortized O(1)
}

Python list:

lst = []
for i in range(1000):
    lst.append(i)  # Amortized O(1)

Java ArrayList:

ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
    list.add(i);  // Amortized O(1)
}

Go slices:

slice := make([]int, 0)
for i := 0; i < 1000; i++ {
    slice = append(slice, i)  // Amortized O(1)
}

3.5 Bit Arrays and Bitsets

When each element needs only one bit, bit arrays provide massive space savings.

Operations on Bit Arrays

// Set bit i to 1
bits[i / 8] |= (1 << (i % 8));

// Clear bit i to 0
bits[i / 8] &= ~(1 << (i % 8));

// Test bit i
if (bits[i / 8] & (1 << (i % 8))) { ... }

Popular Bitset Implementations

Applications of Bit Arrays

Bloom Filters: Multiple hash functions map elements to bits Sets: Efficient set operations (union, intersection, difference) Sieve of Eratosthenes: Finding primes Computer Graphics: Pixel masks, sprites Networking: IP packet filters, routing tables Database: Bitmap indexes

3.6 Array Variants for Specific Purposes

Circular Buffers

A circular buffer wraps around at the end, ideal for queues:

     front                     rear
       │                        │
       ▼                        ▼
┌────┬────┬────┬────┬────┬────┬────┬────┐
│ 30 │ 40 │ 50 │ -- │ -- │ -- │ 10 │ 20 │
└────┴────┴────┴────┴────┴────┴────┴────┘
                ▲                        ▲
              empty                    full
             slots                    slots

Elegant implementation using modulo arithmetic:

• enqueue: rear = (rear + 1) % capacity
• dequeue: front = (front + 1) % capacity

Difference Arrays

Store the difference between consecutive elements:

Original:     [10, 20, 25, 30, 35]
Difference:   [10, 10, 5, 5, 5]

Range update [1,3) += 3:
Original becomes: [10, 23, 28, 33, 35]
Difference becomes: [10, 13, 5, 5, 5]

Range updates become O(1); original array reconstruction is O(n).

Sparse Arrays

For arrays with mostly default values:

struct SparseEntry {
    int index;
    value_type value;
};
vector<SparseEntry> sparse;

Only non-default values stored, with index for position.

3.7 Performance Characteristics

3.8 Real-World Applications

Database Systems: Column stores use columnar arrays for analytical queries Scientific Computing: Dense matrix operations (BLAS, LAPACK) Image Processing: Pixel arrays with convolution operations Signal Processing: Sample buffers with circular buffer patterns Compilers: Symbol tables using open addressing Networking: Packet buffers, ring buffers in device drivers

3.9 Historical Context

The array concept predates electronic computers. In mathematics, matrices and vectors have been studied for centuries. The FORTRAN language (1957) introduced multi-dimensional arrays as a first-class concept, heavily influencing scientific computing.

The dynamic array (vector) concept emerged with languages supporting heap allocation. The Ada language (1983) provided array slicing; modern languages provide richer array operations. The Ruby language introduced the “push” and “pop” terminology that spread to Python and JavaScript.

Where this connects

• Chapter 4: Linked Lists—The Art of Distributed Storage. The same sequence problem solved with pointers instead of contiguity
• Chapter 16: External Memory and Cache-Oblivious Structures. Why contiguous layout beats pointer-chasing by more than the asymptotics suggest

Chapter 4: Linked Lists—The Art of Distributed Storage

4.1 The Linked List Philosophy

Where arrays store elements contiguously, linked lists store elements anywhere in memory, connecting them via pointers. This distribution enables efficient insertion and deletion at arbitrary positions, at the cost of no direct indexing.

The fundamental trade-off:

• Array: Fast access, slow modification
• Linked list: Slow access (must traverse), fast modification

4.2 Singly Linked Lists

Each node contains data and a pointer to the next node:

struct Node {
    element_type data;
    struct Node *next;
};

HEAD                                                            NULL
 │                                                               │
 ▼                                                               ▼
┌────────┬───────┐    ┌────────┬───────┐    ┌────────┬───────┐    ┌────────┬───────┐
│ Data: A│ Next: ──────→│ Data: B│ Next: ──────→│ Data: C│ Next: ──────→│ Data: D│ Next: │
│       │       │    │       │       │    │       │       │    │       │       │
└────────┴───────┘    └────────┴───────┘    └────────┴───────┘    └────────┴───────┘

Core Operations

Insertion at Head:

void insert_head(Node **head_ref, element_type data) {
    Node *new_node = malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = *head_ref;
    *head_ref = new_node;
}

Time: O(1)

Insertion at Position:

void insert_after(Node *prev_node, element_type data) {
    if (prev_node == NULL) return;
    Node *new_node = malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = prev_node->next;
    prev_node->next = new_node;
}

Time: O(1) given position, O(n) to find position

Deletion:

void delete_node(Node **head_ref, element_type key) {
    Node *temp = *head_ref;
    Node *prev = NULL;

    if (temp != NULL && temp->data == key) {
        *head_ref = temp->next;
        free(temp);
        return;
    }

    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) return;
    prev->next = temp->next;
    free(temp);
}

Time: O(n) worst case to find, O(1) to delete

Search:

Node* search(Node *head, element_type key) {
    Node *current = head;
    while (current != NULL) {
        if (current->data == key) return current;
        current = current->next;
    }
    return NULL;
}

Time: O(n)

4.3 Doubly Linked Lists

Each node contains data, a pointer to the next node, and a pointer to the previous node:

struct DNode {
    element_type data;
    struct DNode *next;
    struct DNode *prev;
};

 NULL                                                           NULL
  │                                                             │
  │     ┌────────┬────────┬───────┐    ┌────────┬────────┬───────┐
  │     │  Prev  │  Data  │  Next │    │  Prev  │  Data  │  Next │
  └────→│  NULL  │   A    │   ────┼───→│   ────┤   B    │   ────┼───→ NULL
        └────────┴────────┴───────┘    └────────┴────────┴───────┘

Advantages Over Singly Linked Lists

• Traversal in both directions
• O(1) deletion given a node pointer (no need to find previous)
• O(1) insertion before a given node
• Better for implementing deques

Implementation

Deletion (given node pointer):

void delete_node(DNode *node) {
    if (node->prev != NULL)
        node->prev->next = node->next;
    else
        head = node->next;  // Was head

    if (node->next != NULL)
        node->next->prev = node->prev;

    free(node);
}

Insertion Before:

void insert_before(DNode **head, DNode *next_node, element_type data) {
    DNode *new_node = malloc(sizeof(DNode));
    new_node->data = data;
    new_node->next = next_node;
    new_node->prev = next_node->prev;

    if (next_node->prev != NULL)
        next_node->prev->next = new_node;
    else
        *head = new_node;  // Was head

    next_node->prev = new_node;
}

4.4 Circular Linked Lists

The last node’s next pointer points back to the first node (or for doubly, the first node’s prev points to the last).

Circular Singly:
┌────────┬───────┐    ┌────────┬───────┐    ┌────────┬───────┐
│ Data: A│ Next: ────┼─→│ Data: B│ Next: ────┼─→│ Data: C│ Next: ────┐
│       │       │    │       │       │    │       │       │    │
└────────┴───────┘    └────────┴───────┘    └────────┴───────┘    │
    ↑                                                              │
    └──────────────────────────────────────────────────────────────┘

Circular Doubly:
NULL ◄────────────────────────────────────────────────────────────────► NULL
  │     ┌────────┬────────┬───────┐    ┌────────┬────────┬───────┐    │
  │     │  Prev  │  Data  │  Next │    │  Prev  │  Data  │  Next │    │
  └────→│   ●    │   A    │   ────┼───→│   ────┤   B    │   ────┼───→│
        └────────┴────────┴───────┘    └────────┴────────┴───────┘    │
            ▲                                                              │
            └──────────────────────────────────────────────────────────────┘

Applications

Round-Robin Scheduling: Each process gets equal CPU time Circular Buffers: Efficient producer-consumer patterns Music Playlists: Seamless looping Undo/Redo History: Recent actions cycle through

4.5 The Sentinel’s Guard

Sentinel nodes (dummy nodes) simplify boundary conditions by eliminating null checks:

// Without sentinel - careful null handling
void insert_first(Node **head, element_type data) {
    Node *new_node = malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = *head;
    *head = new_node;
}

// With sentinel - cleaner code
void insert_after(Node *prev, element_type data) {
    Node *new_node = malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = prev->next;
    prev->next = new_node;
}

Common sentinel patterns:

• Head sentinel: Dummy node before first real element
• Tail sentinel: Dummy node after last real element
• Both: Simplifies all operations to “insert after/before”

4.6 XOR Linked Lists

XOR linked lists store only the XOR of consecutive node addresses, saving space:

struct XorNode {
    element_type data;
    uintptr_t npx;  // XOR of previous and next pointers
};

The trick: to traverse, you need the previous node’s address to XOR with npx to get the next node’s address.

Traversal:

XorNode* prev = NULL;
XorNode* current = head;
XorNode* next;

while (current != NULL) {
    printf("%d ", current->data);
    next = (XorNode*)((uintptr_t)prev ^ current->npx);
    prev = current;
    current = next;
}

Advantages: 50% space reduction for pointers Disadvantages: Can’t traverse backwards without storing previous pointer, debugging is harder

4.7 Unrolled Linked Lists

Each node contains multiple elements in a small array:

┌────────┬───────┐    ┌────────┬───────┐
│ 4 │ A │ B │ C │ ──┼─→│ 2 │ D │ E │ ──┼─→ NULL
│ elements│       │    │ elements│       │
└────────┴───────┘    └────────┴───────┘

Advantages:

• Better cache locality (multiple elements per node)
• Less pointer overhead
• Faster iteration
• Still O(1) insertion at arbitrary positions (with smaller shift)

Used in: CD-ROM filesystems (directory entries), Kyoto Cabinet database, Lua’s table implementation

4.8 Performance Characteristics

*With tail pointer or other augmentation

4.9 When to Use Linked Lists

Use Linked Lists When:

• Frequent insertions/deletions at arbitrary positions
• Size is unknown or highly variable
• Memory is fragmented
• No random access needed
• Implementing other structures (stacks, queues)

Avoid Linked Lists When:

• Frequent random access (use arrays)
• Cache performance matters (use arrays or unrolled)
• Memory overhead is a concern (pointers take space)
• Simple iteration is the primary operation (vectors are faster)

4.10 Real-World Applications

Operating Systems:

• Process scheduling queues
• Memory allocation (free lists)
• File system directory entries
• Driver device queues

Databases:

• B-tree leaf nodes (doubly linked for range scans)
• Transaction logs
• Lock chains

Compilers:

• Symbol tables (hash table + linked list chaining)
• Abstract syntax trees (child lists)

Applications:

• Music playlists (doubly linked for bidirectional navigation)
• Browser history (back/forward buttons)
• Undo/redo functionality
• Text buffer implementation (lines as linked list)

4.11 Historical Context

The linked list was invented by Allen Newell, Cliff Shaw, and Herbert A. Simon at RAND Corporation in 1956, as part of the development of the Information Processing Language (IPL), the first AI programming language.

John McCarthy introduced the concept of “linked list” and “car/cdr” (contents of address/register and contents of decrement/register) in LISP (1958), where lists are the fundamental data structure.

The doubly linked list emerged later as programmers recognized the need for bidirectional traversal.

Where this connects

• Chapter 3: Arrays—The Foundation of Contiguous Storage. The contiguous alternative, and when it wins
• Chapter 18: Concurrent Data Structures. Why lock-free versions of these structures are hard

Chapter 5: Stacks and Queues—Ordered Access Patterns

5.1 Stacks: The LIFO Principle

A stack is an ADT supporting two primary operations: push (add to top) and pop (remove from top). The last element pushed is the first to be popped, Last In, First Out.

Mental Model: A stack of plates in a cafeteria. You add plates to the top, and you take plates from the top. You never reach into the middle of the stack.

    ┌─────────┐
    │   TOP   │  ← Push(4), Pop() returns 4
    ├─────────┤
    │    3    │
    ├─────────┤
    │    2    │
    ├─────────┤
    │    1    │
    └─────────┘
        BOTTOM

5.2 Stack Implementation

Array-Based Stack

#define MAX_SIZE 1000

typedef struct {
    int top;
    element_type data[MAX_SIZE];
} Stack;

void init(Stack *s) { s->top = -1; }

int is_empty(Stack *s) { return s->top == -1; }
int is_full(Stack *s) { return s->top == MAX_SIZE - 1; }

void push(Stack *s, element_type x) {
    if (is_full(s)) { /* handle overflow */ }
    s->data[++s->top] = x;
}

element_type pop(Stack *s) {
    if (is_empty(s)) { /* handle underflow */ }
    return s->data[s->top--];
}

element_type peek(Stack *s) {
    if (is_empty(s)) { /* handle empty */ }
    return s->data[s->top];
}

Linked List-Based Stack

typedef struct StackNode {
    element_type data;
    struct StackNode *next;
} StackNode;

StackNode *top = NULL;

void push(element_type x) {
    StackNode *node = malloc(sizeof(StackNode));
    node->data = x;
    node->next = top;
    top = node;
}

element_type pop() {
    if (top == NULL) { /* handle underflow */ }
    StackNode *tmp = top;
    element_type val = tmp->data;
    top = top->next;
    free(tmp);
    return val;
}

5.3 Stack Applications

Function Call Stack

The most important use of stacks: managing function calls. Each function call pushes a stack frame containing:

• Return address
• Parameters
• Local variables
• Saved registers

int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

fact(4):
fact(4) calls fact(3)
    fact(3) calls fact(2)
        fact(2) calls fact(1)
            fact(1) returns 1
        fact(2) returns 2 * 1 = 2
    fact(3) returns 3 * 2 = 6
fact(4) returns 4 * 6 = 24

Stack growth:
┌──────────┐
│ fact(1)  │ ← Returns, stack shrinks
├──────────┤
│ fact(2)  │
├──────────┤
│ fact(3)  │
├──────────┤
│ fact(4)  │ ← Called first
└──────────┘

Stack overflow occurs when the call stack exceeds its allocated size, often due to infinite recursion.

Expression Evaluation

Stacks enable evaluation of expressions in postfix (Reverse Polish) notation:

Infix:     3 + 4 * 2 / (1 - 5)
Postfix:   3 4 2 * 1 5 - / +

Evaluation:
Push 3
Push 4
Push 2
Multiply: pop 2, pop 4, push 8      Stack: [3, 8]
Push 1
Push 5
Subtract: pop 5, pop 1, push -4    Stack: [3, 8, -4]
Divide: pop -4, pop 8, push -2     Stack: [3, -2]
Add: pop -2, pop 3, push 1        Stack: [1]
Result: 1

Infix to Postfix Conversion (Shunting-yard algorithm):

• Numbers: output immediately
• Operators: pop operators with higher precedence, then push
• Left parenthesis: push
• Right parenthesis: pop until left parenthesis

Parentheses Matching

int is_balanced(char *expr) {
    Stack s;
    init(&s);

    while (*expr) {
        if (*expr == '(' || *expr == '[' || *expr == '{') {
            push(&s, *expr);
        } else if (*expr == ')' || *expr == ']' || *expr == '}') {
            if (is_empty(&s)) return 0;
            char top = pop(&s);
            if ((top == '(' && *expr != ')') ||
                (top == '[' && *expr != ']') ||
                (top == '{' && *expr != '}')) {
                return 0;
            }
        }
        expr++;
    }
    return is_empty(&s);
}

Undo/Redo Systems

Applications maintain two stacks: one for undo, one for redo:

typedef struct {
    Stack undo;
    Stack redo;
    Document doc;
} Editor;

void do_action(Editor *ed, Action action) {
    push(&ed->undo, save_state(&ed->doc));
    apply(action, &ed->doc);
    clear_stack(&ed->redo);
}

void undo(Editor *ed) {
    if (is_empty(&ed->undo)) return;
    State *s = pop(&ed->undo);
    push(&ed->redo, save_state(&ed->doc));
    restore(s, &ed->doc);
}

void redo(Editor *ed) {
    if (is_empty(&ed->redo)) return;
    State *s = pop(&ed->redo);
    push(&ed->undo, save_state(&ed->doc));
    restore(s, &ed->doc);
}

Backtracking Algorithms

Depth-first search, maze solving, and many recursive algorithms naturally use stacks:

void solve_maze(int maze[][], int start_x, int start_y) {
    Stack path;
    init(&path);
    push(&path, (Point){start_x, start_y});

    while (!is_empty(&path)) {
        Point p = peek(&path);

        if (is_goal(p)) {
            print_solution(&path);
            return;
        }

        if (!has_unvisited_neighbors(maze, p)) {
            pop(&path);  // Backtrack
        } else {
            Point next = get_unvisited_neighbor(maze, p);
            mark_visited(maze, next);
            push(&path, next);
        }
    }
}

5.4 Queues: The FIFO Principle

A queue is an ADT where elements are added at the rear and removed from the front. First In, First Out.

Mental Model: A line of people waiting for a bus. New arrivals join at the back; those at the front board first.

FRONT                                                   REAR
 │                                                       │
 ▼                                                       ▼
┌────────┬────────┬────────┬────────┬────────┐
│   A    │   B    │   C    │   D    │   E    │
└────────┴────────┴────────┴────────┴────────┘
   ↑                                                 ↑
Dequeue()                                      Enqueue(F)
returns A

5.5 Queue Implementation

Simple Array Queue (Inefficient)

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
    int size;
} Queue;

// Problem: Array fills up even though elements leave from front
// Solution: Circular queue

Circular Queue

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} CircularQueue;

int is_empty(CircularQueue *q) {
    return q->front == q->rear;
}

int is_full(CircularQueue *q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

void enqueue(CircularQueue *q, int x) {
    if (is_full(q)) { /* handle overflow */ }
    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % MAX_SIZE;
}

int dequeue(CircularQueue *q) {
    if (is_empty(q)) { /* handle underflow */ }
    int x = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return x;
}

Enqueue 4, 5, 6, then dequeue twice, then enqueue 7:
         front
            │
            ▼
┌────┬────┬────┬────┬────┬────┐
│ 6  │ 7  │ -- │ -- │ 4  │ 5  │
└────┴────┴────┴────┴────┴────┘
                        │
                       rear

Linked List Queue

typedef struct QNode {
    int data;
    struct QNode *next;
} QNode;

typedef struct {
    QNode *front;
    QNode *rear;
} LinkedQueue;

void enqueue(LinkedQueue *q, int x) {
    QNode *node = malloc(sizeof(QNode));
    node->data = x;
    node->next = NULL;
    if (q->rear) q->rear->next = node;
    q->rear = node;
    if (!q->front) q->front = node;
}

int dequeue(LinkedQueue *q) {
    if (!q->front) { /* handle underflow */ }
    QNode *tmp = q->front;
    int x = tmp->data;
    q->front = tmp->next;
    if (!q->front) q->rear = NULL;
    free(tmp);
    return x;
}

5.6 Double-Ended Queue (Deque)

A deque allows insertion and deletion at both ends:

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
    int size;
} Deque;

void push_front(Deque *d, int x);
void push_back(Deque *d, int x);
int pop_front(Deque *d);
int pop_back(Deque *d);

Applications:

• Implementing both stacks and queues
• Palindrome checking
• A-Steal algorithm (parallel task scheduling)
• Text editor undo/redo (two deques)

5.7 Priority Queues

A priority queue extracts elements based on priority, not arrival order:

// Higher number = higher priority (max-heap)
// Lower number = higher priority (min-heap)

typedef struct {
    element_type *data;
    int size;
    int capacity;
    int (*compare)(element_type, element_type);
} PriorityQueue;

Operations:

• Insert: O(log n)
• Extract min/max: O(log n)
• Peek: O(1)
• Decrease/increase key: O(log n) or O(1) with index

Implementations:

• Binary heap: Most common, O(log n) worst case
• Fibonacci heap: O(1) amortized insert, used in Dijkstra’s algorithm
• Binomial heap: O(log n) all operations, useful for meldable priority queues
• Array (sorted): O(1) extract-min, O(n) insert
• Array (unsorted): O(n) extract-min, O(1) insert

5.8 Queue Applications

Breadth-First Search

BFS naturally uses a queue to explore graphs level by level:

def bfs(graph, start):
    visited = {start}
    queue = deque([start])

    while queue:
        vertex = queue.popleft()
        process(vertex)

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Task Scheduling

Operating systems use queues to manage processes:

• Ready queue: Processes waiting for CPU
• I/O queues: Processes waiting for devices
• Priority queues: Real-time scheduling

Print Spooling

Multiple print jobs go into a queue; printers process them in order (or by priority).

Producer-Consumer Problem

Queues mediate between threads or processes with different speeds:

from queue import Queue
import threading

def producer(queue):
    for i in range(10):
        queue.put(i)  # Blocks if queue full

def consumer(queue):
    while True:
        item = queue.get()  # Blocks if queue empty
        process(item)
        queue.task_done()

queue = Queue()
threading.Thread(target=producer, args=(queue,)).start()
threading.Thread(target=consumer, args=(queue,)).start()

5.9 Historical Context

The stack and queue concepts emerged in the 1950s as programmers recognized common access patterns. Alan Turing’s 1949 work on subroutine linkage predated formal stack concepts, the call stack was an informal but essential mechanism.

The term “stack” became standard in the 1960s, replacing earlier terms like “pushdown list.” The queue concept was formalized alongside it.

Edsger Dijkstra’s 1968 paper on “ cooperating sequential processes“ introduced semaphores and discussed bounded buffers (producer-consumer) as fundamental synchronization problems.

Where this connects

• Chapter 9: Heaps and Priority Queues. The priority queue, when FIFO and LIFO are both the wrong order
• Chapter 21: Algorithm Design Using Data Structures. The stack as the implicit structure behind all recursion

Chapter 6: Tree Fundamentals and Binary Trees

6.1 The Tree Abstraction

A tree is a hierarchical data structure consisting of nodes connected by edges, with a single root node from which all other nodes are reachable. Trees model many natural hierarchies: organizational charts, file systems, family genealogies, and evolutionary relationships.

Formal Definition: A tree T is a connected acyclic graph. Equivalently, a tree is a set of nodes where:

• There is a distinguished root node r
• Every node (except r) has exactly one parent
• There is a unique path from r to any node

6.2 Tree Terminology

                    A (Root, Depth 0)
                   /|\
                  / | \
                 B  C  D
                /|  |   \
               / |  |    \
              E  F  G     H
             /     |
            I      J
              |
             (I is descendant of E, B, A; ancestor of itself)

Key Terms:

• Root: The node with no parent (A)
• Parent: Node with children below it (B is parent of E and F)
• Child: Node with parent above it (E and F are children of B)
• Sibling: Nodes with same parent (E and F are siblings)
• Leaf: Node with no children (I, G, H, J)
• Internal node: Node with at least one child (A, B, C, D, F)
• Depth: Number of edges from root to node (I has depth 3)
• Height: Number of edges on longest path from node to leaf
• Level: All nodes at same depth
• Path: Sequence of nodes connected by edges
• Subtree: Node and all its descendants

6.3 Tree Properties

For a tree with n nodes:

• Exactly n-1 edges (each node except root has one edge to its parent)
• A tree with maximum nodes for a given height is “complete”
• A tree with minimum height for a given n is “balanced”

The Handshaking Lemma: In any tree: Σ degree(v) = 2(n-1) This follows because each of the n-1 edges contributes 2 to the degree sum.

6.4 Binary Trees

A binary tree is a tree where each node has at most two children, distinguished as left and right.

struct TreeNode {
    element_type data;
    struct TreeNode *left;
    struct TreeNode *right;
};

Types of Binary Trees

Full (Proper) Binary Tree: Every node has 0 or 2 children:

       ○
      / \
     ○   ○
    / \
   ○   ○

Complete Binary Tree: All levels filled except possibly the last, filled left to right:

       ○
      / \
     ○   ○
    /\  /\
   ○ ○ ○  ○

Perfect Binary Tree: All internal nodes have 2 children; all leaves at same level:

       ○
      / \
     ○   ○
    /\  /\
   ○ ○ ○ ○

Balanced Binary Tree: Height of left and right subtrees differs by at most 1:

       ○                    ○
      / \                  / \
     ○   ○    is balanced  ○   ○
    /                         \
   ○                           ○

6.5 Binary Tree Representations

Pointer-Based Representation

struct Node {
    element_type data;
    struct Node *left;
    struct Node *right;
};

Simple, natural, widely used.

Array Representation (For Complete Trees)

For complete binary trees, store nodes level-by-level in an array:

Array indices:
       0
      / \
     1   2
    /\  /\
   3  4 5  6

Array: [A, B, C, D, E, F, G]

Parent(i)  = (i - 1) / 2
Left(i)    = 2 * i + 1
Right(i)   = 2 * i + 2

This representation is space-efficient for complete trees and is used for heaps.

Left-Child Right-Sibling Representation

Convert any general tree to binary tree:

struct GeneralNode {
    element_type data;
    struct GeneralNode *first_child;
    struct GeneralNode *next_sibling;
};

The binary tree has:

• left pointer → first child
• right pointer → next sibling

6.6 Tree Traversals

Traversal is visiting each node in a systematic order.

Preorder (Root, Left, Right)

def preorder(node):
    if node is None: return
    visit(node)          # Process root first
    preorder(node.left)   # Then all left subtree
    preorder(node.right)  # Then all right subtree

Use cases: Copy tree, prefix notation, directory listing

Inorder (Left, Root, Right)

def inorder(node):
    if node is None: return
    inorder(node.left)    # Left subtree
    visit(node)           # Process root
    inorder(node.right)   # Right subtree

Use cases: BST in sorted order, infix expression evaluation

Postorder (Left, Right, Root)

def postorder(node):
    if node is None: return
    postorder(node.left)   # Left subtree
    postorder(node.right)  # Right subtree
    visit(node)            # Process root last

Use cases: Delete tree, postfix evaluation, computing directory sizes

Level Order (Breadth-First)

from collections import deque

def level_order(root):
    if root is None: return
    queue = deque([root])

    while queue:
        node = queue.popleft()
        visit(node)
        if node.left:  queue.append(node.left)
        if node.right: queue.append(node.right)

Use cases: Shortest path in unweighted graph, level-by-level processing

Morris Traversal (Threaded Binary Tree)

O(1) space traversal using existing tree structure:

def morris_inorder(root):
    current = root
    while current:
        if current.left is None:
            visit(current)
            current = current.right
        else:
            # Find inorder predecessor (rightmost in left subtree)
            pre = current.left
            while pre.right and pre.right != current:
                pre = pre.right

            if pre.right is None:
                pre.right = current  # Create thread
                current = current.left
            else:
                pre.right = None     # Remove thread
                visit(current)
                current = current.right

6.7 Expression Trees

Binary expression trees represent arithmetic expressions:

Expression: (3 + 4) * (2 - 1)

        *
       / \
      +   -
     / \ / \
    3  4 2  1

Preorder (prefix):    * + 3 4 - 2 1
Inorder (infix):      3 + 4 * 2 - 1  (needs parentheses for correctness)
Postorder (postfix):  3 4 + 2 1 - *

6.8 Binary Space Partitioning Trees

BSP trees recursively divide space with hyperplanes:

        │                    │
   ─────┼─────        ───────┼──────
        │    partition       │    partition
   ─────┼─────        ───────┼──────
        │                    │

Used in:

• 3D graphics (visibility determination)
• Ray tracing
• Collision detection
• CAD systems

6.9 Historical Context

Trees as mathematical structures predate computers. Graph theory, including trees, was studied in the 19th century by Kirchhoff, Cayley, and others. Arthur Cayley (1857) enumerated rooted trees, establishing what we now call “Cayley’s formula”: there are n^(n-1) labeled trees on n nodes.

The binary tree became central to computer science through:

• Syntax trees in compilers (1950s)
• Binary search trees (1960s)
• Balanced tree variants (1970s)
• B-trees for databases (1970s)

Where this connects

• Chapter 7: Binary Search Trees. Adding an ordering invariant to the tree
• Chapter 20: Data Structure Design Patterns. The composite and iterator patterns these traversals exemplify

Chapter 7: Binary Search Trees

7.1 The BST Property

A Binary Search Tree maintains elements in sorted order:

For every node:
    - All nodes in left subtree have keys < node's key
    - All nodes in right subtree have keys > node's key

Example:
            8
           / \
          3   10
         / \    \
        1   6    14
           / \   /
          4   7 13

Inorder traversal: 1, 3, 4, 6, 7, 8, 10, 13, 14 (sorted!)

7.2 BST Operations

Search

def bst_search(node, key):
    if node is None or node.key == key:
        return node
    if key < node.key:
        return bst_search(node.left, key)
    return bst_search(node.right, key)

Time: O(h) where h is height. Worst case O(n) for degenerate tree.

Insertion

def bst_insert(root, key):
    if root is None:
        return TreeNode(key)
    if key < root.key:
        root.left = bst_insert(root.left, key)
    else:
        root.right = bst_insert(root.right, key)
    return root

Insert as leaf; find position by following search path.

Deletion

Three cases:

1. Leaf node: Simply remove
2. One child: Replace node with its child
3. Two children: Replace with inorder successor (minimum in right subtree) or inorder predecessor (maximum in left subtree), then delete that successor/predecessor

def bst_delete(node, key):
    if node is None: return None

    if key < node.key:
        node.left = bst_delete(node.left, key)
    elif key > node.key:
        node.right = bst_delete(node.right, key)
    else:  # Found the node to delete
        if node.left is None: return node.right
        if node.right is None: return node.left

        # Node has two children
        successor = min_value(node.right)
        node.key = successor.key
        node.right = bst_delete(node.right, successor.key)

    return node

Minimum and Maximum

def min_value(node):
    current = node
    while current.left:
        current = current.left
    return current

def max_value(node):
    current = node
    while current.right:
        current = current.right
    return current

7.3 BST Complexity Analysis

Average case assumes randomly inserted keys, yielding approximately balanced trees with height ~log n.

Worst case occurs when keys are inserted in sorted order:

Inserting: 1, 2, 3, 4, 5

     1
      \
       2
        \
         3
          \
           4
            \
             5

Height = n, operations = O(n)

7.4 Self-Balancing BSTs

Self-balancing trees maintain height O(log n) regardless of insertion order.

Height-Balance Definitions

Different balancing criteria define different tree families:

7.5 Threaded Binary Trees

Threaded trees store threads (pointers) to inorder predecessor/successor instead of null pointers:

struct ThreadedNode {
    element_type data;
    struct ThreadedNode *left;
    struct ThreadedNode *right;
    int left_thread;  // true if left points to inorder predecessor
    int right_thread; // true if right points to inorder successor
};

Threaded Tree:
         4
        / \
       2   6
      /     \
     1       8

Threads shown as dashed:
     1 ──→ 2 ──→ 4 ──→ 6 ──→ 8

Advantage: O(1) space for traversal (no stack) Disadvantage: More complex insert/delete

7.6 BST Variants

Treaps (BST + Heap)

Combine BST property with random heap priorities:

Treap example (priorities in parentheses):
            (50)8
           /     \
      (30)3      (70)10
        /   \        \
    (20)1   (40)6   (80)14

The BST property holds on keys; heap property holds on priorities. Random priorities ensure expected O(log n) height.

Skip Lists as BST Alternative

Skip lists can be viewed as a probabilistic alternative to BSTs, with similar complexity but simpler implementation.

AA-Trees

Simplified red-black tree that only allows right children to be red:

• Similar to 2-3 tree representation
• Simpler delete (no complex cases)
• O(log n) guaranteed

7.7 Applications of BSTs

• Ordered maps: Python dict (but actually hash-based), C++ map, Java TreeMap
• Ordered sets: Python set, C++ set, Java TreeSet
• Database indexes: B+ trees (multi-level BSTs)
• Priority queues: Can implement with additional min-pointer
• Finger trees: For sequence operations with good complexity

7.8 Choosing BST vs Alternatives

Use BST When:

• Need ordered iteration
• Range queries needed
• Insert/delete balance with search
• Can tolerate O(n) worst case (or using balanced variant)

Use Hash Table When:

• Only point queries needed
• Insert/delete heavy
• Can tolerate hash collisions

Where this connects

• Chapter 8: Self-Balancing Trees. What to do when this degrades to a linked list
• Chapter 17: Persistent Data Structures. Making a BST persistent, so old versions survive updates

Chapter 8: Self-Balancing Trees

8.1 Why Balance Matters

Consider inserting keys in sorted order into a regular BST:

Insert 1, 2, 3, 4, 5, 6, 7:

     1
      \
       2
        \
         3
          \
           4
            \
             5
              \
               6
                \
                 7

Height = 7, Search = O(7)

Now consider the same in a balanced tree:

Same keys, balanced:

         4
       /   \
      2     6
     / \   / \
    1   3 5   7

Height = 3, Search = O(3)

The difference becomes dramatic at scale:

• n = 1,000,000
• Unbalanced height = 1,000,000 → worst case 1M comparisons
• Balanced height ≈ 20 → at most 20 comparisons

8.2 AVL Trees

AVL trees (Adelson-Velsky and Landis, 1962) were the first balanced BST, maintaining balance via height checks.

The Balance Factor

balance_factor(node) = height(left) - height(right)

Allowed values: -1, 0, 1

AVL Tree (balanced):      Not AVL (unbalanced):
       4                        4
      / \                      /
     2   5                    2
    / \                        \
   1   3                        3
                              /
                             1
Height: -1                     -2

Rotations

Rotations restructure the tree to restore balance.

Right Rotation (for left-heavy):

Before:                    After:
    z                         y
   / \                       / \
  y   T4        →           x   z
 / \                       / \ / \
x   T3                    T1 T2 T3 T4

Node z has balance factor -2 (left-heavy)

Node* rotate_right(Node *z) {
    Node *y = z->left;
    Node *T3 = y->right;

    y->right = z;
    z->left = T3;

    // Update heights
    z->height = 1 + max(height(z->left), height(z->right));
    y->height = 1 + max(height(y->left), height(y->right));

    return y;
}

Left Rotation (for right-heavy):

Before:                    After:
    z                         y
   / \                       / \
  T1  y        →            z   x
     / \                   / \ / \
    T2  x                 T1 T2 T3 T4

Left-Right Double Rotation:

Before:                        After:
    z                           x
   / \                         / \
  y   T4        →             y   z
 / \                         / \ / \
T1  x                       T1 T2 T3 T4
   / \
  T2 T3

AVL Insertion

1. Insert as in BST
2. Update heights
3. Check balance factors from inserted node up
4. If balance factor violates, rotate at first unbalanced node

Node* insert_avl(Node *node, int key) {
    // Standard BST insert
    if (!node) return new_node(key);
    if (key < node->key) node->left = insert_avl(node->left, key);
    else if (key > node->key) node->right = insert_avl(node->right, key);
    else return node;  // Duplicate

    // Update height
    node->height = 1 + max(height(node->left), height(node->right));

    // Get balance factor
    int balance = get_balance(node);

    // Four cases
    // Left-Left
    if (balance > 1 && key < node->left->key)
        return rotate_right(node);

    // Right-Right
    if (balance < -1 && key > node->right->key)
        return rotate_left(node);

    // Left-Right
    if (balance > 1 && key > node->left->key) {
        node->left = rotate_left(node->left);
        return rotate_right(node);
    }

    // Right-Left
    if (balance < -1 && key < node->right->key) {
        node->right = rotate_right(node->right);
        return rotate_left(node);
    }

    return node;
}

AVL Properties

• Height ≤ 1.44 log₂(n+1) (tight bound)
• Search, insert, delete: O(log n)
• Insert may require at most 2 rotations
• Delete may require up to O(log n) rotations
• Better for read-heavy workloads

8.3 Red-Black Trees

Red-black trees use color bits instead of heights, enabling simpler rebalancing.

Red-Black Properties

1. Every node is either red or black
2. Root is black
3. All leaves (NIL) are black
4. Red nodes cannot have red children (no red-red)
5. Every path from a node to descendant leaves has the same number of black nodes

Valid Red-Black Tree:
            B(30)
           /      \
        R(10)    R(40)
        /  \     /   \
      B(5) B(20) B(35) B(50)

Path black counts (from any node):
30→5: B,R,B = 3 black nodes
30→20: B,R,B = 3 black nodes
30→35: B,R,B = 3 black nodes
30→50: B,R,B = 3 black nodes

Why Properties Guarantee Balance

From property 5, all paths from root to leaves have the same black count. Combined with property 4 (no consecutive reds), the longest path is at most twice the shortest. Since shortest path has at least log₂(n+1) black nodes, the tree height is at most 2 × log₂(n+1) = O(log n).

Rotations and Recoloring

Red-black operations are more complex but use fewer rotations than AVL.

Insertion Cases:

Case 1: Uncle is red
    Recolor parent, uncle to black, grandparent to red

Case 2: Uncle is black, triangle
    Rotate child up

Case 3: Uncle is black, line
    Rotate parent up

void insert_rb(Node **root, int key) {
    // Standard BST insert
    Node *new = bst_insert(*root, key);
    new->color = RED;

    // Fix violations
    fix_violation(root, new);
}

void fix_violation(Node **root, Node *z) {
    Node *parent = NULL, *grandparent = NULL;

    while (z != *root && is_red(z) && parent != NULL) {
        parent = z->parent;
        grandparent = parent->parent;

        // Parent is left child
        if (parent == grandparent->left) {
            Node *uncle = grandparent->right;

            if (is_red(uncle)) {  // Case 1
                parent->color = BLACK;
                uncle->color = BLACK;
                grandparent->color = RED;
                z = grandparent;
            } else {
                if (z == parent->right) {  // Case 2
                    z = parent;
                    rotate_left(root, z);
                }
                // Case 3
                parent->color = BLACK;
                grandparent->color = RED;
                rotate_right(root, grandparent);
            }
        } else {  // Parent is right child (symmetric)
            // ... mirror cases
        }
    }
    (*root)->color = BLACK;
}

AVL vs Red-Black Comparison

8.4 Splay Trees

Splay trees (Sleator and Tarjan, 1985) use a different strategy: instead of maintaining invariants, they “splay” accessed nodes to the root.

The Splay Operation

When accessing a node, perform rotations to bring it to the root:

• Zig: Node is child of root
• Zig-Zig: Node and parent are both left/right children
• Zig-Zag: Node is left, parent is right (or vice versa)

Zig-Zig (left-left):
      g                    x
     / \                 / \
    p   T4      →      T1   p
   / \                     / \
  x   T3                  T2  g
 / \                         / \
T1  T2                     T3  T4

Zig-Zag (left-right):
    g                    x
   / \                 / \
  p   T4     →       p   g
 / \                 / \ / \
T1  x               T1 T2 T3 T4
   / \
  T2 T3

Amortized Analysis

Using the potential method with potential = Σ log₂(size(i)), each splay operation costs O(log n) amortized.

Key property: Recently accessed elements are near the root (temporal locality). For repeated access to same element, splay trees are optimal.

Splay Tree Properties

• O(log n) amortized for insert, delete, search
• O(log n) worst-case per operation
• No balance information needed (simpler implementation)
• Adaptive: good for locality of reference
• No guaranteed worst-case (unlike AVL, Red-Black)
• Can be made partially persistent

8.5 Scapegoat Trees

Scapegoat trees maintain balance by rebuilding subtrees when they become too unbalanced.

Balance Criterion

A tree is α-weight-balanced if for every node: size(child) ≤ α × size(node)

Typical α = 0.5 to 1 (0.5 = AVL-like strictness)

Insertion

1. Insert as in BST
2. Walk back to root tracking path
3. If height > log_1/α (n), find scapegoat and rebuild

The scapegoat is not necessarily the deepest unbalanced node; any node on the path that restores balance works.

Properties

• No rotations needed (simpler than AVL/Red-Black)
• O(log n) amortized insert/delete
• O(log n) worst-case search
• Simple to implement
• Good for systems where rotations are expensive

8.6 Treaps

Treaps combine BST with random heap priorities.

Why Random Priorities Work

With random priorities:

• Expected height = O(log n)
• Probability of O(n) height = negligible
• No explicit balancing needed

import random

class TreapNode:
    def __init__(self, key, priority=None):
        self.key = key
        self.priority = priority or random.random()
        self.left = None
        self.right = None

def treap_insert(root, node):
    if not root:
        return node

    if node.key < root.key:
        root.left = treap_insert(root.left, node)
        if root.left.priority < root.priority:
            root = rotate_right(root)
    else:
        root.right = treap_insert(root.right, node)
        if root.right.priority < root.priority:
            root = rotate_left(root)

    return root

8.7 Performance Comparison

*Amortized or expected

8.8 Real-World Usage

Where this connects

• Chapter 7: Binary Search Trees. The unbalanced baseline these structures fix
• Chapter 21: Algorithm Design Using Data Structures. Why skip lists trade rotations for randomness

Chapter 9: Heaps and Priority Queues

9.1 The Heap Property

A heap is a complete binary tree satisfying the heap property:

• Max-heap: Parent ≥ Children (root is maximum)
• Min-heap: Parent ≤ Children (root is minimum)

Max-Heap:
            90
           /  \
         80    70
        /  \   /  \
      50   40 60   30
      / \
    10   20

Min-Heap:
             10
           /    \
         20      30
        /  \    /  \
      50   40  60   70

9.2 Heap Array Representation

Heaps are typically stored in arrays due to their completeness:

Array representation of max-heap:
Index:    0   1   2   3   4   5   6   7   8
Array: [90 | 80 | 70 | 50 | 40 | 60 | 30 | 10 | 20]
         ↑
       Root

Parent(i)     = (i - 1) / 2
LeftChild(i)  = 2 * i + 1
RightChild(i) = 2 * i + 2

The complete tree property guarantees no “holes” in the array.

9.3 Heap Operations

Maintaining the Heap Property: Heapify

Heapify restores the heap property at a node by “sifting down” larger children:

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;
    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

Heapify at index 1 (value 80):
Before:                After:
       90                    90
      /  \                  /  \
    [80]  70      →        50    70
    /  \                /  \
  50   40              80   40

Building a Heap

Two approaches:

1. Insert each element: O(n log n)
2. Heapify from bottom up: O(n)

void build_heap(int arr[], int n) {
    // Index of last non-leaf node = n/2 - 1
    for (int i = n/2 - 1; i >= 0; i--)
        heapify(arr, n, i);
}

Why O(n)? Most nodes are near leaves, requiring few swaps.

Extract Maximum/Minimum

int extract_max(int arr[], int *n) {
    if (*n <= 0) return -1;
    if (*n == 1) return arr[--(*n)];

    int max = arr[0];
    arr[0] = arr[--(*n)];
    heapify(arr, *n, 0);
    return max;
}

Insert

void insert(int arr[], int *n, int key) {
    int i = (*n)++;
    arr[i] = key;

    // Sift up
    while (i > 0 && arr[(i - 1) / 2] < arr[i]) {
        swap(&arr[i], &arr[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

9.4 Heap Sort

Heap sort uses a heap to sort in O(n log n):

void heap_sort(int arr[], int n) {
    // Build max heap
    build_heap(arr, n);

    // Extract elements
    for (int i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);  // Move max to end
        heapify(arr, i, 0);      // Heapify reduced heap
    }
}

Properties:

• In-place: O(1) extra space
• Not stable (equal elements may change relative order)
• O(n log n) worst case
• Good for embedded systems (no recursion, predictable)

9.5 Priority Queue Implementation

Heaps implement priority queues efficiently:

class PriorityQueue:
    def __init__(self):
        self.heap = []

    def push(self, item, priority):
        self.heap.append((priority, item))
        self._sift_up(len(self.heap) - 1)

    def pop(self):
        if not self.heap:
            return None
        max_item = self.heap[0][1]
        last = self.heap.pop()
        if self.heap:
            self.heap[0] = last
            self._sift_down(0)
        return max_item

    def peek(self):
        return self.heap[0][1] if self.heap else None

9.6 Binomial Heaps

Binomial heaps support efficient meld (merge) operations.

Binomial Trees

A binomial tree B_k has:

• 2^k nodes
• Height k
• Made by linking two B_(k-1) trees

B_0:  ○                 (1 node)

B_1:  ○                 (2 nodes)
      │
      ○

B_2:  ○                 (4 nodes)
     /│\
    ○ ○ ○

B_3:  ○                 (8 nodes)
     /│\
    ○ ○ ○
   /│││\
  ○○○○○○○

Binomial Heap Structure

A binomial heap is a collection of binomial trees satisfying:

• Each binomial tree is a min-heap (or max-heap)
• At most one binomial tree of each order k
• Trees are stored in a root list by increasing order

Binomial Heap (7 nodes):
- B_2 tree (4 nodes)
- B_1 tree (2 nodes)
- B_0 tree (1 node)

Root list:
○4 → ○2 → ○1 → NULL
 │     │
 └─○───┘   └─○─→ NULL

Operations:

• Insert: O(1) (create new B_0, merge)
• Extract-min: O(log n) (remove min, merge remaining trees)
• Meld: O(log n)
• Decrease-key: O(log n)

9.7 Fibonacci Heaps

Fibonacci heaps achieve O(1) amortized insert and decrease-key, making them ideal for algorithms like Dijkstra’s.

Structure

• Roots of trees form a circular doubly-linked list
• One pointer to minimum element
• Trees are heap-ordered but not necessarily binomial
• Lazy consolidation: don’t immediately consolidate after deletions

Fibonacci Heap:

   ○20 ←── minimum
  /│\
 ○ ○ ○
 ││││
 ○ ○ ○ ○
    ...

Actual structure varies, no fixed binomial structure

Amortized Analysis

Potential function: Φ = number of trees + 2 × marked nodes

*The degree bound ensures actual cost is bounded

Why “Fibonacci”?

The degree of any node is bounded by about φ × n (golden ratio), leading to the name. Each node can have at most O(log n) children.

9.8 Pairing Heaps

Pairing heaps are simpler than Fibonacci heaps with similar (often better) practical performance.

Structure

• Multiway trees with heap ordering
• Roots linked in a list
• No balance information stored

Operations

def link(pq1, pq2):
    # Link two heaps, return larger root
    if pq1.value < pq2.value:
        pq2.left = pq1.left
        pq1.left = pq2
        return pq1
    else:
        pq1.left = pq2.left
        pq2.left = pq1
        return pq2

def extract_min(pq):
    # Remove root, merge children two-by-two
    children = pq.children  # linked list
    pairs = []
    while children:
        pair = children
        children = children.next
        if children:
            pair.next = children.next
            children = children.next
        pairs.append(link(pair[0], pair[1]))

    result = None
    for p in pairs:
        result = link(result, p) if result else p
    return result

Empirical Performance

Despite lack of theoretical guarantees, pairing heaps:

• Perform as well as or better than Fibonacci heaps in practice
• Are much simpler to implement
• Are cache-friendly

9.9 Applications of Heaps

Sorting: Heap sort Priority queues: Task scheduling, event simulation Graph algorithms: Dijkstra’s (with decrease-key), Prim’s Data compression: Huffman coding Operating systems: Memory allocation, CPU scheduling Statistics: Kth largest/smallest elements Stream processing: Sliding window median

9.10 Historical Context

The heap was introduced by J.W.J. Williams in 1964 as part of heap sort. The binary heap structure was further analyzed by Floyd in 1964, who proved that heapify works in O(n) time.

Fibonacci heaps were introduced by Fredman and Tarjan in 1987, revolutionizing graph algorithms by enabling faster shortest paths.

Binomial heaps were introduced by Vuillemin in 1978, providing efficient meld operations.

Where this connects

• Chapter 19: Emerging and Specialized Structures. Why Fibonacci heaps win on paper and lose in practice
• Chapter 21: Algorithm Design Using Data Structures. The greedy algorithms that are built on this structure

Chapter 10: Multiway Search Trees and B-Trees

10.1 Beyond Binary: The Need for Multiway Trees

Binary trees require O(log n) levels, which means O(log n) disk accesses for large trees stored on disk. If each level requires a disk read, this is still costly.

B-trees solve this by allowing more than two children per node:

Binary tree for 1 million keys:
Height ≈ 20 (with good balance)
Disk accesses for search: 20

B-tree with 1000 children per node:
Height ≈ 3
Disk accesses for search: 3

This dramatic reduction in height makes B-trees ideal for disk-based storage.

10.2 B-Tree Definition

A B-tree of order m satisfies:

1. Every node has at most m children
2. Every internal node (except root) has at least ⌈m/2⌉ children
3. The root has at least 2 children (unless it’s a leaf)
4. A node with k children contains k-1 keys
5. All leaves appear at the same depth

B-tree of order 5 (max 4 keys, 5 children):
        ┌───────────────┐
        │ 20 │ 40 │ 60 │
        └───────────────┘
       /    │    │    \
   [0-20) [20-40) [40-60) [60+)

10.3 B-Tree Operations

Search

Similar to BST but with linear search within nodes:

def btree_search(node, key):
    i = 0
    while i < len(node.keys) and key > node.keys[i]:
        i += 1

    if i < len(node.keys) and key == node.keys[i]:
        return (node, i)  # Found

    if node.is_leaf:
        return None  # Not found

    return btree_search(node.children[i], key)

Insert

1. Find leaf where key belongs
2. Insert key (split if node is full)

def btree_insert(root, key):
    if len(root.keys) == MAX_KEYS:
        # Split root
        new_root = split_root(root)
        root = new_root

    return _insert(root, key)

def _insert(node, key):
    i = 0
    while i < len(node.keys) and key > node.keys[i]:
        i += 1

    if node.is_leaf:
        node.keys.insert(i, key)
    else:
        if len(node.children[i].keys) == MAX_KEYS:
            split_child(node, i)
            if key > node.keys[i]:
                i += 1
        _insert(node.children[i], key)

Splitting Nodes

When a node is full, split it:

Full node with 4 keys (max):
    ┌─────────────────┐
    │10│20│30│40│50│  ← Split into:
    └─────────────────┘
           ↓
    ┌───────┐   ┌───────┐
    │10│20│  │  │40│50│  (two nodes)
    └───┴───┘   └───┴───┘
           │
       ┌───┴───┐
       │  30   │  ← Median key goes up
       └───────┘

10.4 B+ Trees

B+ trees are optimized for range queries, common in databases.

Differences from B-trees

1. Only leaves store data/values; internal nodes store only keys
2. Leaves are linked (usually doubly-linked)
3. Internal nodes are routing nodes (like telephone switching)

B+ Tree (internal nodes):
        ┌───────────────────┐
        │   20  │  40  │ 60 │
        └───────────────────┘
        /     │     │     \
    [0-20) [20-40) [40-60) [60+)

Leaves (linked for range queries):
┌──────┬──────┬──────┐    ┌──────┬──────┐
│10│15│25│30│35│ → │40│50│ → NULL
└──────┴──────┴──────┘    └──────┴──────┘

Advantages:

• More keys fit in internal nodes (higher fan-out, shallower)
• Leaves linked for efficient range scans
• All data at same depth (predictable I/O)

10.5 B* Trees

B* trees modify B-trees to keep nodes at least 2/3 full:

• Split only when two sibling nodes are full
• Redistribute between siblings before splitting
• More space-efficient than B-trees

10.6 2-3 Trees and 2-3-4 Trees

2-3 trees are B-trees of order 3:

• 2-node: 1 key, 2 children
• 3-node: 2 keys, 3 children

2-node:          3-node:
    ┌───┐         ┌───────┐
    │ 5 │        │ 5 │ 8 │
    └─┬─┘         └───┬─┘
      │               /│\

These are conceptual foundations for understanding B-trees and for implementing in-memory balanced trees.

10.7 Real-World Applications

Database Systems:

• MySQL (InnoDB): B+ trees
• PostgreSQL: B+ trees (primary), other indexes
• Oracle: B+ trees, B* trees
• SQL Server: B+ trees

File Systems:

• NTFS (Windows): B+ trees
• HFS+ (macOS): B-trees
• ext4 (Linux): HTrees (generalized B+ trees)
• ReiserFS: B-trees

Key-Value Stores:

• LevelDB: Skip list + SSTable with B-tree-like index
• RocksDB: LSM trees (log-structured merge)
• Cassandra: B+ trees (local), distributed indexes

10.8 Performance Characteristics

10.9 Variations and Extensions

B+-tree variants:

• B*-tree: Higher utilization
• B+-tree with bulk loading
• Prefix B-trees: Compress keys

LSM Trees (Log-Structured Merge):

• Write-optimized alternative
• Used in Cassandra, RocksDB, LevelDB
• Components: memtable (in-memory), SSTables (disk)

RD-tree (Recursive Decomposition):

• For multi-dimensional range queries
• Used in geographic databases

10.10 Historical Context

B-trees were introduced by Rudolf Bayer and Edward McCreight in 1970 at Boeing. The “B” stands for “balanced,” “broad,” or “Boeing” (depending on source).

The B+ tree variant was introduced shortly after, optimized for databases.

Donald Comer provided the comprehensive analysis in his 1979 paper “The Ubiquitous B-Tree,” showing how B-trees dominated database indexing.

Where this connects

• Chapter 16: External Memory and Cache-Oblivious Structures. The external-memory model that explains why B-trees exist
• Chapter 14: Probabilistic Data Structures. The Bloom filters that make LSM-tree reads viable

Volume II: Advanced Structures and Algorithms

Chapters

• Chapter 11: Graphs—Modeling Relationships
• Chapter 12: Hash Tables
• Chapter 13: String Data Structures

Chapter 11: Graphs—Modeling Relationships

11.1 Graph Fundamentals

A graph G = (V, E) consists of:

• V: A set of vertices (also called nodes)
• E: A set of edges connecting pairs of vertices

Graph Example:
V = {A, B, C, D, E}
E = {(A,B), (A,C), (B,D), (C,D), (D,E)}

    A
   /│\
  / │ \
 B   C───D───E

11.2 Graph Types

Directed vs. Undirected:

• Undirected: Edges have no direction (relationships are symmetric)
• Directed: Edges have direction (A → B ≠ B → A)

Weighted vs. Unweighted:

• Weighted: Edges have weights (distances, costs)
• Unweighted: All edges equal weight 1

Simple vs. Multi:

• Simple: No loops, no parallel edges
• Multi: Parallel edges allowed

Cyclic vs. Acyclic:

• Cyclic: Contains cycles
• Acyclic: No cycles (DAGs if directed)

11.3 Graph Representations

Adjacency Matrix

A V×V matrix where matrix[i][j] indicates edge presence:

// For weighted graph
int adj[V][V];
// adj[i][j] = weight if edge exists, INF otherwise

Undirected Graph:
     A  B  C  D
   ┌──────────────
 A │ 0  1  1  0
 B │ 1  0  0  1
 C │ 1  0  0  1
 D │ 0  1  1  0

Space: O(V²)

Pros: O(1) edge queries, simple Cons: O(V²) space even for sparse graphs

Adjacency List

Store neighbors in linked lists or arrays:

struct Node {
    int vertex;
    struct Node *next;
};

struct Graph {
    int V;
    struct Node **adj;
};

Adjacency List:
A → [B] → [C] → NULL
B → [A] → [D] → NULL
C → [A] → [D] → NULL
D → [B] → [C] → [E] → NULL
E → [D] → NULL

Space: O(V + E)

Pros: O(V + E) space, good for sparse graphs Cons: Edge lookup is O(degree)

11.4 Graph Traversal

Breadth-First Search (BFS)

BFS explores vertices in order of distance from source:

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])

    while queue:
        vertex = queue.popleft()
        print(vertex)

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Properties:

• Uses queue (FIFO)
• Produces shortest path in unweighted graphs
• Time: O(V + E)
• Space: O(V)

Depth-First Search (DFS)

DFS explores deeply before backtracking:

def dfs_recursive(graph, vertex, visited=None):
    if visited is None:
        visited = set()

    visited.add(vertex)
    print(vertex)

    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)
            stack.extend(graph[vertex])

Properties:

• Uses stack (LIFO) or recursion
• Produces discovery/exploration order
• Time: O(V + E)
• Space: O(V)

11.5 Topological Sort

Topological sort orders vertices of a DAG so all edges go forward:

def topological_sort(graph):
    in_degree = {v: 0 for v in graph}
    for v in graph:
        for u in graph[v]:
            in_degree[u] += 1

    queue = [v for v in graph if in_degree[v] == 0]
    result = []

    while queue:
        v = queue.pop(0)
        result.append(v)
        for u in graph[v]:
            in_degree[u] -= 1
            if in_degree[u] == 0:
                queue.append(u)

    return result

Applications:

• Build systems (make)
• Course scheduling
• Task dependencies
• Assembly instructions

11.6 Minimum Spanning Trees

A spanning tree connects all vertices with minimum total edge weight.

Kruskal’s Algorithm

Greedy edge-by-edge:

def kruskal(graph):
    edges = sorted(graph.edges, key=lambda e: e.weight)
    uf = UnionFind(V)
    mst = []

    for edge in edges:
        u, v = edge.u, edge.v
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append(edge)
            if len(mst) == V - 1:
                break

    return mst

Time: O(E log E) or O(E log V)

Prim’s Algorithm

Grow MST from a vertex:

def prim(graph, start):
    visited = {start}
    edges = []
    heap = [(w, start, v) for v, w in graph[start]]
    heapq.heapify(heap)

    while heap and len(visited) < len(graph):
        w, u, v = heapq.heappop(heap)
        if v in visited:
            continue

        visited.add(v)
        edges.append((u, v, w))

        for w2, v2 in graph[v]:
            if v2 not in visited:
                heapq.heappush(heap, (w2, v, v2))

    return edges

Time: O(E log V) with binary heap

11.7 Shortest Paths

Single-Source: Dijkstra’s Algorithm

For non-negative weights:

import heapq

def dijkstra(graph, source):
    dist = {v: float('inf') for v in graph}
    dist[source] = 0
    pq = [(0, source)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue

        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))

    return dist

Time: O((V + E) log V)

All-Pairs: Floyd-Warshall

Dynamic programming for all pairs:

def floyd_warshall(graph):
    n = len(graph)
    dist = [[float('inf')] * n for _ in range(n)]

    for i in range(n):
        dist[i][i] = 0
    for u in range(n):
        for v, w in graph[u]:
            dist[u][v] = w

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist

Time: O(V³), Space: O(V²)

11.8 Union-Find (Disjoint Set Union)

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False

        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

Time: O(α(n)) amortized (inverse Ackermann, effectively constant)

11.9 Applications

Social Networks: Friend suggestions, degrees of separation GPS/Maps: Shortest routes, point-to-point navigation Internet: Routing protocols (link-state, distance-vector) Web: PageRank, web crawling Biology: Protein interaction networks, evolutionary trees Finance: Transaction graphs, fraud detection Recommendation Systems: Collaborative filtering

Where this connects

• Chapter 21: Algorithm Design Using Data Structures. The greedy and DP paradigms behind these algorithms
• Chapter 28: Network Topology and Routing Data Structures. The same graph structures applied to network routing

Chapter 12: Hash Tables

12.1 The Hash Table Idea

Hash tables provide O(1) average-case lookup by computing an index from a key via a hash function.

Key: "apple"
Hash function: h(key) → 3
Index 3 → Value stored

Direct addressing would need 26 slots for letters.
Hash table needs fewer slots with good hash function.

The idea is best understood as a compromise between two extremes. Direct addressing (one array slot per possible key)gives genuine O(1) access but needs an array the size of the key space, which for 64-bit integers or arbitrary strings is impossible. A sorted array needs only n slots but costs O(log n) per lookup.

A hash table takes the array indexing of the first and the space of the second, and pays for it with collisions: squeezing a large key space into m slots guarantees that different keys sometimes land on the same one. Everything difficult about hash tables follows from that single consequence.

Worth being precise about the guarantee, since “O(1) lookup” is repeated so often it stops being examined. It is O(1) average case, under the assumption that keys distribute uniformly. The worst case is O(n) (every key colliding)and that worst case is reachable by an adversary who knows your hash function. This is not hypothetical: collision-flooding denial of service against PHP, Java, Python, and Ruby web frameworks was demonstrated in 2011 and forced all of them to change their hashing.

12.2 Hash Functions

A hash function maps keys to array indices.

Requirements

1. Deterministic: Same key always maps to same index
2. Uniform: Keys distribute evenly across indices
3. Fast: O(1) computation

A fourth requirement belongs on that list for anything handling untrusted input: unpredictable. An attacker who can compute your hash function offline can generate thousands of keys that all collide, turning every operation into a linear scan. Uniformity over random input is not the same as uniformity over chosen input.

There is also a subtle correctness requirement that causes real bugs: equal keys must hash equally. In languages where you can override both equality and hashing, overriding one without the other produces a container that loses entries. The key is there, but the lookup goes to the wrong bucket. This is the single most common hash-table bug in application code.

Common Methods

Division Method:

h(k) = k mod m

Choose m as a prime not near a power of 2.

The reason for the prime matters. If m is a power of two, k mod m keeps only the low bits of k and discards everything else, so keys differing only in their high bits all collide. Pointers and aligned addresses have predictable low bits, which is exactly the case where this fails badly. A prime m mixes all the bits of k into the result.

Implementations that do want a power-of-two table size (because masking is faster than division) must therefore mix the bits first: Java’s HashMap XORs the high 16 bits into the low 16 before masking, precisely for this reason.

Multiplication Method:

h(k) = floor(m × (k × A mod 1))

Knuth’s A = (√5 - 1)/2 ≈ 0.618

The value of A is the reciprocal of the golden ratio, and it is chosen because it is the irrational number hardest to approximate with a fraction, which means successive multiples spread across the interval as evenly as possible rather than clustering. Unlike the division method, this works with any m, including powers of two.

Universal Hashing:

h(k) = ((a × k + b) mod p) mod m

Random a, b from large prime field.

This is the principled defense against adversarial input, and the guarantee is stronger than it looks: for any two distinct keys, the probability of collision over a random choice of (a, b) is at most 1/m. No fixed input is bad, because the function is not fixed until runtime. Carter and Wegman’s 1979 result is the reason modern languages seed their hash functions randomly at process start.

String Hashing:

/* Signed overflow is undefined behaviour in C, and a negative
   intermediate makes `% m` negative, an out-of-bounds index.
   Use unsigned, and mask or mod only at the end. */
unsigned long hash_string(const char *s, unsigned long m) {
    unsigned long h = 5381;
    while (*s) {
        h = h * 33 + (unsigned char)*s;   /* djb2; wraps harmlessly */
        s++;
    }
    return h % m;
}

The original version of this function used int and applied % m inside the loop. Both are bugs: signed overflow is undefined behaviour, and a negative h yields a negative index in C. Hash arithmetic should always be done in unsigned types.

What production code actually uses. The classic multiply-and-add hashes (djb2, FNV, the h*31 in Java’s String.hashCode) are fine for well-behaved keys and weak against chosen ones. Modern defaults:

Choose by threat model: keyed hashes for anything reachable by user input, fast unkeyed hashes for internal maps with trusted keys. Rust makes this explicit. The default HashMap uses SipHash, and swapping in FxHashMap for internal use is often a 2× speedup.

12.3 Collision Resolution

When two keys hash to the same index, we need a strategy.

Chaining

Store colliding elements in a linked list:

Index  ┌──────────────────────────────────┐
  0    │ NULL                             │
  1    │ [John:555] → [Mary:123] → NULL │
  2    │ NULL                             │
  3    │ [Alice:456] → NULL              │
  4    │ NULL                             │
  5    │ [Bob:789] → NULL                │
       └──────────────────────────────────┘

Load factor α = n/m (elements per bucket)

• Search: O(1 + α)
• Insert: O(1)
• Delete: O(1 + α)

Because chains can grow without bound, α may exceed 1. A chained table never “fills up”, it just degrades. Deletion is straightforward, which is chaining’s main advantage over the alternative.

Java’s HashMap adds a refinement worth knowing: once a chain exceeds 8 entries it converts to a red-black tree, capping the worst case at O(log n) instead of O(n). That single change neutralises collision-flooding attacks without requiring a keyed hash.

Open Addressing

Find another empty slot in the array.

Linear Probing:

h(k), h(k)+1, h(k)+2, ... (mod m)

Problem: Primary clustering

Quadratic Probing:

h(k), h(k)+1², h(k)+2², h(k)+3², ... (mod m)

Problem: Secondary clustering

Double Hashing:

h(k), h(k)+h₂(k), h(k)+2×h₂(k), ... (mod m)

Best clustering behavior.

The clustering problems are worth distinguishing. Primary clustering is the serious one: with linear probing, any run of occupied slots grows at both ends, and longer runs are more likely to be extended, so clusters feed on themselves and probe sequences lengthen non-linearly. Secondary clustering is milder: keys with the same initial hash follow identical probe sequences, but keys with different hashes do not interfere.

Despite the theory favouring double hashing, linear probing usually wins in practice below about 70% load, because its probe sequence is sequential memory access. The next slot is almost always in the same cache line already fetched. Double hashing jumps randomly through the table and misses cache on nearly every probe. This is Chapter 16’s lesson applied: an algorithm with more operations can be faster if the operations are cheaper.

Two constraints specific to open addressing. Load factor must stay below 1, and performance collapses as it approaches: at α = 0.9 linear probing averages about 50 probes per unsuccessful search, versus about 2.5 at α = 0.5. Resize at 0.7 or below.

And deletion requires tombstones. Simply clearing a slot breaks the probe chain for any key that probed past it, making entries unreachable. The slot must be marked “deleted but occupied” instead, and tombstones accumulate, eventually requiring a rehash to clear.

12.4 Hash Table Operations

A complete open-addressing table, with the resize and tombstone handling that the sketch version omits:

_EMPTY = object()      # never written
_DELETED = object()    # tombstone: probe past it, but reuse on insert

class HashTable:
    def __init__(self, capacity=16):
        self._keys = [_EMPTY] * capacity
        self._values = [None] * capacity
        self._count = 0            # live entries
        self._used = 0             # live entries + tombstones

    def _probe(self, key):
        """Yield indices in probe order. Linear probing: cache-friendly."""
        i = hash(key) % len(self._keys)
        for _ in range(len(self._keys)):
            yield i
            i = (i + 1) % len(self._keys)

    def __setitem__(self, key, value):
        first_tombstone = None
        for i in self._probe(key):
            k = self._keys[i]
            if k is _EMPTY:
                # Reuse an earlier tombstone if we passed one.
                slot = first_tombstone if first_tombstone is not None else i
                if first_tombstone is None:
                    self._used += 1
                self._keys[slot], self._values[slot] = key, value
                self._count += 1
                break
            if k is _DELETED:
                if first_tombstone is None:
                    first_tombstone = i
            elif k == key:
                self._values[i] = value        # overwrite, no count change
                return
        # Resize on *used*, not count, since tombstones lengthen probes too.
        if self._used > len(self._keys) * 0.7:
            self._resize(len(self._keys) * 2)

    def __getitem__(self, key):
        for i in self._probe(key):
            k = self._keys[i]
            if k is _EMPTY:
                raise KeyError(key)            # probe chain ended
            if k is not _DELETED and k == key:
                return self._values[i]
        raise KeyError(key)

    def __delitem__(self, key):
        for i in self._probe(key):
            k = self._keys[i]
            if k is _EMPTY:
                raise KeyError(key)
            if k is not _DELETED and k == key:
                self._keys[i] = _DELETED       # tombstone, not _EMPTY
                self._values[i] = None
                self._count -= 1
                return
        raise KeyError(key)

    def _resize(self, new_capacity):
        """Every key must be rehashed; indices depend on table size."""
        old = [(k, v) for k, v in zip(self._keys, self._values)
               if k is not _EMPTY and k is not _DELETED]
        self._keys = [_EMPTY] * new_capacity
        self._values = [None] * new_capacity
        self._count = self._used = 0
        for k, v in old:
            self[k] = v                        # tombstones dropped here

Four details in that code are the ones people get wrong:

• _EMPTY terminates a probe chain; _DELETED does not. Confusing the two makes entries unreachable after a deletion.
• Resize triggers on _used, not _count. A table churning through insertions and deletions can be mostly tombstones with few live entries; if you only watch the live count, probe sequences grow without ever triggering a rehash.
• Insertion reuses the first tombstone it passed, rather than the empty slot at the end. Otherwise the table fills with tombstones even when entries are being replaced.
• Resizing rehashes everything. Indices are computed modulo the table size, so nothing carries over. This makes a single insertion O(n) occasionally, which is why the bound is amortized O(1): the same argument as the dynamic array in Chapter 3.

That last point has a consequence for latency-sensitive systems: a hash table’s average insert is O(1), but one insert in every n takes O(n). If tail latency matters, either pre-size the table or use an incremental-resize scheme that migrates a few entries per operation, as Redis does.

12.5 Perfect Hashing

If all keys are known in advance, we can construct a hash table with no collisions.

Two-level scheme:

• First level: Hash to buckets
• Second level: Hash each bucket with no collisions (requires more slots)

The FKS scheme (Fredman, Komlós, Szemerédi, 1984) makes this concrete and gives the surprising result: O(1) worst-case lookup in O(n) total space. The trick is the second level. A bucket holding bᵢ keys gets a table of size bᵢ², where a randomly chosen hash function is collision-free with probability above ½, so a few retries always find one. Squaring sounds wasteful, but the expected sum of bᵢ² across all buckets is O(n) when the first level is chosen well.

Minimal perfect hashing goes further, mapping n keys to exactly n slots with no gaps. Modern constructions (CHD, BBHash, PTHash) achieve about 2–3 bits of overhead per key. These are used where a key set is fixed and lookups are hot: compiler keyword recognition, gperf-generated parsers, static routing tables, and the term dictionaries in search indexes.

12.6 Applications

Dictionaries/Maps:

• Python dict, Java HashMap, C++ unordered_map

Sets:

• Python set, Java HashSet

Caches:

• LRU cache with hash table + linked list

Database indexing:

• Hash indexes (for equality queries)

Symbol tables:

• Compiler symbol tables

Counting/frequency:

• Word frequency in text

The LRU cache is worth expanding, because it is the canonical example of composing two structures to get properties neither has alone. A hash table gives O(1) lookup but no notion of recency; a doubly linked list gives O(1) reordering but no lookup. Combine them (hash key → list node, list ordered by recency)and every operation is O(1): find the node by hash, unlink it, move it to the head. Python’s functools.lru_cache and every production cache are built this way.

Where hash tables are the wrong choice, which is easy to forget given how good the average case is: any workload needing ordered iteration, range queries, nearest-key lookups, or prefix matching. Those need a tree or a trie. The failure mode is insidious because a hash table works fine until the day someone asks for “all records between these two dates”.

12.7 Historical Context

Hash tables were invented independently by multiple researchers in the 1950s-1960s. The term “hash” comes from the idea of “hashing” (mixing up) the keys.

The first published description is Arnold Dumey’s in 1956, though Hans Peter Luhn had described chaining in an internal IBM memorandum in 1953, and Gene Amdahl, Elaine McGraw, and Arthur Samuel had implemented linear probing for the IBM 701 assembler in 1954: making it one of the few fundamental data structures whose invention is documented in code before it appeared in a paper.

Donald Knuth’s analysis in The Art of Computer Programming Volume 3 (1973) established the mathematics of both methods and remains the standard reference. Carter and Wegman introduced universal hashing in 1979, which turned adversarial resistance from a hope into a theorem, and Fredman, Komlós, and Szemerédi gave the first O(1) worst-case scheme in 1984. Pagh and Rodler’s cuckoo hashing (2001) achieved the same worst-case guarantee with a far simpler structure.

Where this connects

• Chapter 14: Probabilistic Data Structures. Trading exactness for a 10-100x memory reduction
• Chapter 18: Concurrent Data Structures. What it takes to make a hash table concurrent

Chapter 13: String Data Structures

Strings break the assumptions the rest of this book runs on. A comparison is no longer O(1). Comparing two strings costs up to their length. And the queries people actually want are different in kind: not “is this key present” but “which keys start with this”, “where does this pattern occur”, “what is the longest repeated section”. Hash tables answer none of those, because hashing destroys exactly the structure the questions are about.

The structures here exploit the one property strings have that opaque keys don’t: shared prefixes. Every structure in this chapter is a way of storing a set of strings so that common prefixes are stored once.

13.1 Tries (Prefix Trees)

A trie stores strings by their prefixes. Each edge carries a character, and a string is a path from the root:

Trie for {"cat", "car", "card", "do", "dog", "done"}:

root
 │
 ├── c
 │   └── a
 │       ├── t ●          "cat"
 │       └── r ●          "car"
 │           └── d ●      "card"
 │
 └── d
     └── o ●              "do"
         ├── g ●          "dog"
         └── n
             └── e ●      "done"

● marks a node where a stored word ends.

The end-of-word marks matter more than they look. car and card both terminate, and car’s marker sits on an internal node, so “is this node a leaf” is not the same question as “does a word end here”. A trie that conflates the two cannot store a word that is a prefix of another word, which is a common bug.

class TrieNode:
    __slots__ = ("children", "is_word")

    def __init__(self):
        self.children = {}      # char -> TrieNode
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):                       # O(L)
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    def search(self, word):                       # O(L)
        node = self._walk(word)
        return node is not None and node.is_word

    def starts_with(self, prefix):                # O(P)
        return self._walk(prefix) is not None

    def with_prefix(self, prefix):                # O(P + output)
        """Every stored word beginning with `prefix`. The autocomplete query."""
        node = self._walk(prefix)
        if node is None:
            return
        stack = [(node, prefix)]
        while stack:
            n, s = stack.pop()
            if n.is_word:
                yield s
            for ch, child in n.children.items():
                stack.append((child, s + ch))

    def _walk(self, s):
        node = self.root
        for ch in s:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

The complexity is the selling point. Lookup is O(L) in the length of the query, completely independent of how many strings are stored. A trie holding ten strings and a trie holding ten million answer a 12-character lookup in the same time. No hash table can promise that, because hashing the key is already O(L) and then collisions depend on n.

Note the BST column: string comparison is O(L), so a BST of strings is O(L log n), not O(log n). A detail that reference tables routinely get wrong.

Space is the problem. A node with a 256-entry array per character costs 2KB per node before storing anything. For a dictionary of English words that is wildly wasteful, since most nodes have one or two children. The mitigations, in increasing order of sophistication: a hash map per node (what the code above does. Flexible, one indirection), a sorted array of children (compact, binary search), a 256-bit bitmap plus a packed child array (succinct, the approach in Chapter 24), or compressing the paths outright, which is the next section.

13.2 Radix Trees (Compressed Tries)

Compress any chain of single-child nodes into one edge holding a whole substring:

Radix tree, same words:

root
 │
 ├── "ca"
 │   ├── "t" ●            "cat"
 │   └── "r" ●            "car"
 │       └── "d" ●        "card"
 │
 └── "do" ●               "do"
     ├── "g" ●            "dog"
     └── "ne" ●           "done"

The chain c→a became one edge "ca".

The guarantee this buys: every internal node either ends a word or has at least two children, so a radix tree over n strings has at most n−1 branching nodes regardless of how long the strings are. Space becomes proportional to the number of strings, not the number of characters. For sparse key sets (long keys with little overlap, like URLs or file paths)the saving is enormous.

PATRICIA tries take it further by storing, at each node, only the bit position that distinguishes the subtrees, skipping the intervening bits entirely. A lookup descends on those bit tests alone and performs exactly one full key comparison at the end. This makes them ideal for fixed-width binary keys, which is why they index IP routing tables. An IP lookup is a longest-prefix match over 32 or 128 bits, and the Linux kernel’s routing table (fib_trie) is a PATRICIA variant.

Adaptive Radix Trees (ART) are the modern refinement: node size adapts to the number of children (4, 16, 48, or 256 slots), so sparse and dense regions each get an appropriate layout. ART is competitive with hash tables on lookups while preserving ordering, and is used in HyPer, DuckDB, and several key-value stores.

13.3 Suffix Trees

The structures so far index a set of strings. A suffix tree indexes one string, by all of its suffixes, which is what makes arbitrary substring search possible, because every substring is a prefix of some suffix.

The terminal $ (a character not otherwise in the alphabet) guarantees no suffix is a prefix of another, so every suffix ends at a leaf:

Suffix tree for "banana$": a compressed trie of all 7 suffixes.
Leaf labels are the starting positions of each suffix.

root
 ├── "$"                                  → 6
 ├── "a"
 │    ├── "$"                             → 5
 │    └── "na"
 │         ├── "$"                        → 3
 │         └── "na$"                      → 1
 └── "banana$"                            → 0
 └── "na"
      ├── "$"                             → 4
      └── "na$"                           → 2

Read a path from the root and you have a substring of “banana”. The node reached by “ana” has two leaves below it (3 and 1), which says immediately that “ana” occurs twice, at positions 3 and 1. That is the general pattern: internal nodes correspond to repeated substrings, and the number of leaves below a node is the number of occurrences.

This is why so many string problems collapse to tree traversals:

Ukkonen’s 1995 algorithm builds the tree in O(n) for a constant alphabet: online, one character at a time. It is genuinely difficult to implement correctly; the suffix links and the “active point” bookkeeping are notorious.

That difficulty, plus the memory cost, is why suffix trees are less used than their power suggests. A suffix tree needs roughly 20 bytes per character in a practical implementation. Indexing a 3-billion-character genome would take 60GB. The next section is the response to that.

13.4 Suffix Arrays

A suffix array is just the sorted list of suffix starting positions: the same information as a suffix tree’s leaf order, in a flat integer array:

String: "banana$"

Suffixes:  0:"banana$"  1:"anana$"  2:"nana$"  3:"ana$"
           4:"na$"      5:"a$"      6:"$"

Sorted lexicographically:
  rank 0:  "$"          → position 6
  rank 1:  "a$"         → position 5
  rank 2:  "ana$"       → position 3
  rank 3:  "anana$"     → position 1
  rank 4:  "banana$"    → position 0
  rank 5:  "na$"        → position 4
  rank 6:  "nana$"      → position 2

Suffix array: [6, 5, 3, 1, 0, 4, 2]

Four bytes per character instead of twenty. Same queries, far better cache behavior, because a binary search over a contiguous integer array is about as friendly to hardware as a search gets.

The LCP array stores the longest common prefix between each suffix and the one before it in sorted order, with LCP[0] = 0 by convention:

rank:  0     1      2       3        4          5      6
suffix "$"   "a$"   "ana$"  "anana$" "banana$"  "na$"  "nana$"
LCP:    0     0      1       3        0          0      2
              ↑      ↑       ↑                          ↑
           "$" vs   "a$" vs  "ana$" vs               "na$" vs
           "a$"     "ana$"   "anana$"                "nana$"
           share    share    share "ana"             share "na"
           nothing  "a"

Kasai’s algorithm computes the LCP array in O(n) once the suffix array is known. Together, the suffix array and LCP array carry all the information in a suffix tree: the LCP array encodes the tree’s internal node structure implicitly, so any suffix-tree algorithm can be rewritten to use them.

Construction is a solved problem: SA-IS (Nong, Zhang, Chan, 2009) builds a suffix array in O(n) worst case, is straightforward compared to Ukkonen’s algorithm, and is fast in practice. The simpler O(n log n) doubling approach (sort by first character, then by first 2, then 4, then 8)is what most people implement in contests and is usually fast enough.

Searching with a plain suffix array is O(m log n): binary search, comparing up to m characters at each of log n steps. With the LCP array and a little extra bookkeeping this drops to O(m + log n).

Suffix arrays are the practical default. The FM-index goes one step further, compressing the suffix array to the text’s own entropy while keeping it searchable, which is how BWA and Bowtie fit a human genome index in a few gigabytes.

13.5 Aho–Corasick: Searching for Many Patterns at Once

Everything so far searches for one pattern. The common real problem is the opposite: given ten thousand patterns (a spam word list, a malware signature set, a set of banned URLs)find every occurrence of any of them in one pass over the text.

Running a single-pattern search once per pattern is O(k·n) for k patterns. Aho–Corasick does it in O(n + total pattern length + occurrences), independent of k.

The construction is a trie of all patterns, augmented with failure links. A failure link from a node points to the node representing the longest proper suffix of the current match that is also a prefix of some pattern: exactly the generalization of the KMP failure function to a set of patterns.

Patterns: {"he", "she", "his", "hers"}

        root
       /    \
      h      s
     / \      \
    e●  i      h
    |    \      \
    r     s●     e●        ● = a pattern ends here
    |
    s●

Failure link: the node for "she" fails to the node for "he",
because "he" is the longest suffix of "she" that is also a prefix
of a pattern. So on matching "she" you also report "he" for free.

When a character doesn’t match, follow the failure link instead of restarting. The automaton never re-reads a character of the text, which is where the linear bound comes from. This is the algorithm behind grep -F, most intrusion detection systems, and content filters.

13.6 Choosing a String Structure

The decisive question is which side you preprocess. Index the text (suffix array, FM-index) when the text is fixed and queries are many: a genome, a codebase, a document corpus. Index the pattern (KMP, Aho–Corasick) when the text streams past once and the patterns are fixed: a log pipeline, a packet filter.

13.7 Applications

Autocomplete: Trie prefix matching Spell checking: Dictionary lookup IP routing: Longest prefix match DNA sequencing: Pattern matching Search engines: Inverted indexes

In shipped systems: Elasticsearch and Lucene store their term dictionaries as finite-state transducers, a compressed-trie variant that shares suffixes as well as prefixes; the Linux kernel routes packets through fib_trie, a PATRICIA variant; BWA and Bowtie align sequencing reads against an FM-index of the reference genome; grep -F and Snort use Aho–Corasick; Redis implements its stream IDs and cluster key routing over radix trees; and DuckDB and HyPer index with ART.

13.8 Historical Context

Tries were described by Axel Thue in 1912 in a paper on repetition-free strings, long before computers existed to store them. René de la Briandais rediscovered them for file searching in 1959, and Edward Fredkin named them in 1960. From retrieval, which is why the original pronunciation is “tree” and why nobody agrees about it.

Donald Morrison published PATRICIA in 1968 (“Practical Algorithm To Retrieve Information Coded In Alphanumeric”), one of the better backronyms in computing.

Peter Weiner gave the first linear-time suffix tree construction in 1973, in a paper Knuth reportedly called “the algorithm of the year.” McCreight simplified it in 1976, and Ukkonen produced the online version in 1995 that most implementations follow.

Udi Manber and Gene Myers introduced suffix arrays in 1990 explicitly as the space-efficient answer to suffix trees, and were candid that they were trading a little query time for a large memory saving: a trade that looks better every year as datasets grow faster than RAM.

Alfred Aho and Margaret Corasick published their multi-pattern algorithm in 1975 while at Bell Labs, where it went straight into fgrep.

Where this connects

• Chapter 24: Research-Grade Data Structures. The compressed, succinct versions of these indexes
• Chapter 23: Advanced Competitive Programming Data Structures. Suffix automata and palindromic trees for contests

Volume III: Specialized and Modern Structures

Chapters

• Chapter 14: Probabilistic Data Structures
• Chapter 15: Spatial and Geometric Data Structures
• Chapter 16: External Memory and Cache-Oblivious Structures
• Chapter 17: Persistent Data Structures
• Chapter 18: Concurrent Data Structures
• Chapter 19: Emerging and Specialized Structures
• Chapter 20: Data Structure Design Patterns
• Chapter 21: Algorithm Design Using Data Structures
• Chapter 22: Practical Considerations

Chapter 14: Probabilistic Data Structures

14.1 The Probabilistic Approach

Sometimes we don’t need exact answers, we need fast, space-efficient approximate answers. Probabilistic data structures trade accuracy for speed and space.

That trade is worth stating precisely, because the amount of accuracy given up is small and the amount of space saved is not. Tracking the unique visitors to a website exactly means storing every visitor ID: 100 million IDs at 16 bytes each is 1.6GB. A HyperLogLog answers the same question to within about 2% using 12 kilobytes: a factor of 130,000. For a dashboard, 2% error is invisible and 1.6GB is not.

The general shape of every structure in this chapter:

• Hash the input. A good hash turns arbitrary data into uniformly distributed bits, and uniformity is what makes the statistics work.
• Keep a lossy summary of the hashes rather than the data itself. Bits set, maximum leading-zero counts, counter minima.
• Accept a bounded, quantifiable error in exchange for space that grows far more slowly than n, often not at all.

The critical design question for any of them is which direction the error goes, because a one-sided error is usually safe to build on and a two-sided one usually isn’t:

“False positives only” is what makes a Bloom filter safe as a cache filter: a false positive costs one wasted lookup, while a false negative would mean losing data. Match the error direction to what a mistake costs you.

14.2 Bloom Filters

A Bloom filter tells you if an element is “probably in the set” or “definitely not.”

Structure:

• m-bit array, all initially 0
• k hash functions
• Insert: Set bits at h₁(x), h₂(x), …, hₖ(x)
• Query: Check if all bits at h₁(x), h₂(x), …, hₖ(x) are 1

Bloom filter with m=12, k=3:

After inserting "apple", "banana":
bits: [1] [0] [1] [0] [0] [1] [0] [1] [0] [1] [0] [1]
       0   1   2   3   4   5   6   7   8   9  10  11

Query "grape": bits 2,5,9 all 1 → "Probably present" (false positive!)
Query "mango": bit 3 is 0 → "Definitely not present"

The asymmetry is structural, not a limitation to be engineered away. Insertion only ever sets bits to 1 and never clears them, so a bit that is 0 proves that nothing which hashes there was inserted, “definitely not present” is a proof. A bit that is 1 only proves something set it, which may have been a different element. Hence: no false negatives, ever; false positives at a rate you choose.

class BloomFilter:
    def __init__(self, expected_items, false_positive_rate=0.01):
        # These two formulas are the whole design.
        self.m = math.ceil(-expected_items * math.log(false_positive_rate)
                           / (math.log(2) ** 2))
        self.k = max(1, round(self.m / expected_items * math.log(2)))
        self.bits = bytearray((self.m + 7) // 8)

    def _positions(self, item):
        # Kirsch-Mitzenmacher: two real hashes simulate k of them
        # with no loss in the false-positive bound.
        h1, h2 = mmh3.hash64(item)
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, item):
        for pos in self._positions(item):
            self.bits[pos // 8] |= 1 << (pos % 8)

    def __contains__(self, item):
        return all(self.bits[pos // 8] >> (pos % 8) & 1
                   for pos in self._positions(item))

False positive probability:

p ≈ (1 - e^(-kn/m))^k

Optimal k = (m/n) × ln 2

The optimal k balances two opposing pressures: more hash functions means more bits must coincidentally align for a false positive, but also more bits set per insertion, filling the array faster. The optimum falls where the array is exactly half full, which is a pleasing result. A Bloom filter operating at its design capacity has half its bits set.

What the formula implies in practice, which is the part worth memorising:

Bits per element is independent of element size. Ten bits per element whether the elements are 8-byte integers or 2KB URLs. That property is why Bloom filters appear wherever the exact set would not fit in memory.

The Kirsch-Mitzenmacher trick in the code above matters for performance: computing seven independent hash functions is expensive, and it turns out two are enough. h1 + i*h2 gives the same asymptotic false-positive rate. Every production implementation does this.

Properties:

• False positives possible
• False negatives impossible
• Cannot delete (Counting Bloom Filter needed)
• Space: ~1.44 × log₂(1/p) bits per element

Two further constraints that catch people. You must size it in advance. A Bloom filter cannot grow, and exceeding the expected count degrades the false-positive rate quickly rather than gracefully. (Scalable Bloom filters chain progressively larger filters to work around this.) And you cannot enumerate the contents: a Bloom filter can answer questions about membership but cannot tell you what it holds.

14.3 Counting Bloom Filters

Store counters instead of bits to enable deletion:

Standard Bloom:     [1] [0] [1] [0]
Counting Bloom:     [3] [0] [2] [0]

After deleting one "apple" (counters decrement):
Counting Bloom:     [2] [0] [1] [0]

Deleting from a standard Bloom filter is impossible because clearing a bit might erase evidence of a different element that happens to share it. Counters fix this by recording how many elements set each position.

The cost is 4× the space, since 4 bits per counter is the usual choice. Four bits caps a counter at 15, and counter overflow is the failure mode to know about: if a counter saturates it must stop incrementing, and thereafter decrements can take it below its true value, which reintroduces false negatives, the one guarantee the structure was supposed to keep. With good hashing, overflow at 4 bits is vanishingly rare, but the analysis assumes it never happens.

Delete only elements you actually inserted. Deleting an element that was never added decrements counters that belong to other elements and silently corrupts the filter.

14.4 Cuckoo Filters

Modern alternative to Bloom filters:

• Better space efficiency
• Supports deletion
• O(1) expected operations
• Uses cuckoo hashing internally

A cuckoo filter stores a short fingerprint of each element (typically 8 to 12 bits)in a cuckoo hash table with two candidate buckets per item. A query checks both buckets for the fingerprint.

The trick that makes it work is partial-key cuckoo hashing. Standard cuckoo hashing needs the original key to relocate an item, and a filter has thrown the key away. Cuckoo filters compute the second bucket as:

bucket2 = bucket1 XOR hash(fingerprint)

Because XOR is its own inverse, either bucket yields the other from the fingerprint alone, so items can be relocated without ever storing the key.

Versus a Bloom filter: about 20% less space at false-positive rates below 3%, genuine deletion support, and better cache behavior (two bucket probes instead of k scattered bit tests). Against: insertion can fail when eviction chains grow too long, so the table must stay below about 95% load, and like counting Bloom filters, deleting something never inserted corrupts it.

Use a cuckoo filter when you need deletion or the lowest false-positive rate per bit. Use a Bloom filter when you need guaranteed insertion and maximum simplicity.

14.5 HyperLogLog

Estimates the number of distinct elements with ~2% error using ~12KB:

Idea: Hash each element
If hash starts with k zeros, it's a rare event
The maximum number of leading zeros seen estimates n ≈ 2^R

Register-based improvement:
Split hash into:
- r bits → register index (2^r registers)
- (64-r) bits → count leading zeros

The intuition is worth dwelling on because it is genuinely clever. If hashes are uniformly random bit strings, then roughly half start with 0, a quarter with 00, an eighth with 000. So seeing a hash with 10 leading zeros suggests you have probably looked at around 2¹⁰ distinct values. The rarest event you have observed tells you how many trials you have run.

Using only the single maximum is very noisy: one unlucky hash with 20 leading zeros would suggest a million elements when there were ten. The fix is stochastic averaging: use the first r bits of the hash to pick one of 2^r registers, track the maximum leading-zero count separately in each, and combine them. The registers partition the input, so their estimates are independent, and averaging 16,384 independent estimates cuts the error by √16384 = 128.

The combination uses a harmonic mean, not an arithmetic one, because the harmonic mean suppresses the influence of a single large outlier: precisely the failure mode being defended against:

E = α_m · m² / Σᵢ 2^(−M[i])

m = number of registers, M[i] = max leading zeros in register i
α_m ≈ 0.7213 / (1 + 1.079/m)     bias correction constant

Standard error is 1.04/√m. With m = 16,384 registers at 6 bits each (12KB)that is 0.81% error, for a set of any cardinality up to about 2⁶⁴.

The mergeability is the underrated property. The union of two HyperLogLogs is the element-wise maximum of their registers. That means cardinality across a hundred servers can be computed by each server keeping its own sketch and sending 12KB to a coordinator. No coordination, no shuffling of raw data, and the merge is exact. Merging sketches of A and B gives precisely the sketch you’d get from counting A ∪ B directly. This is why every distributed analytics system uses it.

Intersections, however, are not supported. Inclusion-exclusion (|A∩B| = |A| + |B| − |A∪B|) compounds the error of three estimates and produces garbage when the sets differ greatly in size.

14.6 Count-Min Sketch

Estimates frequency of items:

Structure: d rows, w columns
Each row has its own hash function

Add x: increment position h_i(x) in row i
Estimate count of x: min over all rows of count at h_i(x)

Always overestimates (never underestimates)

Where a Bloom filter answers “is x present”, a Count-Min Sketch answers “how many times have I seen x”: in fixed space, for a stream of unbounded length.

d=3 rows, w=6 columns. Adding "apple" three times:

row 0 (h₀):  [0] [3] [0] [0] [0] [0]     h₀(apple) = 1
row 1 (h₁):  [0] [0] [0] [3] [0] [0]     h₁(apple) = 3
row 2 (h₂):  [0] [0] [3] [0] [0] [0]     h₂(apple) = 2

Now add "banana" twice, and suppose h₀(banana) = 1 too:

row 0:  [0] [5] [0] [0] [0] [0]     ← collision inflates this cell
row 1:  [0] [0] [2] [3] [0] [0]
row 2:  [0] [0] [3] [2] [0] [0]

estimate("apple") = min(5, 3, 3) = 3   ✓ the collision is discarded

Why the minimum works: every cell for x contains x’s true count plus whatever collided there. Collisions only ever add, so every row gives an overestimate, and the smallest is the least-contaminated. With d rows the chance that every row collided badly falls exponentially.

The error bound is additive relative to the total stream volume: with w = ⌈e/ε⌉ and d = ⌈ln(1/δ)⌉, the estimate exceeds the truth by more than ε·N with probability at most δ, where N is the total count of all items. The practical implication is that heavy hitters are estimated accurately and rare items are not. An item appearing 0.001% of the time may be swamped by noise. That is usually the right bias, since heavy hitters are what these are deployed to find.

Count-Min sketches are linear: adding two sketches element-wise gives the sketch of the combined stream. Same distributed benefit as HyperLogLog.

14.7 Two More Worth Knowing

MinHash estimates the Jaccard similarity of two sets (|A∩B|/|A∪B|)without comparing them. Hash every element of a set and keep the minimum hash. The probability that two sets share the same minimum is exactly their Jaccard similarity, so keeping k independent minima estimates it to within about 1/√k. Combined with locality-sensitive hashing, this is how near-duplicate detection works at web scale: Google used it for deduplicating crawled pages, and it remains standard for plagiarism detection and clustering.

t-digest estimates quantiles (medians, p95, p99)over a stream in a few kilobytes, with the crucial property that accuracy is highest at the extremes. Ordinary sampling gives uniform accuracy, which is backwards for latency monitoring: nobody cares about a precise median, and everyone cares about p99. t-digest is what Prometheus-adjacent tooling, Elasticsearch percentile aggregations, and most latency dashboards use.

14.8 Applications

Bloom Filters:

• Web caching (Akamai, Google Chrome)
• Database optimization (Google Bigtable)
• Bitcoin SPV nodes
• Spell checkers

HyperLogLog:

• Google BigQuery
• Redis (PFADD, PFCOUNT)
• Analytics dashboards

Count-Min Sketch:

• Network traffic analysis
• Database query optimization

The single highest-leverage deployment is in LSM-tree storage engines. A read in an LSM tree may need to check several sorted runs on disk, and most of them will not contain the key. A Bloom filter per run answers “definitely not here” from memory, skipping the disk read entirely. Cassandra, RocksDB, LevelDB, HBase, and Bigtable all do this, and it is the difference between an LSM read being one disk seek and being ten: see Chapter 16.

Also worth noting: Chrome’s Safe Browsing originally shipped a Bloom filter of malicious URLs so the browser could check locally and only consult Google’s servers on a hit, privacy and latency from the same structure. Medium uses them to avoid re-recommending read articles; Ethereum puts one in every block header so light clients can skip blocks with no relevant logs.

14.9 Historical Context

Burton Bloom published his filter in 1970 in a two-page CACM paper about hyphenation dictionaries. The problem was that a full dictionary would not fit in the memory of the machines of the day. The structure sat quietly for two decades until networking and databases at scale made it indispensable.

Philippe Flajolet spent much of his career on this family. Probabilistic counting came in 1985 with Nigel Martin, LogLog in 2003, and HyperLogLog in 2007 with Fusy, Gandouet, and Meunier. Flajolet’s approach: analytic combinatorics, using complex analysis to derive exact constants like that 0.7213. Is why these structures come with precise error bounds rather than empirical rules of thumb. He died in 2011; HyperLogLog now runs in essentially every large-scale analytics system.

Graham Cormode and S. Muthukrishnan introduced the Count-Min Sketch in 2005, and Andrei Broder developed MinHash at AltaVista in 1997 for exactly the problem the web had just created: too many near-identical pages.

Where this connects

• Chapter 12: Hash Tables. The exact structure these approximate
• Chapter 16: External Memory and Cache-Oblivious Structures. Why Bloom filters are what make LSM-tree reads viable

Chapter 15: Spatial and Geometric Data Structures

15.1 The Spatial Query Problem

Every structure so far has assumed a total order. You can ask a BST for everything between 40 and 60 because “between” means something on a line. In two or more dimensions it stops meaning anything: there is no ordering of points in the plane that keeps neighbors adjacent, so a sorted array of coordinates cannot answer “which restaurants are within 500 metres of me.”

Spatial structures exist to answer three query types that ordered structures cannot:

• Range query: which objects fall inside this rectangle or circle?
• Nearest neighbor (NN): which object is closest to this point? Which k are closest?
• Intersection query: which objects overlap this one?

The shared strategy is the same one trees always use. Recursively partition the space so that a query can discard most of it without examining its contents. What differs is how the partition is chosen: by alternating coordinate (KD-tree), by fixed geometric subdivision (quadtree), or by grouping the objects themselves (R-tree).

15.2 K-Dimensional Trees (KD-Trees)

KD-trees partition k-dimensional space:

2D KD-Tree:
Level 0: Split on x-axis
Level 1: Split on y-axis
Level 2: Split on x-axis
...

        Split on x: x < 7
               │
         ┌─────┴─────┐
         │           │
    [2,3] │       [8,1]
          │
    Split on y: y < 5
         │
    ┌────┴────┐
    │         │
[1,8]     [5,4]

A KD-tree is a BST where the comparison dimension cycles with depth. At depth d in a k-dimensional tree, nodes compare on axis d mod k. Every node therefore splits space with an axis-aligned hyperplane, and the subtree below it occupies a rectangular cell.

Construction. Building a balanced KD-tree means choosing the median along the current axis at each level:

def build_kdtree(points, depth=0):
    if not points:
        return None
    axis = depth % len(points[0])
    points.sort(key=lambda p: p[axis])       # O(n log n) per level
    mid = len(points) // 2
    return KDNode(
        point=points[mid],
        axis=axis,
        left=build_kdtree(points[:mid], depth + 1),
        right=build_kdtree(points[mid + 1:], depth + 1),
    )

Sorting at every level costs O(n log² n). Using a linear-time median selection (introselect / nth_element) brings it to O(n log n), which is what production implementations do.

Nearest neighbor search is where the structure earns its keep. Descend to the leaf containing the query point, then unwind, but at each ancestor, check whether the splitting plane is closer than the best distance found so far. If it is, the other side of that plane could hold something better and must be searched. If it isn’t, an entire subtree is discarded.

def nearest(node, target, best=None):
    if node is None:
        return best
    if best is None or dist(target, node.point) < dist(target, best):
        best = node.point

    axis = node.axis
    diff = target[axis] - node.point[axis]
    near, far = (node.left, node.right) if diff < 0 else (node.right, node.left)

    best = nearest(near, target, best)
    # Only cross the splitting plane if a closer point could exist beyond it
    if abs(diff) < dist(target, best):
        best = nearest(far, target, best)
    return best

That pruning test (abs(diff) < dist(target, best))is the entire algorithm. Everything else is bookkeeping.

The curse of dimensionality. KD-tree NN search is O(log n) on average in low dimensions and O(n) in the worst case. The worst case stops being rare as k grows: in high dimensions almost every cell is close enough to the query that the pruning test fails, and the search degenerates to a full scan. The rule of thumb is that KD-trees stop paying for themselves somewhere around k ≈ 10–20, or more precisely once n < 2^k. Beyond that, use approximate methods. LSH, or HNSW graphs, which is what modern vector databases do.

KD-trees do not rebalance on insertion. A long-lived tree under heavy insertion degrades, and the standard fix is periodic bulk rebuild rather than rotations. Rotating would break the axis-cycling invariant.

15.3 Quad Trees

Divide 2D space into four quadrants recursively:

Level 0:        ┌─────────┐
               │         │
               │         │
               └─────────┘
Level 1:    ┌───┬───┐
           │ NW │ NE │
           ├───┼───┤
           │ SW │ SE │
           └───┴───┘

Where a KD-tree splits on a data point, a quadtree splits on geometry, always at the exact centre of the current cell, regardless of what the data looks like. That single difference drives everything else about the structure.

Point quadtrees subdivide a cell once it holds more than some threshold of points. Region quadtrees subdivide until each cell is uniform. The classic use is image compression, where a solid-colored region collapses to a single leaf no matter how large it is.

class QuadTree:
    def __init__(self, boundary, capacity=4):
        self.boundary = boundary      # (x, y, width, height)
        self.capacity = capacity
        self.points = []
        self.divided = False

    def insert(self, point):
        if not self.boundary.contains(point):
            return False
        if len(self.points) < self.capacity and not self.divided:
            self.points.append(point)
            return True
        if not self.divided:
            self.subdivide()          # create nw, ne, sw, se
        return (self.nw.insert(point) or self.ne.insert(point)
                or self.sw.insert(point) or self.se.insert(point))

Because the subdivision is geometric rather than data-driven, depth depends on how clustered the data is, not on how much of it there is. A million points spread evenly gives a shallow tree; a thousand points stacked nearly on top of each other gives a very deep one. Implementations guard this with a maximum depth.

The 3D generalization is the octree (eight children instead of four), used throughout graphics for frustum culling, collision broadphase, and voxel storage, Minecraft-style voxel worlds are octrees.

15.4 R-Trees

R-trees index rectangles/hyper-rectangles:

R-Tree:
        ┌──────────────────┐
        │   [MBR of all]    │
        │  ┌──┐      ┌──┐   │
        │  │  │      │  │   │
        │  └──┘      └──┘   │
        │    ┌──────┐      │
        │    │      │      │
        │    └──────┘      │
        └──────────────────┘

KD-trees and quadtrees index points. R-trees index extended objects (roads, building footprints, delivery zones)and they are the structure databases actually ship.

An R-tree is a B-tree whose keys are minimum bounding rectangles (MBRs). Each internal entry stores the MBR enclosing everything in its subtree. A query descends into every child whose MBR intersects the query region, which may be more than one, and that is the crucial difference from a B-tree. Where a B-tree descends exactly one path, an R-tree may descend several.

This gives R-trees B-tree virtues: balanced by construction, high fanout, tuned to disk pages, and O(log n) height. It also gives them their central problem: overlap. Sibling MBRs may intersect, and every intersection means a query that could have followed one path now follows two. Search degrades toward O(n) as overlap grows.

The whole R-tree literature is about controlling overlap when a node splits and its entries must be divided in two. Guttman’s original 1984 paper offered linear and quadratic split heuristics. The R-tree* (Beckmann et al., 1990) minimizes a combination of overlap, MBR area, and margin, and reinserts a fraction of entries on overflow instead of splitting immediately; it is meaningfully better in practice and is what most implementations mean by “R-tree” today. The R+-tree eliminates overlap entirely by duplicating objects across cells, trading space and update cost for query speed.

For static data, bulk loading by sorting along a space-filling curve (Sort-Tile-Recursive packing) produces far better trees than repeated insertion.

15.5 Grids, Geohashes, and Space-Filling Curves

The simplest spatial index is a uniform grid: divide space into fixed cells, hash each object into the cells it touches. Insert and point lookup are O(1), which no tree can match. The catch is that a grid has no way to adapt. Cell size must be chosen up front, and real geographic data is wildly non-uniform. A grid sized for Manhattan is useless for Montana.

Space-filling curves offer a different trick: map 2D coordinates to a single number that mostly preserves locality, then use an ordinary B-tree.

• Z-order (Morton) curve: interleave the bits of x and y. Cheap to compute, but has discontinuities where the curve jumps across the space.
• Hilbert curve: better locality preservation and no long jumps, at higher computational cost.

Geohash applies Z-order to latitude/longitude and base-32 encodes the result, so that a shared string prefix means geographic proximity, u4pruyd and u4pruyf are neighbors. This makes spatial proximity queryable in any plain key-value store, which is why geohashes are everywhere. The failure mode is boundary effects: two points either side of a major cell boundary are physically adjacent but share no prefix, so correct implementations query the eight neighboring cells as well.

Production systems have largely moved to hierarchical cell systems built on this idea: Google’s S2 (Hilbert curve projected onto a sphere) and Uber’s H3 (hexagonal cells, so all neighbors are equidistant, which matters for routing and surge pricing).

15.6 Choosing a Spatial Structure

The practical decision tree is short. Points or shapes? Shapes means R-tree. Points in memory and static? KD-tree. Points, clustered, and 2D/3D? Quadtree or octree. Needs to live in a database or shard across machines? Geohash or S2. More than ~20 dimensions? Give up on exactness and use HNSW.

15.7 Applications

KD-Trees:

• Nearest neighbor search
• Point clouds
• Ray tracing

Quad Trees:

• Image compression
• Collision detection
• Sparse data

R-Trees:

• Geographic Information Systems
• Database spatial indexes
• Map applications

In shipped systems: PostGIS and Oracle Spatial index with R-trees (PostgreSQL’s GiST is a generalized R-tree); SQLite ships an R*-tree module; MongoDB and Redis use geohash-backed indexes for $near and GEORADIUS; scikit-learn’s KDTree and BallTree back its neighbor queries; game engines use octrees and BSP trees for visibility and collision; and ray tracers use KD-trees or bounding volume hierarchies, a BVH is essentially an R-tree for triangles.

15.8 Historical Context

Jon Bentley introduced KD-trees in 1975 while a graduate student at Stanford, as a multidimensional generalization of binary search. Raphael Finkel and Bentley described quadtrees the previous year, in 1974. Antonin Guttman published the R-tree in 1984 specifically to make spatial data indexable on disk, and the R*-tree refinement followed from Beckmann, Kriegel, Schneider, and Seeger in 1990.

The space-filling curves are much older than the structures that use them: Giuseppe Peano constructed the first in 1890 and David Hilbert described his variant in 1891, as pure mathematics with no application in view. G. M. Morton put Z-order to work for geographic databases at IBM in 1966: a rare case of a piece of nineteenth-century mathematics arriving in computing essentially unchanged.

Where this connects

• Chapter 16: External Memory and Cache-Oblivious Structures. Why KD-trees degrade once the data leaves cache
• Chapter 19: Emerging and Specialized Structures. HNSW and the high-dimensional case these structures cannot handle

Chapter 16: External Memory and Cache-Oblivious Structures

16.1 The Memory Hierarchy

Modern computers have multiple levels of memory:

• L1 cache: ~32KB, ~1ns
• L2 cache: ~256KB, ~4ns
• L3 cache: ~8MB, ~15ns
• Main memory: ~64GB, ~100ns
• SSD: ~100GB, ~100μs
• Hard disk: ~TB, ~10ms

Read that list again as ratios rather than absolutes. Main memory is roughly 100× slower than L1. A disk seek is roughly 10,000,000× slower. Every complexity result in this book so far has assumed the RAM model from Chapter 1, where any memory access costs the same O(1). Across a spread that wide, that assumption is not an approximation. It is simply false, and it produces wrong predictions about which structure is faster.

The classic demonstration: a linked list and an array with identical asymptotic complexity for traversal, O(n), differ by 10× or more in wall-clock time. The array walks contiguous cache lines and the hardware prefetcher predicts every access. The list chases pointers to arbitrary addresses, and each hop is a potential cache miss. Same O(n), different machines being used.

Two things matter and the RAM model captures neither:

• Transfers are blocked. Memory does not move one word at a time. It moves in cache lines (typically 64 bytes) or disk pages (typically 4KB). Reading one byte costs the same as reading the whole block it sits in.
• Locality is free performance. If a structure arranges the data an algorithm touches together so it arrives in the same block, the remaining accesses cost nothing.

The structures in this chapter are the ones designed under those two facts instead of in spite of them.

16.2 External Memory Model

The I/O model accounts for disk access:

• B: Block size (elements per block)
• M: Internal memory size
• D: Disk access time relative to memory

Goal: Minimize block transfers.

The external memory model (also called the I/O model or the Aggarwal–Vitter model, after its 1988 authors)replaces “count the operations” with “count the block transfers.” Computation on data already in memory is free; only I/O counts. This sounds crude, and it predicts real performance remarkably well.

The model changes the answers, not just the constants:

The last three rows are the whole argument for B-trees. A balanced BST and a B-tree are both O(log n) in the RAM model, so the RAM model says they are equivalent. In the I/O model the BST costs one transfer per level while the B-tree packs B keys into each transfer, giving log_B n instead of log₂ n. With B = 512, a billion keys take 30 I/Os in a BST and 4 in a B-tree. That is not a constant-factor difference in any practical sense. It is the difference between a usable database index and an unusable one.

Sorting is the other headline result. The optimal external sort is a multiway merge with fanout M/B, not the binary merge you would write in memory: read M/B blocks at a time, merge them, write out. Reducing the number of passes over the data is everything, because each pass is n/B transfers. This is why external merge sort in a database uses hundreds of runs at once rather than merging two at a time.

Cache-aware vs. cache-oblivious. A structure that takes B and M as tuning parameters is cache-aware (B-trees are the canonical example: you pick the node size to match the page size). This works, but it must be re-tuned per machine, and it can only be tuned for one level of a hierarchy that has five. Tune your B-tree node to the disk page and you have said nothing about L1, L2, or L3.

16.3 Cache-Oblivious Structures

Cache-oblivious structures perform well at all cache levels without tuning:

van Emde Boas Layout:

Recursively divide at mid-level:

       ┌───────────────┐
       │       ○       │
       ├───────┬───────┤
       │   ○   │   ○   │
       ├───┬───┼───┬───┤
       │ ○ │ ○ │ ○ │ ○ │
       └───┴───┴───┴───┘

A cache-oblivious structure achieves the optimal I/O bound without knowing B or M. This sounds impossible (how do you optimize for a block size you were never told?)and the resolution is elegant: build the structure so that it is simultaneously well-organized at every scale. Whatever B turns out to be, some level of the recursion matches it.

The van Emde Boas layout is the foundational trick. Take a complete binary tree of height h and cut it horizontally at the middle, producing a top subtree of height h/2 and roughly √n bottom subtrees of height h/2. Lay each of those out recursively, and store them contiguously.

Tree:              Layout in memory:
      1            [1 | 2 3 | 4 5 | 6 7 ...]
     / \             ↑    ↑     ↑
    2   3          top  sub1  sub2   ← each recursively vEB-laid-out
   /|   |\
  4 5   6 7

Now consider a root-to-leaf search under any block size B. Somewhere in the recursion there is a level whose subtrees have size between √B and B: those subtrees fit in one block. The search path crosses O(log_B n) such subtrees, so it costs O(log_B n) transfers. That is the same bound a B-tree achieves, obtained without ever naming B. And because the argument holds for every B simultaneously, the same layout is optimal for L1, L2, L3, RAM, and disk at once, which no cache-aware structure can be.

Compare the layouts directly:

The level-order row is worth noting because it is the layout most people write by default. Storing a binary tree breadth-first feels cache-friendly (it is contiguous, after all)but a root-to-leaf path in it touches one new block per level near the bottom, where almost all the nodes are.

Other cache-oblivious results. Funnelsort achieves the optimal sorting bound obliviously, using a recursively-defined merger structure. Cache-oblivious B-trees combine the vEB layout with a packed-memory array to support updates. These are theoretically beautiful and less common in production than the theory would suggest. The constant factors are worse than a well-tuned B-tree, and in practice you usually do know your page size.

16.4 What Production Systems Actually Do

The ideas in this chapter show up in shipped code more often through their conclusions than their specific structures.

B-trees everywhere. Every relational database index, every filesystem (NTFS, HFS+, ext4, APFS all use B-trees or variants), and embedded stores like LMDB. Node size is matched to the page size.

LSM trees take the opposite approach to the same problem. Where a B-tree updates in place (costing a random write per update)a Log-Structured Merge tree buffers writes in a memory table, flushes them as sorted immutable runs, and merges runs in the background. Every disk write becomes sequential. Reads get slower (you may check several runs, which is what the Bloom filters from Chapter 14 mitigate) and space amplification goes up, but write throughput improves by an order of magnitude on both spinning disks and SSDs. This is the write-heavy tradeoff, and it is why LevelDB, RocksDB, Cassandra, and ScyllaDB use it.

Column stores (Parquet, ORC, ClickHouse) are external-memory thinking applied to analytics. A query touching 3 columns of a 200-column table reads 3/200ths of the blocks instead of all of them. Same asymptotics, ~60× fewer transfers.

Struct-of-arrays is the same reasoning at cache-line scale. Storing {x[], y[], z[]} rather than {x,y,z}[] means a loop over just the x values fills each cache line entirely with x values. Games and numerics rely on this heavily.

Practical rules that follow from the model:

1. Prefer contiguous layouts. std::vector beats std::list almost always, even when the asymptotics favor the list.
2. Match node sizes to blocks. A tree node should fill a cache line or a page, not straddle two.
3. Count passes over data, not operations. Two passes over 10GB is a real cost; the arithmetic in between usually is not.
4. Batch and sort. Random access converted into sequential access is often a 100× win.
5. Measure with hardware counters, not just a stopwatch. perf stat reports cache misses directly, which tells you whether you have a locality problem or a computation problem.

16.5 Historical Context

Alok Aggarwal and Jeffrey Vitter formalized the external memory model in their 1988 paper “The Input/Output Complexity of Sorting and Related Problems,” establishing the sorting bound that still bears their names, though the practical wisdom substantially predates the theory, since Knuth’s treatment of external sorting in The Art of Computer Programming Volume 3 (1973) covers tape-based merging in detail.

Cache-oblivious algorithms arrived much later. Harald Prokop’s 1999 MIT master’s thesis, supervised by Charles Leiserson, introduced the model and the van Emde Boas layout application, with the fuller treatment in Frigo, Leiserson, Prokop, and Ramachandran’s FOCS 1999 paper. The layout itself is named for Peter van Emde Boas, who used the recursive halving idea in his 1975 priority queue: a structure solving an entirely different problem.

The LSM tree came from Patrick O’Neil and colleagues in 1996, and sat relatively unused until Google’s Bigtable (2006) made it the default architecture for write-heavy distributed storage.

Where this connects

• Chapter 10: Multiway Search Trees and B-Trees. The B-trees this model exists to explain
• Chapter 22: Practical Considerations. Turning these findings into profiling decisions

Chapter 17: Persistent Data Structures

17.1 Persistence Defined

A persistent data structure preserves previous versions when modified.

Types:

• Partial persistence: Query old versions, update current
• Full persistence: Query and update any version
• Confluent persistence: Merge versions

Every structure so far has been ephemeral: modifying it destroys what was there before. Insert into a BST and the old tree is gone. Persistence removes that destruction. An update returns a new version while every old version remains valid and queryable.

The naive implementation is to copy the whole structure on every update, which is correct, obvious, and O(n) per operation in both time and space. The entire subject is about achieving persistence without paying that price. The key insight is that an update usually touches a small part of the structure, so the new version can share everything it did not touch with the old one.

The three levels of persistence form a strict hierarchy:

Confluent persistence is genuinely harder than the other two. When versions can merge, a node can be reachable by exponentially many paths, and the naive analysis of sharing breaks down.

Immutability is the enabling property. Sharing is only safe if shared nodes are never modified in place. Otherwise a change made through the new version would be visible through the old one, which is exactly what persistence is supposed to prevent. This is why persistent structures and functional programming arrived together.

17.2 Persistent BSTs

Share unchanged nodes on modification. Inserting 25 requires copying every node on the path from the root down to the insertion point, and only those nodes. Everything hanging off that path is shared with the previous version:

Before (version 1):        After (version 2), inserting 25:

      A(50)                  A(50)          A'(50)      ← new root
     /     \                /     \        /      \
  B(30)   C(70)          B(30)   C(70)  B'(30)     │
   /                      /               /   \     │
D(10)                  D(10)          D(10)  E(25)  │
                          ↑              ↑     ↑     │
                          └──────────────┘     │     │
                              shared        new    shared
                                            node   (C(70))

Version 1 root = A, version 2 root = A'.
Copied: A → A', B → B'.  New: E(25).  Shared: D(10), C(70).

Note that B must be copied, not shared: its right-child pointer changes to point at the new node E. This is the part that is easy to get wrong. Any node whose pointers change must be copied; a node is only shareable if nothing about it changes. Since only nodes along the root-to-leaf path have changed children, exactly O(log n) nodes are copied in a balanced tree.

def insert(node, key):
    """Returns the root of a NEW version; `node` remains valid and unchanged."""
    if node is None:
        return Node(key, None, None)
    if key < node.key:
        return Node(node.key, insert(node.left, key), node.right)   # copy, new left
    elif key > node.key:
        return Node(node.key, node.left, insert(node.right, key))   # copy, new right
    return node                                                      # already present

v1 = build_tree([50, 30, 70, 10])
v2 = insert(v1, 25)     # v1 still queryable, unchanged
v3 = insert(v2, 60)     # three coexisting versions

There is no mutation anywhere in that function (it only ever constructs new nodes)which is what makes the old roots remain valid.

This is path copying, and its cost is the height of the tree:

Balance matters more here than in the ephemeral case, because an unbalanced tree costs you both time and permanent space on every update. Red-black trees and AVL trees both path-copy cleanly; the rotations simply produce a few more copied nodes.

Fat nodes are the alternative technique: instead of copying a node, store a list of (version, value) pairs inside it and binary search for the right one at query time. This gives O(1) space per update rather than O(log n), at the cost of an O(log m) slowdown on every access for m versions. Node copying (Driscoll, Sarnak, Sleator, and Tarjan, 1986) combines both: give each node a small fixed number of extra modification slots, and only copy when they fill. Achieving O(1) amortized space with no query slowdown. That paper is where the general theory of making any pointer structure persistent comes from.

17.3 Persistent Arrays and HAMTs

Trees path-copy naturally because they are already logarithmic-depth pointer structures. Arrays do not. A persistent array cannot copy 1,000,000 elements per write.

The standard solution is to stop using a flat array and use a wide, shallow tree instead, then path-copy that. Clojure’s persistent vector is a 32-way branching trie: with a branching factor of 32, a vector of a billion elements is only 6 levels deep, so an update copies 6 nodes of 32 pointers each rather than a billion elements. Depth is ⌈log₃₂ n⌉, which for any realistic n is at most 7. Close enough to constant that these are often described as “effectively O(1)” operations.

32-way trie holding 1,000,000 elements, 4 levels deep:

              [root: 32 ptrs]
             /       |       \
        [32 ptrs] [32 ptrs] [32 ptrs]     ← copied only along the path
        /    |         |          \
     ...   [32 ptrs]  ...        ...
              |
        [32 values]  ← leaf: the element lives here

Update one element: copy 4 nodes (~128 pointers), share everything else.

The Hash Array Mapped Trie (HAMT) applies the same structure to maps. Hash the key, then use 5 bits of the hash per level to index into a 32-wide node. The refinement that makes it space-efficient is a bitmap in each node marking which of the 32 slots are occupied, so a node with 3 children stores 3 pointers and a 32-bit mask rather than 32 mostly-null pointers. Population count on the bitmap converts a logical index to a physical one in one instruction.

HAMTs are the backbone of persistent maps in Clojure, Scala, and Haskell, and the same idea appears in Erlang and in immutable-collections libraries for JavaScript.

17.4 Functional Data Structures

Functional languages favor immutable structures:

• Thread-safe by default
• Undo/redo trivial
• Predictable performance

Examples:

• Clojure’s persistent vectors
• Haskell’s persistent maps
• Scala’s immutable collections

Each of those bullets deserves unpacking, because they are the practical reasons persistence is worth its overhead.

Thread-safe by default is the big one. Every concurrency hazard in Chapter 18 (torn reads, lost updates, iterator invalidation)comes from one thread mutating what another is reading. If nothing is ever mutated, there is nothing to synchronize. Readers need no locks at all, and a writer publishes a new version with a single atomic pointer swap. This is why Clojure’s concurrency story is as simple as it is.

Undo/redo becomes free. Keeping a stack of old roots is the undo history; no command objects, no inverse operations, no replay. Editors and CAD tools built on persistent structures get unlimited undo as a side effect of the data model.

Predictable performance cuts both ways honestly. Persistent structures avoid the latency spikes of a dynamic array’s O(n) resize, but they allocate constantly, which puts pressure on the garbage collector. The constant factors are genuinely worse than mutable equivalents, typically 2–4× for a HAMT versus a good mutable hash table.

Where persistence earns its cost:

• Version control. Git is a persistent data structure. Every commit is a new root over a Merkle tree of directory nodes, sharing every unchanged subtree, which is exactly why committing a one-line change to the Linux kernel does not copy the kernel.
• Databases. MVCC (multi-version concurrency control) in PostgreSQL is partial persistence: readers see a consistent snapshot at their transaction’s start while writers proceed, without either blocking the other. CouchDB and Datomic go further and keep every version permanently.
• Filesystems. ZFS and Btrfs are copy-on-write; a snapshot is just a retained old root, which is why it is instant and initially free.
• UI frameworks. React’s rendering model assumes immutable props, so change detection is a reference comparison rather than a deep traversal.
• Debugging. Time-travel debuggers replay old versions directly, because they still exist.

The cost side, stated plainly: 2–4× slower on write-heavy single-threaded workloads, higher memory use and allocation churn, and worse cache locality than a flat array. The wide-trie designs mitigate that last one but do not eliminate it. Persistence is the right default in concurrent and versioned settings, and the wrong one in a tight numerical loop.

17.5 Historical Context

Driscoll, Sarnak, Sleator, and Tarjan’s 1986 paper “Making Data Structures Persistent” is the foundational work: it established the partial/full/confluent taxonomy and proved that any pointer-based structure with bounded in-degree can be made partially persistent with O(1) amortized space overhead per update. A much stronger and more general result than the path-copying technique most implementations actually use.

Chris Okasaki’s Purely Functional Data Structures (1998), which grew out of his 1996 CMU thesis, addressed the complementary question: which structures can be implemented efficiently without any mutation at all? His treatment of amortization under persistence is the subtle part. The usual banker’s argument breaks when an expensive operation can be re-executed by replaying an old version, and Okasaki’s solution using lazy evaluation and memoization is why the book remains standard reading.

Phil Bagwell introduced the Hash Array Mapped Trie in 2001. Rich Hickey built Clojure’s collections on it in 2007, which more than anything else moved persistent structures from a functional-programming specialty into general practice.

Where this connects

• Chapter 18: Concurrent Data Structures. The concurrency hazards immutability removes outright
• Chapter 7: Binary Search Trees. The BST being made persistent here

Chapter 18: Concurrent Data Structures

18.1 Thread Safety

Concurrent access requires synchronization.

Correctness criteria:

• Linearizability: Each operation appears atomic
• Sequential consistency: Operations match program order
• Lock-freedom: At least one thread progresses
• Wait-freedom: All threads progress in bounded steps

To see why these criteria are needed, look at what breaks without them. Consider two threads pushing onto the singly linked stack from Chapter 5:

void push(Stack *s, Node *n) {
    n->next = s->head;    // (1) read head
    s->head = n;          // (2) write head
}

Thread A executes (1) and is preempted. Thread B runs both lines and pushes its node. Thread A resumes and executes (2), overwriting head with a node whose next still points at the old head. Thread B’s node is gone: silently, with no error, no crash, and no way to detect it later. That is a lost update, and it happens because the read and the write were not one indivisible step.

The two properties above address different questions:

Safety. What results are legal. Linearizability is the standard: every operation appears to take effect instantaneously at some point between its call and its return, and that ordering is consistent with real time. It matters because it composes. Linearizable components can be combined and the result stays reasonable, which is not true of weaker conditions like sequential consistency.

Liveness: whether threads make progress. These form a hierarchy:

The distinction that matters in production: with locks, a thread that is descheduled, page-faults, or crashes while holding a lock stalls every other thread indefinitely. Lock-free structures cannot suffer that failure mode. This matters far more in a real-time or kernel context than in a typical server, which is worth remembering before reaching for lock-free code.

18.2 Lock-Free Techniques

Compare-and-Swap (CAS) is the primitive everything else is built from. Its semantics are: atomically, compare the value at an address to an expected value, and if they match, replace it with a new value. Report whether the swap happened.

The critical word is atomically. This is a single indivisible hardware instruction (LOCK CMPXCHG on x86, LDREX/STREX or CAS on ARM)not something you can write in plain C. The following is what CAS is specified to do, and is emphatically not a valid implementation, since the read and the write can be interleaved by another thread exactly as in the lost-update example above:

/* SPECIFICATION ONLY. This is what the hardware does atomically.
   Written like this in plain C it is a race, not a CAS. */
bool cas_semantics(int *addr, int expected, int new_value) {
    if (*addr == expected) {   // ← another thread can run between
        *addr = new_value;     //   these two lines
        return true;
    }
    return false;
}

The real thing comes from the compiler or the standard library:

#include <stdatomic.h>

/* C11: compiles to a single LOCK CMPXCHG on x86.
   On failure, `expected` is updated with the actual value. */
bool ok = atomic_compare_exchange_weak(&head, &expected, new_value);

The standard usage pattern is a retry loop: read the current value, compute the new one, attempt to swap, and start over if someone beat you to it.

void lock_free_push(_Atomic(Node*) *head, Node *n) {
    Node *old_head = atomic_load(head);
    do {
        n->next = old_head;
    } while (!atomic_compare_exchange_weak(head, &old_head, n));
    /* If the CAS fails, old_head now holds the current value; retry. */
}

No thread ever waits for another. A failed CAS means someone else succeeded, which is why this is lock-free rather than wait-free: the system always progresses, but one unlucky thread could in principle retry forever.

The ABA problem is the classic trap. CAS checks whether a value is unchanged, but what you actually care about is whether the state is unchanged, and those differ. Thread A reads head = X. Thread B pops X, pops Y, then pushes X back. Thread A’s CAS on X succeeds (the pointer matches)but the list beneath it is now completely different, and A may splice in a node pointing at freed memory.

The standard defenses:

• Tagged pointers: pack a counter alongside the pointer and CAS both together (a double-width CAS, LOCK CMPXCHG16B). The counter increments on every update, so a recycled pointer no longer compares equal.
• Hazard pointers: each thread publishes the pointers it is currently dereferencing; memory is not reclaimed while any hazard pointer references it.
• Epoch-based reclamation / RCU: defer reclamation until every thread has passed through a quiescent state.
• Garbage collection: in a GC’d language, ABA via memory reuse largely disappears, which is why lock-free code is considerably easier to write correctly in Java than in C.

Memory reclamation is the hard part of lock-free programming in a non-GC language, and it is where most bugs live. Removing a node from a lock-free structure is easy; knowing when no other thread can still be reading it is not. This is the single strongest argument for using a well-tested library rather than writing your own.

Memory ordering is the other subtlety. Modern CPUs and compilers reorder memory operations aggressively. Correct lock-free code requires explicit ordering constraints. memory_order_acquire on loads that must see prior writes, memory_order_release on stores that must be visible to subsequent readers. Defaulting to memory_order_seq_cst is correct and slower; anything weaker demands genuine care. x86 has a strong memory model that hides many mistakes; the same code on ARM or POWER then fails in production, which is a well-known way to ship a bug.

18.3 Concurrent Data Structures

The Michael–Scott queue (1996) is the standard lock-free FIFO and repays study. It keeps separate head and tail pointers with a permanent dummy node so that the empty case needs no special handling, and enqueue proceeds in two CAS steps: first link the new node to the current last node, then advance the tail pointer.

Between those two steps the queue is in an intermediate state where tail lags one node behind reality. The trick that makes this work is that any thread which observes the lagging tail helps fix it before proceeding:

void enqueue(Queue *q, Node *n) {
    n->next = NULL;
    while (1) {
        Node *tail = atomic_load(&q->tail);
        Node *next = atomic_load(&tail->next);
        if (tail != atomic_load(&q->tail)) continue;      // stale, re-read
        if (next != NULL) {
            /* Someone else is mid-enqueue, so help them finish. */
            atomic_compare_exchange_weak(&q->tail, &tail, next);
            continue;
        }
        if (atomic_compare_exchange_weak(&tail->next, &next, n)) {
            atomic_compare_exchange_weak(&q->tail, &tail, n);  // may fail; fine
            return;
        }
    }
}

That final CAS is allowed to fail, because if it does, some other thread has already performed the fix-up. This helping pattern (threads completing each other’s partial operations rather than waiting)is the general technique for building lock-free structures with multi-step updates.

Concurrent hash maps are where most real applications actually meet this material, and the design has evolved:

• One global lock: correct, trivially, and a bottleneck at any real concurrency.
• Lock striping: N independent locks, bucket i guarded by lock i mod N. Java’s ConcurrentHashMap used 16 segments by default through Java 7. Simple and effective.
• Per-bucket locking with lock-free reads: Java 8 onward CASes into empty buckets and locks only the first node of a non-empty one, while reads are entirely lock-free over volatile fields. Reads scale perfectly; writes contend only on the exact bucket.
• Split-ordered lists (Shalev and Shavit, 2006): a genuinely lock-free hash table that supports resizing without ever blocking. Resizing being the operation that makes concurrent hash tables hard, since it touches everything at once.

Concurrent skip lists are worth knowing because they are why ConcurrentSkipListMap exists while a concurrent balanced BST does not. Insertion is local (CAS a few forward pointers)whereas a red-black tree rebalance rotates nodes far from the insertion point, which is very hard to do lock-free. Randomized structure buys concurrency. This is the same trade that makes skip lists attractive in MemSQL, LevelDB’s memtable, and Redis sorted sets.

Read-Copy-Update (RCU) deserves separate mention because it is the dominant technique inside the Linux kernel. Readers pay nothing at all: no atomics, no barriers on most architectures, literally just a dereference. Writers copy the structure, modify the copy, and atomically swap the pointer, then wait for a grace period before freeing the old version. It is the right answer for the extremely common read-mostly case, and the wrong one for write-heavy workloads.

18.4 When Not to Go Lock-Free

Lock-free programming is one of the easiest ways to write code that is subtly, intermittently, unreproducibly wrong. Before choosing it, work down this list:

1. Don’t share. Thread-local state, sharding, or message passing eliminates the problem instead of solving it. This is by far the best option when it applies.
2. Use immutable data. Persistent structures (Chapter 17) need no synchronization for readers at all.
3. Use a plain lock. An uncontended mutex costs ~20ns. Correct, readable, and fast enough for the overwhelming majority of code.
4. Use a well-tested concurrent library. ConcurrentHashMap, folly::ConcurrentHashMap, crossbeam, java.util.concurrent. These were written by specialists and tested for years.
5. Only then write lock-free code yourself, and only with model checking or stress testing under a race detector (TSan, loom in Rust, JCStress in Java). Reasoning alone is not sufficient; neither is testing on x86 alone.

The honest summary: lock-free structures win on tail latency and on immunity to a stalled thread, not usually on average throughput. A striped lock frequently beats a hand-rolled lock-free structure on both performance and correctness.

18.5 Historical Context

Leslie Lamport defined sequential consistency in 1979 and produced the first lock-free queue (for one reader and one writer) in 1977. Maurice Herlihy and Jeannette Wing introduced linearizability in 1990, giving the field its correctness criterion.

Herlihy’s 1991 paper “Wait-Free Synchronization” is the theoretical foundation: it established the consensus hierarchy, proving that primitives have a consensus number (the maximum number of threads for which they can solve consensus)and that atomic read/write registers have consensus number 1, while compare-and-swap has consensus number ∞. That result is why CAS is the universal primitive and why hardware designers ship it: with CAS you can build a wait-free implementation of any object, and without something like it you provably cannot.

Maged Michael and Michael Scott published their queue in 1996; it went into java.util.concurrent and has been the reference lock-free FIFO ever since. Michael followed with hazard pointers in 2004, addressing the reclamation problem. Paul McKenney’s RCU work brought the read-mostly approach into the Linux kernel from 2002 onward, where it is now used in tens of thousands of places.

Where this connects

• Chapter 17: Persistent Data Structures. Immutability as the alternative to synchronisation
• Chapter 12: Hash Tables. The hash table these techniques are usually applied to

Chapter 19: Emerging and Specialized Structures

This chapter surveys directions the field is currently moving in. Some of these are mature enough to deploy today; others are research with an unclear path to production. Each entry says which. Where a topic gets a full treatment later in the book, this chapter gives the short version and points you there.

19.1 Fibonacci Heaps Revisited

Recent work has produced simpler implementations while maintaining theoretical bounds.

The Fibonacci heap from Chapter 9 is the standard example of a structure that wins on paper and loses in practice. Its O(1) amortized decrease-key improves Dijkstra’s algorithm from O(E log V) to O(E + V log V), which is asymptotically optimal for comparison-based implementations. Yet almost nobody uses one. The constant factors are large, the node structure is heavy (parent pointers, child lists, mark bits), and the cascading-cut logic is cache-hostile. A plain binary heap usually wins on real graphs, and a d-ary heap tuned to the cache line usually wins by more.

The response has been a search for structures with the same bounds and less machinery:

• Pairing heaps (Fredman et al., 1986) are dramatically simpler (a single multiway tree with a merge operation)and fast in practice. Their exact amortized decrease-key complexity was an open problem for two decades; it is now known to be O(log log n), not O(1), yet they still beat Fibonacci heaps on essentially every real workload.
• Rank-pairing heaps (Haeupler, Sen, Tarjan, 2011) achieve the full Fibonacci bounds with substantially simpler restructuring.
• Strict Fibonacci heaps (Brodal, Lagogiannis, Tarjan, 2012) attain the same bounds in the worst case rather than amortized: theoretically significant for real-time systems, still not competitive in practice.

The durable lesson is the one from Chapter 1: asymptotic superiority is a claim about behavior in a limit, and the limit may sit far beyond any input you will ever see.

Status: mature theory, rarely deployed. Use a binary or d-ary heap unless profiling proves decrease-key dominates.

19.2 Succinct Data Structures

Store data in space close to the information-theoretic minimum:

• Operations directly on compressed representation
• Rank, select, navigation

A succinct structure uses Z + o(Z) bits, where Z is the information-theoretic minimum, while still supporting fast queries: crucially, without decompressing. That last property is what separates succinct structures from ordinary compression: gzip achieves better ratios but you must decompress before you can query.

The canonical example: a binary tree of n nodes takes 2n + o(n) bits succinctly, against roughly 128n bits for a pointer-based representation with two 64-bit pointers per node. That is a 64× reduction, and it turns “this index does not fit in RAM” into “this index fits in RAM”, which is a far bigger performance win than any constant-factor speedup.

Everything is built on two primitives over a bit vector:

• rank(i): how many 1s occur before position i
• select(k): the position of the k-th 1

Both answer in O(1) using auxiliary structures occupying o(n) extra bits. Tree navigation, string search, and set membership all reduce to these two operations.

Chapter 24 covers the machinery properly: LOUDS, balanced parentheses, DFUDS, wavelet matrices, and the FM-index.

Status: deployed where memory is the binding constraint. Genomic aligners (BWA, Bowtie) index the human genome with FM-indexes. Succinct tries back autocomplete at scale. The Rust succinct and C++ sdsl-lite libraries are production-quality.

19.3 External Memory Hash Tables

For massive datasets that don’t fit in memory:

• Cuckoo hashing on disk
• Buffered repository trees

A hash table’s defining virtue is that a lookup is one random probe. On disk, one random probe is a 100μs seek, and the virtue becomes the defect, which is why disk-resident indexes are overwhelmingly B-trees rather than hash tables, as Chapter 16 explains.

The techniques that make hashing viable in external memory all amount to trading probes for batching:

• Linear hashing and extendible hashing grow one bucket at a time rather than rehashing everything, so a resize never stalls. Both date to 1979–80 and both are still in use: extendible hashing indexes Berkeley DB and, more recently, PostgreSQL hash indexes.
• Cuckoo hashing on disk bounds lookups to a constant number of probes (two, in the basic scheme), which matters far more when a probe is 100μs than when it is 100ns. The cost is expensive insertions when eviction chains grow long.
• Buffered repository trees and B^ε-trees buffer updates in internal nodes and flush them down in batches, converting many random writes into few sequential ones. This is the same insight as the LSM tree, arrived at from the theory side. TokuDB and its successor, Percona’s fractal tree indexes, shipped it commercially.

Status: mature. The interesting modern development is that NVMe changes the calculus. A random read on NVMe is ~10μs rather than ~10ms, which narrows the gap between hash and tree indexes considerably and is quietly reopening design questions that were settled in the disk era.

19.4 Learned Indexes

Machine learning for index structures:

• Replace B-trees with neural networks
• Can be faster for certain access patterns
• Active research area

The idea, from Kraska et al.’s 2018 paper “The Case for Learned Index Structures,” is a genuine reframing: an index is a function from key to position, and a model can approximate a function. If your keys are integers 1 to 100,000,000 stored in order, the “index” is position = key − 1, no tree needed. Real data is not that clean, but real data is rarely random either, and a model that captures the shape of the key distribution can beat a structure that assumes nothing about it.

A learned index predicts a position, then does a bounded local search to correct the prediction. The Recursive Model Index stages simple models (usually linear regressions, not neural networks, because inference must cost nanoseconds)with each stage narrowing the range.

Reported results are strong: up to 3× faster lookups at a fraction of the memory of a B-tree. The caveats are equally real, and they are what keeps this out of most production systems:

• Updates are the hard part. The original design was read-only. ALEX (2020) and PGM-index (2020) support updates, but a distribution shift may require retraining.
• Worst-case bounds vanish. A B-tree is O(log n) on adversarial input. A learned index is fast on data resembling its training distribution and can degrade badly otherwise.
• Sorted data is the precondition. The technique assumes a sorted array underneath; it accelerates the search, it does not replace the storage.

Status: active research, early production. The PGM-index has strong theoretical guarantees and a usable implementation. Learned bloom filters and learned cache-eviction policies are seeing more real adoption than learned indexes proper.

19.5 Delta Encoding and CRDTs

Conflict-free replicated data types for distributed systems:

• Eventual consistency
• No coordination needed
• Used in collaborative applications

A CRDT is a structure whose merge operation is commutative, associative, and idempotent. Those three algebraic properties are the entire trick: if merging is order-independent and repeat-safe, replicas that receive the same updates in any order, possibly more than once, provably converge to the same state. With no coordination, no consensus, and no leader.

That means a CRDT keeps working while partitioned. In CAP terms it chooses AP and gets convergence anyway, by restricting itself to operations that cannot conflict.

The building blocks, in increasing order of difficulty:

Delta CRDTs address the practical problem with the basic formulation: naive state-based CRDTs ship the entire state on every sync, which is untenable for a large document. Delta CRDTs transmit only the changed portion while preserving the convergence properties.

Collaborative text editing is the demanding case, since concurrent inserts at the same position must produce a consistent order without a coordinator. Yjs and Automerge are the mature implementations, and both are fast enough for real editors: Yjs handles documents with millions of operations.

Chapter 27 develops the theory and the distributed-systems context.

Status: production-ready and spreading fast. Figma, Linear, Apple Notes, and Redis’s conflict-free replicated types all ship CRDTs. This is the most immediately practical topic in this chapter.

19.6 Structures for Vector Search

One significant omission from the original survey, added because it went from research to ubiquitous in roughly three years.

Embedding models turn text, images, and audio into high-dimensional vectors (typically 384 to 1,536 dimensions)and searching them means approximate nearest neighbor over millions of points. Chapter 15 explained why KD-trees collapse at these dimensionalities. The structures that work instead:

• HNSW (Hierarchical Navigable Small World, Malkov and Yashunin, 2016) builds a layered proximity graph and greedily descends it. A skip list where the “links” are nearest neighbors. It is the default in most vector databases: excellent recall, fast queries, high memory use, awkward deletion.
• IVF (inverted file index) clusters vectors and searches only the nearest clusters. Lower memory, tunable recall.
• Product quantization compresses vectors into compact codes, letting billion-scale indexes fit in RAM at some accuracy cost. Usually combined with IVF.
• ScaNN (Google, 2020) uses anisotropic quantization tuned for inner-product search specifically.

Status: production, moving very fast. FAISS, hnswlib, pgvector, Pinecone, Weaviate, Qdrant, and Milvus all ship these. Every retrieval-augmented LLM application depends on one.

19.7 Reading the Frontier

A few honest heuristics for evaluating structures like these, since most novel structures do not survive contact with production:

What tends to succeed solves a problem created by a hardware or workload shift. LSM trees won because write amplification on flash mattered. HNSW won because embeddings created a genuinely new query type. CRDTs won because collaborative editing became a product requirement.

What tends to fail improves an asymptotic bound while worsening constants, requires the workload to be well-behaved, or optimizes something that was not the bottleneck. Fibonacci heaps are the enduring cautionary example.

Questions worth asking of any new structure: What is the constant factor, measured? How does it behave on adversarial input? Does it support updates, or only bulk builds? What happens at the cache and page level? Is there a tested implementation, or only a paper?

That last question filters out most of them.

Where this connects

• Chapter 24: Research-Grade Data Structures. The research-grade treatment of succinct structures
• Chapter 15: Spatial and Geometric Data Structures. The spatial structures vector search replaces

Chapter 20: Data Structure Design Patterns

The preceding chapters covered structures. This one covers the recurring shapes of the code around them: how to extend a structure without rewriting it, how to expose traversal without exposing internals, and how to keep the cost of an abstraction visible.

The patterns here are the Gang of Four patterns as they specifically apply to collections, plus a few that are particular to data structures and appear in no pattern catalog.

20.1 Wrapper/Decorator Pattern

Add functionality to existing structures:

class SynchronizedDict(dict):
    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
        self.lock = threading.Lock()

    def __getitem__(self, key):
        with self.lock:
            return super().__getitem__(key)

A decorator wraps a structure in another object with the same interface, adding behavior on the way through. Synchronization, logging, validation, caching, access counting, and copy-on-write are all naturally decorators. Each is a concern orthogonal to how the data is stored, so each belongs outside the storage.

The example above illustrates the pattern and also a trap worth naming, because it is the single most common way this pattern is misapplied. Subclassing a built-in collection does not reliably intercept its operations. dict.update(), dict.get(), and dict.setdefault() are implemented in C and do not route through __getitem__, so the lock above simply does not apply to them. The structure looks synchronized and is not.

Composition rather than inheritance fixes it, by making the delegation explicit:

class SynchronizedDict:
    """Wraps a dict rather than subclassing it, so nothing bypasses the lock."""

    def __init__(self, initial=None):
        self._data = dict(initial or {})
        self._lock = threading.RLock()      # reentrant: safe if callbacks re-enter

    def __getitem__(self, key):
        with self._lock:
            return self._data[key]

    def __setitem__(self, key, value):
        with self._lock:
            self._data[key] = value

    def get(self, key, default=None):
        with self._lock:
            return self._data.get(key, default)

Worth being honest about what this buys: per-operation locking makes each operation atomic, but sequences of operations still race. if k in d: d[k] += 1 acquires the lock twice and another thread can interleave between them. This is why Java deprecated Hashtable in favor of ConcurrentHashMap’s compound operations like computeIfAbsent, and why a synchronized wrapper is usually the wrong concurrency answer: see Chapter 18.

Real uses: Java’s Collections.unmodifiableList() and synchronizedMap(); Python’s types.MappingProxyType; the copy-on-write wrappers in persistent collection libraries.

20.2 Composite Pattern

Tree-like hierarchical structures:

class Component:
    def operation(self): pass

class Composite(Component):
    def __init__(self):
        self.children = []

    def add(self, c):
        self.children.append(c)

    def operation(self):
        for c in self.children:
            c.operation()

The composite pattern makes a leaf and a container of leaves interchangeable, so client code can treat “one thing” and “a tree of things” identically. Filesystems are the standard illustration. A directory’s size is the sum of its children’s sizes, and a file’s size is its own, but the caller asks the same question of both:

class Node(ABC):
    @abstractmethod
    def size(self) -> int: ...

class File(Node):
    def __init__(self, name, size):
        self.name, self._size = name, size

    def size(self):
        return self._size

class Directory(Node):
    def __init__(self, name):
        self.name, self.children = name, []

    def add(self, node: Node) -> "Directory":
        self.children.append(node)
        return self

    def size(self):
        return sum(child.size() for child in self.children)

This is exactly how the expression trees in Chapter 6 work: a literal and an operator node both answer evaluate(). It is also how the DOM, scene graphs, GUI widget hierarchies, and query plan trees are built.

Two warnings. First, recursive traversal means recursive depth. A deep composite will overflow the stack, and structures with user-controlled depth need an explicit stack instead. Second, the pattern is often written with add()/remove() on the base Component so leaves and composites share one interface; that forces leaves to implement operations that make no sense for them. Keeping child management on Composite alone is the safer choice, at the cost of clients needing a type check to add children.

20.3 Iterator Pattern

Abstract traversal:

class TreeIterator:
    def __init__(self, root):
        self.stack = [root] if root else []

    def __iter__(self):
        return self

    def __next__(self):
        if not self.stack:
            raise StopIteration
        node = self.stack.pop()
        if node.right:
            self.stack.append(node.right)
        if node.left:
            self.stack.append(node.left)
        return node.val

The iterator decouples what you want to visit from how the structure is laid out. Its real value is that it lets a caller consume a traversal without the structure handing over its internals, and without building an intermediate list.

The example above is a pre-order traversal made iterative: note the right child pushed before the left, so the left pops first. Doing this without recursion is not merely stylistic: it makes the traversal lazy, so a caller can stop early after examining three nodes of a million-node tree and pay for three.

In Python, generators express the same thing far more directly, and the in-order version is worth having since it is the traversal that yields a BST’s keys in sorted order:

def in_order(node):
    """Lazy in-order traversal. O(1) amortized per element, O(h) space."""
    stack, current = [], node
    while stack or current:
        while current:                 # descend left, remembering the path
            stack.append(current)
            current = current.left
        current = stack.pop()
        yield current.val              # visit
        current = current.right        # then the right subtree

# Consumes only as much of the tree as it needs:
first_five = list(itertools.islice(in_order(root), 5))

Iterator invalidation is the classic hazard: mutating a structure while iterating it. Growing a Python list during a for loop skips elements; a C++ vector reallocation leaves every outstanding iterator dangling; Java throws ConcurrentModificationException from a modification counter checked on each next(). The three responses (undefined behavior, fail-fast, and snapshot semantics (CopyOnWriteArrayList))represent a real design choice, and fail-fast is usually the right one because it converts a silent wrong answer into a loud crash.

20.4 Builder Pattern

Complex construction:

class BSTBuilder:
    def __init__(self):
        self.values = []

    def add(self, value):
        self.values.append(value)
        return self

    def build(self):
        self.values.sort()
        return self._build_range(0, len(self.values))

    def _build_range(self, lo, hi):
        if lo >= hi:
            return None
        mid = (lo + hi) // 2
        node = TreeNode(self.values[mid])
        node.left = self._build_range(lo, mid)
        node.right = self._build_range(mid + 1, hi)
        return node

Builders matter most for data structures when bulk construction beats repeated insertion, which is often, and by more than people expect.

The example is a good illustration of why. Inserting n sorted values into a plain BST one at a time produces a linked list of height n. Collecting them, sorting once, and recursively taking the midpoint produces a perfectly balanced tree of height ⌈log₂ n⌉ in O(n log n) total, and needs no rotation logic at all.

The same asymmetry recurs throughout:

The B-tree row is easy to overlook and matters in practice: incremental insertion leaves nodes about 70% full, so a bulk-loaded index is meaningfully smaller and shallower. This is exactly why CREATE INDEX on an existing table produces a better index than the same rows inserted one at a time, and why REINDEX is a real optimization.

One further note on the example: build() sorts self.values in place and can be called twice with different results if add() is called in between. Builders that are consumed by build() should say so, or copy.

20.5 Adapter, Flyweight, and Policy

Three more that earn their place in collection code.

Adapter converts one interface to another. A max-heap from a min-heap by negating keys is the smallest possible example, and Python’s heapq (min-only)makes it a daily occurrence:

class MaxHeap:
    """Adapts heapq's min-heap into a max-heap by negating."""
    def __init__(self):
        self._h = []

    def push(self, value):
        heapq.heappush(self._h, -value)

    def pop(self):
        return -heapq.heappop(self._h)

Also: a deque adapted to a stack or a queue, and a Set adapted from a Map with dummy values, which is literally how Java’s HashSet is implemented.

Flyweight shares immutable state between many objects. String interning is the ubiquitous case: Java and Python both intern short strings so that a million occurrences of "active" cost one allocation. Tries share prefixes for the same reason, and the shared subtrees of persistent structures in Chapter 17 are flyweights created automatically by immutability.

Policy / strategy parameterizes a structure by a decision rather than baking it in. A comparator is the everyday example; so is a hash function, an eviction policy, or an allocator. C++’s std::map<K, V, Compare, Allocator> makes all of them template parameters, which is why the same container serves ascending order, descending order, and arena allocation with no runtime cost.

20.6 Choosing a Pattern

The pattern that applies to all of them: an abstraction over a data structure hides the layout but does not hide the cost. A List interface backed by a linked list and one backed by an array have identical signatures and completely different performance, and code written against the interface will silently get whichever it is handed. This is the practical reason C++ names std::vector and std::list distinctly instead of offering one List, and the reason Java’s List interface has been a recurring source of accidental O(n²) loops. get(i) in a loop over a LinkedList is quadratic and looks exactly like the linear version.

Abstract the interface. Document the cost.

Where this connects

• Chapter 22: Practical Considerations. The practical judgment these patterns support
• Chapter 6: Tree Fundamentals and Binary Trees. The composite and iterator patterns in their original setting

Chapter 21: Algorithm Design Using Data Structures

Algorithm design is usually taught as a catalog of paradigms and data structures as a separate catalog of containers. They are not separate. Each paradigm is defined by a specific bookkeeping problem, and the paradigm becomes practical exactly when a structure solves that bookkeeping in the right complexity.

Dijkstra’s algorithm is the cleanest demonstration. The algorithm (repeatedly settle the nearest unsettled vertex)is unchanged since 1956. Its complexity is entirely a property of the structure answering “which is nearest?”:

Same algorithm, three complexities. This chapter reads each paradigm that way: what does it need to remember, and which structure remembers it best?

21.1 Divide and Conquer

Use data structures to divide problems:

• Quicksort: Partition around pivot
• Merge sort: Divide at midpoint, merge sorted halves
• Binary search: Divide search space in half

Divide and conquer splits a problem into independent subproblems, solves them recursively, and combines the results. Its bookkeeping need is the recursion itself, which is why the stack from Chapter 5 is the paradigm’s implicit data structure. Every recursive call is a stack frame, and converting a recursive algorithm to an iterative one always means making that stack explicit.

Cost follows the Master Theorem: for T(n) = a·T(n/b) + f(n), compare f(n) against n^(log_b a). The three sorts above are the three cases in miniature. Merge sort is T(n) = 2T(n/2) + O(n) = O(n log n), binary search is T(n) = T(n/2) + O(1) = O(log n).

The structural insight worth carrying: the split and the combine trade off against each other. Merge sort splits trivially at the midpoint and pays in the merge. Quicksort pays in the partition and combines for free. Same total, different placement, and it is why quicksort sorts in place while merge sort needs O(n) scratch space.

Where a structure changes the answer outright:

• Segment trees (Chapter 23) are divide-and-conquer made persistent. Rather than re-splitting per query, the split is stored once as a tree and reused, turning O(n) range queries into O(log n).
• Karatsuba multiplication and Strassen’s algorithm win by reducing the number of subproblems (3 instead of 4, 7 instead of 8)so the branching factor a drops and the exponent falls with it.
• Deep recursion on user-controlled input is a stack-overflow bug. An explicit stack is not just a style preference.

21.2 Dynamic Programming

Optimal substructure + overlapping subproblems:

• Use memoization (hash table)
• Tabulation (array)

Dynamic programming applies when subproblems overlap: the case where plain divide and conquer recomputes the same work exponentially many times. Its bookkeeping need is a map from subproblem to answer, and the choice of map is the whole implementation decision.

Memoization (top-down) uses a hash table, recursion, and computes only reachable subproblems. Tabulation (bottom-up) uses an array, iteration, and computes all of them. The tradeoff is concrete: memoization skips unreachable states, which matters when the state space is sparse; tabulation has no recursion overhead and far better cache locality, which usually makes it faster when the state space is dense.

# Memoized: sparse state space, natural recursion, hash table lookup per call
@lru_cache(maxsize=None)
def lcs(i, j):
    if i == 0 or j == 0:
        return 0
    if a[i-1] == b[j-1]:
        return 1 + lcs(i-1, j-1)
    return max(lcs(i-1, j), lcs(i, j-1))

# Tabulated with rolling rows: O(min(m, n)) space instead of O(m·n)
def lcs_table(a, b):
    if len(b) > len(a):
        a, b = b, a                       # keep the inner dimension small
    prev = [0] * (len(b) + 1)
    for i in range(1, len(a) + 1):
        cur = [0] * (len(b) + 1)
        for j in range(1, len(b) + 1):
            cur[j] = 1 + prev[j-1] if a[i-1] == b[j-1] else max(prev[j], cur[j-1])
        prev = cur
    return prev[len(b)]

The rolling-row trick in the second version is the most broadly useful DP optimization there is: if a row depends only on the previous row, only two rows need to exist. An O(m·n) table becomes O(min(m,n)) space. Sequence alignment on genomes is feasible because of this.

Structures that change what DP can do:

• Monotonic deque: sliding-window maximum in O(1) amortized, turning an O(n·k) DP into O(n). The basis of the sliding-window-maximum optimization.
• Convex hull trick / Li Chao tree, when transitions have the form min(m·x + b), maintaining the lower envelope of lines drops an O(n²) DP to O(n log n).
• Fenwick tree (Chapter 23), when a transition sums over a prefix of previous states, prefix sums in O(log n) beat re-scanning in O(n).
• Bitsets. Subset-sum over n items and capacity W runs in O(nW/64) rather than O(nW), a 64× constant-factor win that regularly decides feasibility.

21.3 Greedy Algorithms

Make locally optimal choices:

• Huffman coding: Greedy tree building
• Dijkstra’s: Greedy shortest path
• Kruskal’s: Greedy MST

A greedy algorithm commits to the locally best choice and never reconsiders. Its bookkeeping need is “what is the best remaining option?”, asked repeatedly, which is precisely the priority queue’s interface. That is not a coincidence; it is why heaps appear in nearly every greedy algorithm.

Look at the three examples through their structures:

Kruskal’s is the interesting row, because its bookkeeping is not “what’s cheapest” (sorting answers that once)but “would this edge create a cycle?” Union-find answers it in near-constant amortized time, α(n), and without union-find the cycle check would be a graph traversal per edge and the algorithm would be O(E·V). A different question needs a different structure.

Greedy is only correct when the problem has the right structure, and that is a genuine mathematical condition, not a hopeful assumption. The matroid property guarantees it. Kruskal’s is correct because forests of a graph form a matroid. Absent such a property, greedy produces plausible wrong answers: it fails on 0/1 knapsack, on set cover (though it gives a ln n approximation), and on shortest paths with negative edges, which is exactly why Dijkstra requires non-negative weights. A greedy algorithm that is nearly right is often worse than an obviously wrong one, because nobody notices.

21.4 Backtracking

Systematic search with pruning:

• Use stack to track state
• Prune when impossible

Backtracking explores a decision tree depth-first, abandoning a branch as soon as it cannot lead to a solution. Its bookkeeping need is the current partial state, cheaply undoable, and the emphasis belongs on undoable, because the difference between a fast solver and a hopeless one is usually the cost of undoing a move.

The naive approach copies the state at each node, costing O(state) per branch. The right approach mutates and reverses:

def solve(board, row, cols, diag1, diag2):
    """N-Queens. Sets give O(1) conflict checks; undo is symmetric with do."""
    if row == len(board):
        return True
    for col in range(len(board)):
        if col in cols or (row - col) in diag1 or (row + col) in diag2:
            continue                                    # prune
        cols.add(col); diag1.add(row - col); diag2.add(row + col)   # do
        board[row] = col
        if solve(board, row + 1, cols, diag1, diag2):
            return True
        cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)  # undo
    return False

The three sets are the data-structure decision. Checking conflicts by scanning previously placed queens is O(n) per candidate; the sets make it O(1). Same search tree, different constant, and the constant is what makes n = 20 tractable.

Structures that make backtracking practical:

• Bitmasks replace those sets entirely for small n. cols | diag1 | diag2 in three integers, with conflict-checking and undo as single instructions. This is the standard fast N-Queens.
• Dancing Links (DLX): Knuth’s doubly-linked-list technique for exact cover, where removing and restoring a row or column are both O(1) pointer updates. It is the fastest known general Sudoku and pentomino solver, and it exists entirely because of how cheap its undo is.
• Union-find with rollback (Chapter 23) provides undoable connectivity for search over graph states.
• Trie: in word search and Boggle solvers, a trie prunes the moment a prefix cannot extend to any word, which collapses the search space dramatically.

Constraint propagation deserves mention as the general principle: the more work you do to detect a dead end early, the smaller the tree. This is why SAT solvers spend most of their time in propagation rather than search.

21.5 Randomized Algorithms

Probabilistic techniques:

• Quicksort (random pivot)
• Hash tables (random hash functions)
• Skip lists (random levels)

Randomization buys two distinct things, and conflating them is a common confusion:

Las Vegas algorithms are always correct, with running time that varies. Randomized quicksort always sorts, and is O(n log n) expected. Monte Carlo algorithms have fixed running time and may be wrong: a Bloom filter always answers in O(k), and sometimes answers wrongly.

The unifying purpose across all three examples is defeating adversarial input. Deterministic quicksort with a fixed pivot has an O(n²) input, and it is easy to construct, this was a real denial-of-service vector. Deterministic hashing has a collision-flooding input, which was a widely exploited DoS against web frameworks in 2011. Randomization means the adversary cannot construct a bad input in advance, because the bad input depends on choices not yet made.

Skip lists deserve a closer look because they show randomization buying something beyond speed. A skip list and a red-black tree are both O(log n), but the skip list gets there with coin flips instead of rotations, and since insertion touches only a few forward pointers rather than rebalancing a region, skip lists are far easier to make concurrent, as Chapter 18 discusses. Randomness bought simplicity and locality, and concurrency came along with them.

Two practical cautions. First, “random” must mean unpredictable to an adversary: seeding a hash function with a fixed constant, or with the process start time, reintroduces exactly the attack you were defending against. Second, expected-case bounds say nothing about any individual run. A randomized quicksort can be quadratic, just not reliably, and a system with hard latency requirements may need a guaranteed bound instead.

21.6 Choosing a Paradigm

The diagnostic question for each:

And the thread running through all of them: identify the question the algorithm asks over and over, then pick the structure that answers that question fastest. Dijkstra asks “which is nearest.” Kruskal asks “would this cycle.” DP asks “have I computed this.” Backtracking asks “can this branch still work.” Get the question right and the structure is usually obvious; get it wrong and no amount of optimization will help.

Where this connects

• Chapter 9: Heaps and Priority Queues. The priority queue behind every greedy algorithm
• Chapter 11: Graphs—Modeling Relationships. The graph algorithms these paradigms produce

Chapter 22: Practical Considerations

Everything up to here has been about what structures are. This chapter is about the decisions you actually make on a Tuesday afternoon: which one to reach for, what your language already gives you, what to do when it’s too slow, and how to find the bug when it’s wrong.

22.1 Choosing the Right Structure

Questions to ask:

1. What operations are most frequent?
2. What is the access pattern?
3. How large is the data?
4. What are the memory constraints?
5. Is thread safety required?

Those five questions are the right ones. Here is how to actually use them.

Start with question 1, and be specific about proportions. “I need lookups and inserts” is not an answer; “99% lookups, 1% inserts, no iteration” is. The ratio decides everything. A sorted array beats a hash table for a read-mostly set that fits in cache, and loses catastrophically the moment writes are frequent.

Question 2 is the one people skip and shouldn’t. Sequential access and random access are different problems, and Chapter 16 explains why the gap is 10–100×, not 10–20%. Ask specifically: do I ever need the elements in order? That single question separates hash tables from trees, and it is the most common source of a wrong initial choice: people reach for a hash map, then discover six months later that they need ordered iteration.

Question 3 changes which model applies. Under ~1,000 elements, constant factors dominate and a linear scan of an array frequently beats every “better” structure. It is one cache line at a time with perfect prefetching, and there is no hashing or pointer-chasing. Above what fits in RAM, the external memory model applies and B-trees or LSM trees are the only serious options.

A decision table for the common cases:

Question 5 deserves a warning. “Is thread safety required?” is often answered too fast, in both directions. Wrapping every structure in a lock because the application is multithreaded is how you get a program that is slower than the single-threaded version. Conversely, a structure reachable from two threads without synchronization is broken even if it has never visibly failed. The best answer is usually to avoid sharing at all: see Chapter 18.

22.2 Language-Specific Collections

What matters is what those names are actually implemented as, because the names hide real differences:

Three practical notes that catch people repeatedly:

• Go randomizes map iteration order on purpose, so that code cannot come to depend on it. If you need order, sort the keys.
• Rust’s default hasher is SipHash, chosen to resist collision attacks, and it is measurably slower than a non-cryptographic hash. For internal maps with trusted keys, FxHashMap is often 2× faster.
• C++ std::list is nearly always a mistake. The textbook case for a linked list (cheap insertion in the middle)loses to std::vector at surprisingly large n, because finding the insertion point requires a traversal and the traversal is cache-hostile. Measure before believing otherwise.

22.3 Performance Optimization

• Profiling first: Don’t optimize without measuring
• Cache awareness: Sequential access > random access
• Memory pools: Reduce allocation overhead
• Object pooling: Reuse frequently allocated objects

Profile first, and profile the right thing. A wall-clock profiler tells you where time goes; it does not tell you why. If a function is slow and the arithmetic is trivial, the answer is usually memory, and you need hardware counters to see it:

perf stat -e cache-misses,cache-references,instructions,cycles ./program

An instructions-per-cycle figure below ~1.0 with a high cache-miss rate means the CPU is waiting on memory, and no amount of algorithmic micro-tuning will help, the layout is the problem. Above ~2.0 IPC, you are compute-bound and the algorithm is the thing to change. This single distinction redirects more optimization effort than any other measurement.

The optimization ladder, roughly in order of payoff per unit of effort:

1. Better algorithm or structure. O(n²) → O(n log n) beats every constant-factor trick combined. This is where the leverage is, and the rest of this book is about it.
2. Better memory layout. Struct-of-arrays over array-of-structs; contiguous over pointer-chasing; shrink the hot struct so more fits per cache line. Often 2–10×.
3. Fewer allocations. Pre-size containers (reserve, make([]T, 0, n)). Reuse buffers. Arena-allocate objects with a shared lifetime. Allocation is rarely the headline cost, but allocation churn wrecks locality and GC pause times.
4. Batching. Amortize per-operation overhead, one bulk insert instead of n inserts, one syscall instead of n.
5. Micro-optimization. Branch elimination, SIMD, intrinsics. Real, but last, and easily undone by the next compiler version.

On object pooling specifically: it is a genuine win for expensive-to-construct objects (database connections, threads, large buffers) and frequently a net loss for cheap ones in a garbage-collected language. Modern generational GCs allocate by bumping a pointer and collect short-lived objects nearly for free; a pool converts those into long-lived objects that survive into the old generation and must be traced on every major collection. Pool connections, not integers.

On premature pessimization, which is the more common error than premature optimization: choosing an O(n) structure where an O(1) one was equally convenient, copying a large object where a reference would do, or building a string in a loop with +=. None of these are “optimizations” to skip. They are defaults to get right the first time.

22.4 Debugging Data Structure Bugs

• Invariants: Check them during development
• Visualization: Draw the structure
• Testing: Property-based testing (QuickCheck)
• Assertions: Validate preconditions and postconditions

Data structure bugs have a characteristic signature: the structure is silently wrong long before anything visibly fails. A corrupted red-black tree keeps answering queries: it just answers some of them incorrectly, and the crash comes later, somewhere else. This is why the techniques below emphasize detection near the cause rather than debugging at the point of failure.

Write the invariant checker first. For every structure, there is a predicate that must hold after every operation. Write it as code, not as a comment:

def check_bst(node, lo=float('-inf'), hi=float('inf')):
    """Every BST bug this catches would otherwise surface as a wrong query."""
    if node is None:
        return True
    if not (lo < node.key < hi):
        return False
    return (check_bst(node.left, lo, node.key)
            and check_bst(node.right, node.key, hi))

def check_heap(a, i=0):
    l, r = 2*i + 1, 2*i + 2
    for c in (l, r):
        if c < len(a) and (a[i] > a[c] or not check_heap(a, c)):
            return False
    return True

Note that check_bst must thread bounds down the recursion. The version that only compares each node to its immediate children is the classic wrong answer: it accepts trees that violate the BST property across subtrees.

Then run the checker after every mutation in debug builds:

def insert(self, key):
    self._insert(key)
    assert self._check_invariants(), f"invariant broken inserting {key}"

This turns a bug that would surface a thousand operations later into one that surfaces on the operation that caused it. For a red-black tree, check all five properties; for a B-tree, check occupancy bounds and uniform leaf depth; for union-find, check that no parent chain cycles.

Property-based testing is the highest-value testing technique for this domain, because data structure correctness is naturally expressible as properties, and random generation finds the edge cases you did not think of: empty, single element, duplicates, exactly-at-capacity:

from hypothesis import given, strategies as st

@given(st.lists(st.integers()))
def test_matches_reference(items):
    """The structure must behave identically to an obviously-correct model."""
    mine, reference = MyBST(), set()
    for x in items:
        mine.insert(x); reference.add(x)
    assert sorted(mine.in_order()) == sorted(reference)

@given(st.lists(st.integers()), st.integers())
def test_search_agrees(items, probe):
    mine = MyBST()
    for x in items:
        mine.insert(x)
    assert mine.contains(probe) == (probe in items)

That first pattern (model-based testing against a simple, obviously-correct reference implementation)is the most effective single technique for validating a data structure. Your red-black tree should behave exactly like a sorted list; your LRU cache should behave exactly like an ordered dict with manual eviction. The reference can be absurdly slow; it only has to be right.

Hypothesis (Python), QuickCheck (Haskell), proptest (Rust), and jqwik (Java) all shrink failing cases automatically, so a failure on a 500-element list is reported as the 3-element list that actually breaks it.

Visualize when the invariant checker says “broken” but not why. Graphviz output is about ten lines of code and worth every one:

def to_dot(node, out):
    if node is None:
        return
    for child, side in ((node.left, 'L'), (node.right, 'R')):
        if child:
            out.append(f'  "{node.key}" -> "{child.key}" [label="{side}"];')
            to_dot(child, out)

For memory bugs (use-after-free, double-free, buffer overruns in hand-written C structures)reach for the sanitizers rather than reasoning: -fsanitize=address and -fsanitize=undefined find in seconds what code review misses for weeks. For concurrent structures, -fsanitize=thread, Java’s JCStress, or Rust’s loom are effectively mandatory; a race that has not manifested in testing is not a race that does not exist.

A checklist for the specific bug classes that recur:

That last row is worth internalizing. Sorted input is the worst case for a naive BST and for quicksort with a fixed pivot, and real-world data arrives sorted far more often than random test data does: by timestamp, by ID, by insertion order. Test with sorted, reverse-sorted, and all-identical inputs deliberately.

Where this connects

• Chapter 16: External Memory and Cache-Oblivious Structures. Why the profiler says memory and not arithmetic
• Chapter 25: Complete Selection Guide and Complexity Reference. The selection matrix in reference form

Volume IV: Competitive Programming and Research-Grade Structures

Chapters

• Chapter 23: Advanced Competitive Programming Data Structures
• Chapter 24: Research-Grade Data Structures
• Chapter 25: Complete Selection Guide and Complexity Reference

Competitive-programming resources and the research papers behind these structures are collected in the Bibliography.

A note on numbering: an earlier draft had a Chapter 26 here, an extended bibliography. Its content was folded into the appendices, and the chapter numbers were kept stable so published links do not break — Volume V therefore begins at Chapter 27.

Chapter 23: Advanced Competitive Programming Data Structures

23.1 Introduction to Competitive Programming Data Structures

Competitive programming demands data structures that excel under specific constraints: fast operations, minimal memory, and elegant implementation. While the foundational structures covered earlier serve as building blocks, competitive programming has developed specialized structures optimized for algorithmic challenges.

This chapter covers structures essential for International Olympiad in Informatics (IOI), International Collegiate Programming Contest (ICPC), and Codeforces/Topcoder competitions. These structures often sacrifice generality or worst-case guarantees for practical performance and competitive implementation.

23.2 Segment Trees with Lazy Propagation

Conceptual Foundation

A segment tree is a binary tree that represents an array segment, enabling efficient range queries and updates. Lazy propagation defers updates until necessary, dramatically improving performance for range modifications.

Core Properties:

• Represents array in binary tree form
• Each node stores aggregate of its segment (sum, min, max, etc.)
• Height: O(log n)
• Space: O(n) with 4n safe upper bound

Mechanism: Range Query with Lazy Propagation

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self.lazy = [0] * (4 * self.n)
        self._build(1, 0, self.n - 1, arr)

    def _build(self, node, l, r, arr):
        if l == r:
            self.tree[node] = arr[l]
        else:
            mid = (l + r) // 2
            self._build(node * 2, l, mid, arr)
            self._build(node * 2 + 1, mid + 1, r, arr)
            self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def _push(self, node, l, r):
        """Push lazy values to children"""
        if self.lazy[node] != 0:
            mid = (l + r) // 2
            # Apply to left child
            self.tree[node * 2] += self.lazy[node] * (mid - l + 1)
            self.lazy[node * 2] += self.lazy[node]
            # Apply to right child
            self.tree[node * 2 + 1] += self.lazy[node] * (r - mid)
            self.lazy[node * 2 + 1] += self.lazy[node]
            self.lazy[node] = 0

    def range_update(self, node, l, r, ql, qr, val):
        if ql <= l and r <= qr:
            self.tree[node] += val * (r - l + 1)
            self.lazy[node] += val
            return

        if r < ql or l > qr:
            return

        self._push(node, l, r)
        mid = (l + r) // 2
        self.range_update(node * 2, l, mid, ql, qr, val)
        self.range_update(node * 2 + 1, mid + 1, r, ql, qr, val)
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def range_query(self, node, l, r, ql, qr):
        if ql <= l and r <= qr:
            return self.tree[node]

        if r < ql or l > qr:
            return 0

        self._push(node, l, r)
        mid = (l + r) // 2
        return (self.range_query(node * 2, l, mid, ql, qr) +
                self.range_query(node * 2 + 1, mid + 1, r, ql, qr))

Complexity Analysis

Advanced Variants

Merge Sort Tree: For k-th smallest queries, store sorted vectors at each node.

Segment Tree Beats: For range min/max updates with constraints.

Dynamic Segment Tree: For values outside initial range, create nodes on demand.

23.3 Fenwick Trees (Binary Indexed Trees)

Conceptual Foundation

A Fenwick tree, invented by Boris Ryabko in 1989 and popularized by Peter Fenwick, provides O(log n) prefix operations with minimal memory. It’s simpler than segment trees for prefix-sum based queries.

Key Insight: Use binary representation to represent ranges as sums of power-of-two sized blocks.

Mechanism

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, idx, delta):
        """Add delta at position idx (1-indexed)"""
        while idx <= self.n:
            self.bit[idx] += delta
            idx += idx & (-idx)

    def prefix_sum(self, idx):
        """Sum of [1, idx]"""
        result = 0
        while idx > 0:
            result += self.bit[idx]
            idx -= idx & (-idx)
        return result

    def range_sum(self, l, r):
        """Sum of [l, r]"""
        return self.prefix_sum(r) - self.prefix_sum(l - 1)

    def find_kth(self, k):
        """Find smallest idx with prefix_sum >= k"""
        idx = 0
        bit_mask = 1 << (self.n.bit_length() - 1)
        while bit_mask:
            t_idx = idx + bit_mask
            if t_idx <= self.n and self.bit[t_idx] < k:
                idx = t_idx
                k -= self.bit[t_idx]
            bit_mask >>= 1
        return idx + 1

2D Fenwick Tree

class BIT2D:
    def __init__(self, n, m):
        self.n, self.m = n, m
        self.bit = [[0] * (m + 1) for _ in range(n + 1)]

    def add(self, x, y, delta):
        i = x
        while i <= self.n:
            j = y
            while j <= self.m:
                self.bit[i][j] += delta
                j += j & (-j)
            i += i & (-i)

    def prefix_sum(self, x, y):
        result = 0
        i = x
        while i > 0:
            j = y
            while j > 0:
                result += self.bit[i][j]
                j -= j & (-j)
            i -= i & (-i)
        return result

23.4 Heavy-Light Decomposition

Conceptual Foundation

Heavy-Light Decomposition (HLD), introduced by Sleator and Tarjan, enables O(log n) path queries on trees by decomposing the tree into chains where heavy edges form continuous segments.

Key Concepts:

• Heavy edge: Edge to child with largest subtree
• Light edge: All other edges
• Heavy path: Path following heavy edges
• Decomposition ensures O(log n) chains per path

Mechanism

class HeavyLightDecomposition:
    def __init__(self, n, edges):
        self.n = n
        self.adj = [[] for _ in range(n)]
        for u, v in edges:
            self.adj[u].append(v)
            self.adj[v].append(u)

        self.parent = [-1] * n
        self.depth = [0] * n
        self.size = [0] * n
        self.heavy = [-1] * n
        self.head = [0] * n
        self.pos = [0] * n
        self.cur_pos = 0

        self._dfs(0)
        self._decompose(0, 0)

    def _dfs(self, v):
        self.size[v] = 1
        max_size = 0
        for u in self.adj[v]:
            if u != self.parent[v]:
                self.parent[u] = v
                self.depth[u] = self.depth[v] + 1
                self._dfs(u)
                self.size[v] += self.size[u]
                if self.size[u] > max_size:
                    max_size = self.size[u]
                    self.heavy[v] = u

    def _decompose(self, v, h):
        self.head[v] = h
        self.pos[v] = self.cur_pos
        self.cur_pos += 1
        if self.heavy[v] != -1:
            self._decompose(self.heavy[v], h)
        for u in self.adj[v]:
            if u != self.parent[v] and u != self.heavy[v]:
                self._decompose(u, u)

    def query_path(self, u, v, segtree):
        """Query on path u-v using segment tree"""
        result = 0
        while self.head[u] != self.head[v]:
            if self.depth[self.head[u]] < self.depth[self.head[v]]:
                u, v = v, u
            head_u = self.head[u]
            result += segtree.range_query(self.pos[head_u], self.pos[u])
            u = self.parent[head_u]
        # Same head
        if self.depth[u] > self.depth[v]:
            u, v = v, u
        result += segtree.range_query(self.pos[u], self.pos[v])
        return result

Applications

23.5 Link-Cut Trees

Conceptual Foundation

Link-cut trees, invented by Sleator and Tarjan in 1983, support dynamic forest operations: linking trees, cutting edges, and querying aggregates on paths, all in O(log n) amortized time.

Operations:

• link(u, v): Connect u as child of v
• cut(u): Remove edge between u and parent
• evert(u): Make u the root
• path_query(u, v): Aggregate on u-v path

Mechanism

class LinkCutTree:
    class Node:
        def __init__(self, val):
            self.val = val
            self.left = None
            self.right = None
            self.parent = None
            self.rev = False
            self.sum = val

    def _push(self, x):
        if x and x.rev:
            x.left, x.right = x.right, x.left
            if x.left: x.left.rev ^= True
            if x.right: x.right.rev ^= True
            x.rev = False

    def _update(self, x):
        x.sum = x.val
        if x.left: x.sum ^= x.left.sum
        if x.right: x.sum ^= x.right.sum

    def _rotate(self, x):
        p = x.parent
        g = p.parent
        if p == p.parent.left:
            p.parent.left = x
        else:
            p.parent.right = x
        x.parent = g.parent
        if x == p.left:
            p.left = x.right
            if x.right: x.right.parent = p
            x.right = p
        else:
            p.right = x.left
            if x.left: x.left.parent = p
            x.left = p
        p.parent = x
        self._update(p)
        self._update(x)

    def _splay(self, x):
        stack = []
        y = x
        stack.append(y)
        while y.parent:
            stack.append(y.parent)
            y = y.parent
        while stack:
            self._push(stack.pop())
        while x.parent:
            self._push(x.parent)
            if x == x.parent.left:
                if x.parent.parent and x.parent == x.parent.parent.left:
                    self._rotate(x.parent)
                self._rotate(x)
            else:
                if x.parent.parent and x.parent == x.parent.parent.right:
                    self._rotate(x.parent)
                self._rotate(x)

    def access(self, x):
        last = None
        while x:
            self._splay(x)
            x.right = last
            self._update(x)
            last = x
            x = x.parent
        return last

    def make_root(self, x):
        self.access(x)
        self._splay(x)
        x.rev ^= True

    def link(self, x, y):
        self.make_root(x)
        x.parent = y

    def cut(self, x, y):
        self.make_root(x)
        self.access(y)
        self._splay(y)
        if y.left == x:
            y.left.parent = None
            y.left = None
            self._update(y)

    def query_path(self, x, y):
        self.make_root(x)
        self.access(y)
        self._splay(y)
        return y.sum

23.6 Mo’s Algorithm

Conceptual Foundation

Mo’s algorithm answers offline range queries in O((n + q)√n) by reordering queries to minimize pointer movement. It’s particularly effective for queries with additive functions.

Key Insight: Sort queries by block of L, then by R for optimal pointer movement.

Mechanism

class MoSolver:
    def __init__(self, arr, queries):
        self.arr = arr
        self.queries = queries
        self.block_size = int(len(arr) ** 0.5)
        self.answers = [0] * len(queries)
        self._process()

    def _process(self):
        # Sort queries: block by L, then by R (alternating for optimization)
        self.queries.sort(key=lambda x: (
            x.l // self.block_size,
            x.r if (x.l // self.block_size) % 2 == 0 else -x.r
        ))

        cur_l, cur_r = 0, -1
        for q in self.queries:
            while cur_l > q.l:
                cur_l -= 1
                self._add(cur_l)
            while cur_r < q.r:
                cur_r += 1
                self._add(cur_r)
            while cur_l < q.l:
                self._remove(cur_l)
                cur_l += 1
            while cur_r > q.r:
                self._remove(cur_r)
                cur_r -= 1
            self.answers[q.idx] = self._get_answer()

    def _add(self, idx):
        # Update frequency and current answer
        pass

    def _remove(self, idx):
        # Update frequency and current answer
        pass

    def _get_answer(self):
        return 0

Variants

Mo’s on Trees: Use Euler tour to flatten tree into array.

3D Mo’s: Add time dimension for updates.

Mo’s with Rollback: For parallel binary search.

23.7 Suffix Automaton

Conceptual Foundation

A suffix automaton (SAM) recognizes all substrings of a string in O(n) construction time, with at most 2n-1 states. It’s a deterministic acyclic finite automaton.

Properties:

• Minimum DFA for all substrings
• Size ≤ 2n - 1
• Links form suffix links (longest proper suffix)

Mechanism

class SuffixAutomaton:
    def __init__(self):
        self.next = [dict()]  # state 0: initial
        self.link = [-1]
        self.len = [0]
        self.last = 0

    def extend(self, c):
        p = self.last
        cur = len(self.next)
        self.next.append(dict())
        self.len.append(self.len[p] + 1)
        self.link.append(0)

        while p >= 0 and c not in self.next[p]:
            self.next[p][c] = cur
            p = self.link[p]

        if p == -1:
            self.link[cur] = 0
        else:
            q = self.next[p][c]
            if self.len[p] + 1 == self.len[q]:
                self.link[cur] = q
            else:
                clone = len(self.next)
                self.next.append(self.next[q].copy())
                self.len.append(self.len[p] + 1)
                self.link.append(self.link[q])

                while p >= 0 and self.next[p].get(c) == q:
                    self.next[p][c] = clone
                    p = self.link[p]

                self.link[q] = self.link[cur] = clone

        self.last = cur
        return cur

Applications

23.8 Palindromic Tree (Eertree)

Conceptual Foundation

The Palindromic Tree, invented by Mikhail Rubinchik and later popularized, stores all distinct palindromic substrings. It uses two root nodes: odd length (-1) and even length (0).

Properties:

• O(n) construction
• O(n) distinct palindromes maximum
• Each node represents a palindrome

Mechanism

class PalindromicTree:
    class Node:
        def __init__(self, length, pos):
            self.length = length
            self.pos = pos  # ending position
            self.next = {}
            self.link = 0

    def __init__(self, s):
        self.s = s
        self.nodes = [self.Node(-1, -1), self.Node(0, -1)]
        self.nodes[0].link = 0
        self.nodes[1].link = 0
        self.last = 1
        self.size = 2
        self.num_pal = 0

        for i, c in enumerate(s):
            self._add_char(i, c)

    def _add_char(self, pos, c):
        cur = self.last
        while True:
            cur_len = self.nodes[cur].length
            if pos - cur_len - 1 >= 0 and self.s[pos - cur_len - 1] == c:
                break
            cur = self.nodes[cur].link

        if c in self.nodes[cur].next:
            self.last = self.nodes[cur].next[c]
            return

        new_node = self.Node(self.nodes[cur].length + 2, pos)
        self.nodes.append(new_node)
        self.nodes[cur].next[c] = self.size
        self.size += 1

        if new_node.length == 1:
            new_node.link = 1
        else:
            tmp = self.nodes[cur].link
            while True:
                if pos - self.nodes[tmp].length - 1 >= 0 and \
                   self.s[pos - self.nodes[tmp].length - 1] == c:
                    break
                tmp = self.nodes[tmp].link
            new_node.link = self.nodes[tmp].next[c]

        self.last = self.size - 1
        self.num_pal += 1

23.9 Wavelet Trees

Conceptual Foundation

Wavelet trees answer range quantile queries (k-th smallest) in O(log σ) where σ is alphabet size, using only O(n log σ) space. They recursively partition based on the most significant bit.

Key Operation: K-th smallest in subarray [l, r]

Mechanism

class WaveletTree:
    def __init__(self, arr, lo, hi):
        self.lo = lo
        self.hi = hi
        self.b = []

        if lo >= hi or not arr:
            return

        mid = (lo + hi + 1) // 2
        self.c = lo

        left_arr = []
        right_arr = []

        for x in arr:
            if x < mid:
                left_arr.append(x)
            else:
                right_arr.append(x)
            self.b.append(len(left_arr))

        self.left = WaveletTree(left_arr, lo, mid - 1)
        self.right = WaveletTree(right_arr, mid, hi)

    def kth(self, l, r, k):
        if l > r:
            return None
        if self.lo == self.hi:
            return self.lo

        in_left = self.b[r] - (self.b[l - 1] if l > 0 else 0)
        left_l = 1 if l == 0 else self.b[l - 1] + 1
        left_r = left_l + in_left - 1

        if k <= in_left:
            return self.left.kth(left_l, left_r, k)
        else:
            right_l = r - (self.b[r] - self.b[r - 1] if r > 0 else 0) - in_left + 1
            right_r = r - in_left
            return self.right.kth(right_l, right_r, k - in_left)

23.10 Li Chao Trees

Conceptual Foundation

Li Chao trees maintain dynamic line sets for point queries in O(log C) where C is coordinate range. They’re ideal for online convex hull trick scenarios.

Operations:

• Add line (insert)
• Query minimum at point

Mechanism

class LiChaoNode:
    def __init__(self, line=None):
        self.line = line  # (m, b) for y = mx + b
        self.left = None
        self.right = None

class LiChaoTree:
    def __init__(self, x_left, x_right):
        self.x_left = x_left
        self.x_right = x_right
        self.root = None

    def f(self, line, x):
        return line[0] * x + line[1]

    def add_line(self, line):
        self.root = self._add_line(self.root, self.x_left, self.x_right, line)

    def _add_line(self, node, l, r, new_line):
        if not node:
            return LiChaoNode(new_line)

        mid = (l + r) // 2
        left_is_better = self.f(new_line, l) < self.f(node.line, l)
        mid_is_better = self.f(new_line, mid) < self.f(node.line, mid)

        if mid_is_better:
            node.line, new_line = new_line, node.line

        if r == l:
            return node

        if left_is_better != mid_is_better:
            node.left = self._add_line(node.left, l, mid, new_line)
        else:
            node.right = self._add_line(node.right, mid + 1, r, new_line)

        return node

    def query(self, x):
        return self._query(self.root, self.x_left, self.x_right, x)

    def _query(self, node, l, r, x):
        if not node:
            return float('inf')
        if l == r:
            return self.f(node.line, x)
        mid = (l + r) // 2
        if x <= mid:
            return min(self.f(node.line, x),
                      self._query(node.left, l, mid, x))
        else:
            return min(self.f(node.line, x),
                      self._query(node.right, mid + 1, r, x))

23.11 Sparse Tables

Conceptual Foundation

Sparse tables answer static range queries in O(1) after O(n log n) preprocessing, but only for idempotent operations (min, max, gcd).

Limitation: Not for sum (not idempotent).

Mechanism

class SparseTable:
    def __init__(self, arr, op=min):
        self.n = len(arr)
        self.log = [0] * (self.n + 1)
        for i in range(2, self.n + 1):
            self.log[i] = self.log[i // 2] + 1

        self.k = self.log[self.n] + 1
        self.st = [[0] * self.n for _ in range(self.k)]
        self.st[0] = arr[:]

        for k in range(1, self.k):
            for i in range(self.n - (1 << k) + 1):
                self.st[k][i] = op(self.st[k-1][i],
                                   self.st[k-1][i + (1 << (k-1))])

    def query(self, l, r):
        j = self.log[r - l + 1]
        return min(self.st[j][l], self.st[j][r - (1 << j) + 1])

23.12 Cartesian Trees

Conceptual Foundation

A Cartesian tree maintains array order via inorder traversal while enforcing heap property. O(n) construction using monotonic stack.

Properties:

• Inorder traversal gives original array
• Heap property on values
• Unique for given array

Mechanism

def build_cartesian(arr):
    n = len(arr)
    parent = [-1] * n
    left = [-1] * n
    right = [-1] * n

    stack = []
    for i in range(n):
        last = -1
        while stack and arr[stack[-1]] > arr[i]:
            last = stack.pop()

        if stack:
            right[stack[-1]] = i
            parent[i] = stack[-1]

        if last != -1:
            parent[last] = i
            left[i] = last

        stack.append(i)

    root = stack[0] if stack else -1
    return root, parent, left, right

23.13 Sqrt Decomposition

Conceptual Foundation

Sqrt decomposition divides array into blocks of size √n, enabling O(√n) range queries. Simpler than segment trees but slower.

Mechanism

class SqrtDecomposition:
    def __init__(self, arr):
        self.arr = arr
        self.n = len(arr)
        self.block_size = int(self.n ** 0.5)
        self.n_blocks = (self.n + self.block_size - 1) // self.block_size
        self.block_sum = [0] * self.n_blocks
        self.block_min = [float('inf')] * self.n_blocks

        for i in range(self.n):
            b = i // self.block_size
            self.block_sum[b] += arr[i]
            self.block_min[b] = min(self.block_min[b], arr[i])

    def range_query(self, l, r):
        result = 0
        while l <= r:
            if l % self.block_size == 0 and l + self.block_size - 1 <= r:
                result += self.block_sum[l // self.block_size]
                l += self.block_size
            else:
                result += self.arr[l]
                l += 1
        return result

23.14 DSU with Rollback

Conceptual Foundation

DSU with rollback supports undoing union operations, essential for offline queries and divide-and-conquer approaches.

Mechanism

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.changes = []

    def find(self, x):
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            self.changes.append((-1, -1, -1))
            return

        if self.size[x] < self.size[y]:
            x, y = y, x

        self.changes.append((y, self.parent[y], self.size[x]))
        self.parent[y] = x
        self.size[x] += self.size[y]

    def snapshot(self):
        return len(self.changes)

    def rollback(self, state):
        while len(self.changes) > state:
            y, parent_y, size_x = self.changes.pop()
            if y == -1:
                continue
            x = self.parent[y]
            self.size[x] = size_x
            self.parent[y] = parent_y

Where this connects

• Chapter 21: Algorithm Design Using Data Structures. The paradigms these structures accelerate
• Chapter 25: Complete Selection Guide and Complexity Reference. The selection matrix for picking among them

Chapter 24: Research-Grade Data Structures

24.1 Introduction to Research-Grade Structures

Research-grade data structures push the boundaries of what is theoretically possible. They achieve remarkable space-time tradeoffs, often approaching information-theoretic lower bounds. These structures are essential for large-scale systems, specialized applications, and pushing the frontier of computer science.

24.2 Succinct Data Structures

Conceptual Foundation

Succinct data structures store information in space close to the theoretical minimum while supporting efficient operations. They achieve entropy-compressed space.

Space Bounds:

• Succinct: n·H₀ + O(n / log n) bits
• Compact: O(n log σ) bits
• Implicit: n + O(1) bits

Rank and Select

class SuccinctBitVector:
    def __init__(self, bits):
        self.bits = bits
        self.n = len(bits)
        self._build_rank()

    def _build_rank(self):
        self.rank_block = [0] * ((self.n + 63) // 64)
        for i in range(self.n):
            if self.bits[i]:
                self.rank_block[i // 64] += 1
        for i in range(1, len(self.rank_block)):
            self.rank_block[i] += self.rank_block[i - 1]

    def rank(self, i):
        """Count of 1s in [0, i]"""
        block = i // 64
        return self.rank_block[block] + bin(
            self.bits[block * 64: i + 1]
        ).count('1')

    def select(self, k):
        """Position of k-th 1"""
        lo, hi = 0, self.n - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if self.rank(mid) <= k:
                lo = mid + 1
            else:
                hi = mid
        return lo

24.3 Succinct Trees (LOUDS, BP, DFUDS)

Balanced Parentheses (BP)

Tree → balanced parentheses string where “(” means enter node, “)” means exit.

def find_close(bp, i):
    """Find matching ')' for '(' at i"""
    delta = -1
    while delta < 0:
        i += 1
        delta += 1 if bp[i] == '(' else -1
    return i

def find_open(bp, i):
    """Find matching '(' for ')' at i"""
    delta = 1
    while delta > 0:
        i += 1
        delta += 1 if bp[i] == '(' else -1
    return i - 1

LOUDS (Level-Order Unary Degree Sequence)

Level-order traversal with unary degree encoding. Each node: (degree times ‘(’) + ‘)’.

24.4 Wavelet Matrices

Conceptual Foundation

Wavelet matrices extend wavelet trees with better space utilization and dynamic alphabet support using bitmaps with rank/select.

Improvements over Wavelet Tree:

• No separate child arrays
• Better bit-level packing
• Same query complexity

24.5 FM-Index

Conceptual Foundation

The FM-Index (Ferragina-Manzini) is a compressed self-indexing text index using the Burrows-Wheeler Transform.

Key Components:

• BWT string
• Occurrence counts (compressed)
• Suffix array samples
• LF-mapping

def bwt(s):
    """Burrows-Wheeler Transform"""
    s = s + '$'
    suffixes = sorted(range(len(s)), key=lambda i: s[i:])
    return ''.join(s[i-1] for i in suffixes), suffixes

24.6 Cache-Oblivious Data Structures

Conceptual Foundation

Cache-oblivious structures achieve optimal performance without knowing cache size M or block size B. They work well across all memory hierarchy levels.

Key Idea: Optimal algorithms for all configurations simultaneously.

van Emde Boas Layout

Tree layout recursively:
VEB Layout of tree with height h:
- If h = 0: single node
- If h > 0: layout of left subtree of size 2^(h-1),
            then layout of right subtree of size 2^(h-1)

Search Complexity: O(log_B N) I/Os, optimal.

24.7 External Memory Data Structures

External Memory Model

Parameters: B (block size), M (memory size), D (disk latency).

Log-Structured Merge Trees

LSM trees (LevelDB, RocksDB, Cassandra) achieve write-optimized storage:

Levels: L0, L1, L2, ..., L_k
- Each level T times larger than previous
- Data flows: MemTable → L0 → L1 → ... → Lk
- Compaction merges sorted runs

24.8 Fully Persistent Data Structures

Persistence Types

Fat Nodes

Store modification logs at each node:

class FatNode:
    def __init__(self, value):
        self.value = value
        self.mod_log = []  # (time, field, old, new)
        self.left = None
        self.right = None

    def write(self, field, new_value, time):
        self.mod_log.append((time, field, getattr(self, field), new_value))
        setattr(self, field, new_value)

24.9 Conflict-Free Replicated Data Types (CRDTs)

Conceptual Foundation

CRDTs achieve eventual consistency in distributed systems without coordination. Operations commute, guaranteeing convergence.

G-Counter (Grow-only)

class GCounter:
    def __init__(self, node_id):
        self.counts = {node_id: 0}

    def increment(self):
        self.counts[self.node_id] += 1

    def merge(self, other):
        for node, count in other.items():
            self.counts[node] = max(self.counts.get(node, 0), count)

    def value(self):
        return sum(self.counts.values())

Common CRDT Types

24.10 Dynamic Graph Algorithms

Holm-de Lichtenberg-Thorup (HDnT)

Fully dynamic connectivity in O(log n):

class HDnTConnectivity:
    def __init__(self, n):
        self.n = n
        self.LOG = int(math.log2(n)) + 1
        self.levels = [[] for _ in range(self.LOG)]
        self.spanning_forests = [None] * self.LOG

Dynamic Shortest Paths

24.11 String B-Trees

B-trees optimized for string keys:

24.12 Fractional Cascading

Accelerate searches in layered structures:

def fractional_cascading_search(layers, query):
    """Search in multiple layers with caching"""
    pos = binary_search(layers[0], query)
    for i in range(1, len(layers)):
        # Use cached bounds from previous level
        cached_lower = layers[i-1].get_cached_lower(pos)
        pos = bounded_search(layers[i], query, cached_lower)
    return pos

Speedup: O(log n + k) vs O(Σ log n_i)

24.13 Melding Data Structures

Combine data structures efficiently:

24.14 Research Frontiers

Emerging Areas

Open Problems

1. Dynamic connectivity in true O(log n)?
2. Sub-logarithmic string operations?
3. Persistent arrays with O(1) space per version?
4. Cache-oblivious sorting optimal?

Where this connects

• Chapter 19: Emerging and Specialized Structures. Where this research is heading next
• Chapter 16: External Memory and Cache-Oblivious Structures. The cache-oblivious model several of these depend on

Chapter 25: Complete Selection Guide and Complexity Reference

25.1 Data Structure Selection Matrix

25.2 Complete Complexity Reference

Competitive Programming Structures

Two rows are easy to get wrong. DSU with rollback is O(log n), not O(α(n)). Undoing a union requires knowing exactly which parent pointers changed, and path compression rewrites pointers all along the path, so rollback DSU must use union by rank alone. You trade the inverse-Ackermann bound for the ability to undo. And Mo’s algorithm is offline: it answers q queries in O((n + q)√n) total, so the O(√n) is an amortized per-query share, not a bound on any individual query.

Research-Grade Structures

★ = amortized. H_k(T) is the k-th order empirical entropy of the text. The FM-index is compressed to the text’s own entropy, which is what “self-indexing” means: you can discard the original text and still reconstruct any substring.

25.3 Algorithm Design Patterns

Each paradigm is defined by a bookkeeping question it must answer repeatedly, and becomes practical when a structure answers that question fast enough. Chapter 21 develops this in full; the summary:

The recurring trap: greedy is only correct when the problem has the matroid property or an equivalent exchange argument. Without it, greedy produces plausible wrong answers, which is worse than obviously wrong ones, because they pass casual testing.

Where this connects

• Chapter 22: Practical Considerations. The practical version of this decision process

Volume V: Network and System Design Data Structures

The previous volumes established data structures as fundamental building blocks of computation. This volume reveals a profound truth: network topologies and system design patterns are simply data structures applied at scale. When you examine distributed systems, load balancers, CDN architectures, and routing protocols through the lens of data structures, patterns emerge. A routing table is a trie for network paths. Consistent hashing is a modified hash ring. A distributed message queue is a persistent FIFO with durability guarantees. This volume bridges the gap between academic data structures and production system design, showing how foundational structures compose into the complex systems that power the internet.

Chapters

• Chapter 27: Distributed Data Structures
• Chapter 28: Network Topology and Routing Data Structures
• Chapter 29: System Design as Data Structure Composition
• Chapter 30: Advanced System Patterns and Case Studies
• Chapter 31: Real-World Case Studies
• Chapter 32: Synthesis and Future Directions

Chapter 27: Distributed Data Structures

27.1 The Philosophy of Distributed Data

In single-machine computing, data structures operate on shared memory with uniform access times. Distributed computing shatters this model: data spans machines, networks have latency, and failures are not exceptions but expectations. Every distributed data structure must answer a fundamental question: how do we maintain the illusion of a single coherent data structure across a cluster of unreliable machines?

The CAP Theorem provides the theoretical foundation. In partitioned systems, you must choose between Consistency (all nodes see the same data) and Availability (every request receives a response). You cannot have both during network partitions. This trade-off shapes every distributed data structure.

PACELC extends CAP: if there is a partition (P), the system must choose between Availability (A) and Consistency (C). Else (E), even without partitions, the system must choose between Latency (L) and Consistency (C). A Dynamo-style system chooses L over C; a Bigtable-style system chooses C over L.

27.2 Distributed Hash Tables (DHT)

A DHT extends the hash table concept across a cluster. The key insight: map both data items and nodes onto the same hash space, creating a self-organizing overlay network.

Chord Protocol

Chord assigns each node and key an m-bit identifier using consistent hashing. Each node maintains a finger table of size O(log N), allowing lookups in O(log N) hops.

Identifier calculation:
node_id = hash(node_ip)
key_id = hash(key)

Successor operation:
successor(id) = first node whose id >= id in the identifier circle

Finger table construction: The i-th entry of node n contains the successor of (n + 2^(i-1)) mod 2^m, for i = 1..m. This enables exponential jumps across the identifier space.

Join operation: A new node asks a known node to find its successor, then updates predecessor’s finger table and notifies its successor to adjust.

Stabilization: Periodically, nodes verify their successor’s predecessor and fix finger table entries to maintain correctness despite churn.

Kademlia

Kademlia uses a XOR metric for distance, enabling more efficient lookups. The key properties:

XOR Distance: d(a,b) = a ⊕ b. This distance is symmetric and satisfies the triangle inequality, enabling simpler routing.

Node buckets: Each node maintains k buckets for each prefix length. Buckets are prioritized by least-recently-seen nodes, ensuring long-lived nodes stay in routing tables.

Lookup algorithm: Start with the closest node from own buckets. Parallel query α closest nodes at each step (typically α = 3). Terminate when no node in the queried set is closer than current best.

Republishing: Keys are republished periodically with longer expiration times. Original publishers become responsible for refreshing, preventing orphaned keys.

Apache Cassandra’s Partitioner

Cassandra uses consistent hashing with virtual nodes (vnodes). Each node owns multiple token ranges, enabling:

• Load balancing: Fine-grained distribution across heterogeneous hardware
• Easier cluster expansion: New nodes claim portions of existing ranges
• Mechanical sympathy: Sequential ranges for sequential access patterns

The Murmur3 partitioner hashes keys to 64-bit tokens. The ring divides this space into contiguous ownership zones.

27.3 Consistent Hashing

Traditional hashing maps N items to K servers with N/K average load. But adding or removing servers requires rehashing almost all items. Consistent hashing minimizes disruption.

Basic Algorithm

1. Map both servers and keys to points on a circular hash space (0 to 2^32-1)
2. Each key is assigned to the nearest server in the clockwise direction
3. Virtual nodes (replicas) distribute load more evenly

Problem: Uneven distribution when nodes join/leave. Solution: introduce virtual nodes (100-200 per physical node), creating finer-grained ownership.

Server placement:
server_i = hash("server_" + i + "_replica_1")
server_i = hash("server_" + i + "_replica_2")
...
server_i = hash("server_" + i + "_replica_v")

Key placement:
key_assigned_to = first_server where server_token > key_token

Consistent Hashing with Bounded Load

Amazon Dynamo improves on basic consistent hashing with load bounds:

1. Each node gets a “capacity” number representing load responsibility
2. When a node receives too many keys, it splits its range with a neighbor
3. System guarantees load within a factor of (2k/k+1) of ideal

27.4 Distributed Snapshots and State Machine Replication

Replicating state across machines requires capturing consistent global states despite concurrent operations.

Chandy-Lamport Algorithm

Designed for distributed snapshot collection without process coordination:

1. Initiator sends marker on all outgoing channels
2. When a process receives marker on channel C:
   • Record local state (marker is first from C)
   • Forward marker on all other outgoing channels
   • Start recording messages on channel C
3. When all channels have received markers, snapshot is complete

Causality guarantee: The algorithm captures a consistent cut where each process’s recorded state occurred at the same logical time across the system.

State Machine Replication

A deterministic state machine, combined with replicated logs of identical commands, guarantees consistent replicas. Key requirements:

• Determinism: Same initial state + same operations = same final state
• Atomicity: No partial command execution
• Ordering: Total order across all replicas

Paxos and Raft are consensus protocols that implement replicated logs. Raft’s key innovation: decomposing consensus into leader election, log replication, and safety.

Raft Log Entry:
{
    term: number,        // When entry was created
    index: number,       // Position in log
    command: object     // State machine command
}

27.5 CRDTs in Distributed Systems

Conflict-free Replicated Data Types (CRDTs) enable eventual consistency without coordination. They guarantee convergence regardless of operation order.

Operation-based CRDTs

Each operation carries metadata enabling correct merge:

G-Counter (Grow-only Counter):

class GCounter:
    def __init__(self):
        self.state = {}  # node_id -> count

    def increment(self, node_id):
        self.state[node_id] += 1

    def merge(self, other):
        for node_id, count in other.state.items():
            self.state[node_id] = max(self.state.get(node_id, 0), count)

    def value(self):
        return sum(self.state.values())

LWW-Register (Last-Write-Wins Register):

class LWWRegister:
    def __init__(self):
        self.value = None
        self.timestamp = 0

    def set(self, value, timestamp):
        if timestamp > self.timestamp:
            self.value = value
            self.timestamp = timestamp

    def merge(self, other):
        if other.timestamp > self.timestamp:
            self.value = other.value
            self.timestamp = other.timestamp

State-based CRDTs (Convergent CRDTs)

Operations are applied locally and entire state is merged using join operations:

OR-Set (Observed-Remove Set):

class ORSet:
    def __init__(self):
        self.elements = {}  # tag -> value
        self.tombstones = set()  # removed tags

    def add(self, value):
        tag = uuid4()
        self.elements[tag] = value
        return (tag, value)

    def remove(self, tag):
        self.tombstones.add(tag)

    def merge(self, other):
        # Union of elements, removing tombstones
        self.elements.update(other.elements)
        self.elements = {
            k: v for k, v in self.elements.items()
            if k not in self.tombstones
        }

27.6 Distributed Consensus Mechanisms

Consensus is the problem of getting distributed nodes to agree on a value. FLP impossibility proves deterministic consensus is impossible with even one faulty process in asynchronous systems. Real systems relax requirements.

Raft Consensus

Raft’s three roles: Leader, Follower, Candidate. Term numbers provide logical clocks.

Leader election:

1. Heartbeat timeout triggers follower → candidate transition
2. Candidate votes for self, requests votes from others
3. If majority votes, become leader
4. Election timeout randomized to prevent split votes

Log replication:

1. Client sends command to leader
2. Leader appends to local log, replicates to followers in parallel
3. When majority acknowledge, apply to state machine
4. Commit index propagates with AppendEntries

Safety: If log entry has committed in a term, future leaders must contain it.

Multi-Paxos

Optimized Paxos for replicated state machines:

• One leader per term (reduces prepare messages)
• PreparePromise with all accepted entries instead of single value
• Accept phase can be skipped if no competing proposals

27.7 Quorum Systems

Quorums define the minimum number of nodes required for read/write operations.

Strict quorum: Read and write quorums must overlap (R + W > N)

Quorum construction:

• Majority quorum: R = W = ⌊N/2⌋ + 1 (tolerates N/2 failures)
• Sloppy quorum: Prefer local nodes, fall back to remote on failure
• Hierarchical quorum: Tree structure reduces coordination

Version vectors track object versions across replicas:

class VersionVector:
    def __init__(self):
        self.versions = {}  # node_id -> counter

    def increment(self, node_id):
        self.versions[node_id] = self.versions.get(node_id, 0) + 1

    def merge(self, other):
        for node_id, version in other.versions.items():
            self.versions[node_id] = max(
                self.versions.get(node_id, 0),
                version
            )

    def happens_before(self, other):
        # True if all entries in self <= other, and at least one <
        return all(
            self.versions.get(k, 0) <= v
            for k, v in other.versions.items()
        ) and any(
            self.versions.get(k, 0) < v
            for k, v in other.versions.items()
        )

Where this connects

• Chapter 19: Emerging and Specialized Structures. CRDTs in the broader context of emerging structures
• Chapter 17: Persistent Data Structures. The persistence ideas that underpin versioned replicas

Chapter 28: Network Topology and Routing Data Structures

28.1 Graph Representations for Networks

Network topology is fundamentally a graph problem. The choice of graph representation determines routing efficiency, memory usage, and update complexity.

Adjacency Matrix vs Adjacency List

Adjacency matrix (O(V²) space):

  Router | A | B | C | D |
  -------|---|---|---|---|
     A   | 0 | 1 | 1 | 0 |
     B   | 1 | 0 | 0 | 1 |
     C   | 1 | 0 | 0 | 1 |
     D   | 0 | 1 | 1 | 0 |

• O(1) edge existence check
• O(V²) space even for sparse graphs
• Good for dense networks

Adjacency list (O(V + E) space):

A: B → 10, C → 5
B: A → 10, D → 3
C: A → 5, D → 7
D: B → 3, C → 7

• O(degree) neighbor enumeration
• Space proportional to actual edges
• Standard for network routing

Compressed Representations for Large Networks

CSR (Compressed Sparse Row): Store edges in three arrays:

• offsets: Starting position for each vertex’s edges
• edges: Destination vertex IDs
• weights: Edge weights (optional)

Routing tables can use trie-like compression for hierarchical networks:

Hierarchical trie for routing:
           [root]
          /  |  \
        [A] [B] [C]
       /  \    /  \
    [A1][A2] [C1][C2]

28.2 Routing Table Structures

Routing tables map network prefixes to next hops. The data structure must support fast longest prefix match (LPM), the core operation of IP forwarding.

Trie for Routing

Binary trie for IP addresses:

• Each level represents one bit
• 32 levels for IPv4, 128 for IPv6
• LPM: traverse bits until reaching longest matching prefix

Memory explosion: 2^32 possible leaves = 4 billion nodes. Solution: compressed tries (Radix Tree / Patricia Tree).

Radix Tree (Patricia Tree)

Collapse unary nodes (nodes with only one child) to reduce depth:

Standard trie path: 0→1→1→1→1
Radix tree: [01111] - single node representing this path

Example: 192.168.0.0/16, 192.168.1.0/24
    [192.168]
     /       \
  [0.0/16] [1.0/24]

Linux routing cache uses this structure internally. Memory per prefix: O(L) where L is number of bits until first branching.

LC-Trie (Level Compressed Trie)

Idea: Group levels with low fan-out into arrays, apply trie compression to high-fan-out levels.

Level 0-7: Compressed into single node (2^7 prefix range)
Level 8-15: Second level compression
...

Used in Cisco IOS and many hardware routers. Enables hardware-accelerated lookup with minimal memory.

Multi-bit Trie

Process multiple bits per step:

• 4-bit trie: Process 4 bits at a time (8 steps for IPv4 vs 32)
• 16-bit trie: Process 16 bits (2 steps for IPv4)

Trade-off: More memory (2^4 = 16 children per node) but faster lookup.

28.3 BGP Routing Data Structures

Border Gateway Protocol (BGP) routes between Autonomous Systems (AS). BGP routing tables are massive (~900K IPv4 prefixes as of 2024).

BGPRIB (Routing Information Base)

BGP stores paths in a multi-attributed structure:

Prefix: 10.0.0.0/8
  └─ AS_PATH: [1239, 701, 80]
  └─ NEXT_HOP: 192.0.2.1
  └─ LOCAL_PREF: 100
  └─ MED: 50
  └─ ORIGIN: IGP

Selection criteria (in order):

1. Highest LOCAL_PREF
2. Shortest AS_PATH
3. Lowest ORIGIN (IGP < EGP < Incomplete)
4. Lowest MED
5. eBGP over iBGP
6. Lowest IGP metric to NEXT_HOP
7. Lowest router ID

Path Vector Storage

AS_PATH is a sequence, not a set. Multiple paths to same destination create branching structures:

Dijkstra's algorithm adaptation for BGP:
- Priority queue ordered by path attributes
- Early exit when best path is known
- Incremental updates when AS_PATH changes

28.4 Software-Defined Networking (SDN) Tables

OpenFlow switch tables store flow entries with wildcard matching:

TCAM (Ternary Content-Addressable Memory)

Hardware structure for wildcard matching:

• 0 = match bit exactly
• 1 = match bit exactly
• • = don’t care (wildcard)

Priority: Longest match wins (evaluate in order).

Flow entry structure:
{
    match: {
        src_ip: 10.0.*.*,
        dst_ip: *.168.1.*,
        protocol: TCP,
        src_port: *,
        dst_port: 443
    },
    action: OUTPUT(port=3),
    priority: 100,
    stats: { packets: 1000, bytes: 50000 }
}

Wildcard Compression

Multiple rules can be merged if they differ only on don’t-care fields:

Rule 1: 10.0.0.0/8 with action A
Rule 2: 10.0.0.0/16 with action B
→ Cannot merge (Rule 2 is more specific)

28.5 Network Measurement Data Structures

Count-Min Sketch

Estimate traffic flow frequencies:

class CountMinSketch:
    def __init__(self, width, depth):
        self.width = width
        self.depth = depth
        self.table = [[0] * width for _ in range(depth)]
        self.hash_functions = [generate_hash() for _ in range(depth)]

    def add(self, item, count=1):
        for i, h in enumerate(self.hash_functions):
            self.table[i][h(item) % self.width] += count

    def estimate(self, item):
        return min(
            self.table[i][h(item) % self.width]
            for i, h in enumerate(self.hash_functions)
        )

Accuracy: With width w and depth d, error ≤ ε·N with probability 1-δ where w = e/ε, d = ln(1/δ).

Heavy Hitter Detection

Identify flows exceeding threshold T:

class SpaceSaving:
    def __init__(self, k):
        self.k = k
        self.counters = {}  # flow_id -> count
        self.min_heap = []  # (count, flow_id) min-heap

    def add(self, item):
        if item in self.counters:
            self.counters[item] += 1
        elif len(self.counters) < self.k:
            self.counters[item] = 1
            heapq.heappush(self.min_heap, (1, item))
        else:
            # Evict minimum
            min_count, evict_item = heapq.heappop(self.min_heap)
            self.counters[evict_item] = 0
            self.counters[item] = min_count + 1
            heapq.heappush(self.min_heap, (min_count + 1, item))

    def top_k(self):
        return sorted(self.counters.items(), key=lambda x: -x[1])[:self.k]

28.6 Gossip Protocol Data Structures

Gossip-based systems use epidemic algorithms for dissemination. Each node periodically exchanges state with random peers.

Anti-entropy

Periodic comparison and reconciliation:

def anti_entropy(node, peer):
    # Exchange digests (summary of owned data)
    local_digest = node.compute_digest()
    remote_digest = peer.compute_digest()

    # Find differences
    differences = compare_digests(local_digest, remote_digest)

    # Synchronize
    for key, version in differences:
        if local_version < remote_version:
            node.request(key, peer)
        elif local_version > remote_version:
            peer.request(key, node)

Convergence time: O(log N) rounds for O(N log N) messages total.

Broadcast Trees

Gossip can be organized into spanning trees for efficiency:

Root node creates spanning tree across cluster
Messages flow down tree (log N depth)
Negative acknowledgments flow up for reliability

Swim protocol for failure detection: Incremental membership updates with suspicion mechanism.

Where this connects

• Chapter 11: Graphs—Modeling Relationships. The graph fundamentals underneath routing
• Chapter 13: String Data Structures. The tries that routing tables actually are

Chapter 29: System Design as Data Structure Composition

29.1 The Unifying Theory

System design is the art of composing data structures and algorithms to solve real-world problems at scale. Every complex system reduces to foundational building blocks.

The System Design Equation:

System = Data Structures + Concurrency Control + Replication + Consistency + APIs

Where:
- Data Structures: How information is organized
- Concurrency Control: Managing simultaneous access
- Replication: Duplicating data for reliability
- Consistency: Maintaining truth across copies
- APIs: The interface to the outside world

29.2 Key-Value Stores

Key-value stores are the simplest non-trivial data structure composition: a hash table extended with persistence and replication.

Memcached Architecture

In-memory hash table with LRU eviction:

Client request:
1. Hash key → server selection (consistent hash)
2. Connect to server (TCP)
3. Send GET/SET command
4. Parse response
5. Return to client

Server internal:
- Hash table: O(1) lookup
- LRU chain: O(1) insertion/deletion
- Slab allocator: Reduce fragmentation

Slab allocation: Pre-allocate size classes (64B, 128B, …, 1MB). Items assigned to smallest sufficient class. Reduces fragmentation but may waste space.

Redis Data Structures

Redis implements rich data types on top of key-value:

• String: Binary-safe value (bitmap operations available)
• List: Linked list, O(1) push/pop at both ends
• Hash: Field-value map, O(1) field operations
• Set: Hash set (no duplicates), O(1) membership
• Sorted Set: Score-ordered, O(log N) insert/range

Persistence: RDB (point-in-time snapshots) + AOF (append-only log). Trade-off: performance vs durability.

29.3 Message Queues as Persistent Queues

Message queues are persistent FIFO structures with durability and ordering guarantees.

Apache Kafka Architecture

Log-structured storage with consumer groups:

Topic: ordered, immutable sequence of records
    ↓ (partitioned)
Partition: sequential log on disk
    ↓ (replicated)
Leader + Followers (ISR - In-Sync Replicas)

Producer: batch writes to partition leader
Consumer: offset-based consumption, committed to disk

Offset management: Consumer tracks position in partition. Enables:

• At-least-once: Commit offset after processing
• At-most-once: Commit offset before processing
• Exactly-once: Transactional commits (Kafka transactions)

Segment files: Logs split into segments (~1GB). Index file maps offset → position. Enables efficient seeking.

RabbitMQ

Queue-based with exchange routing:

Exchange (topic/direct/fanout)
    → Binding
    → Queue
    → Consumer

Persistence levels:
- Queue durable: Survive broker restart
- Message persistent: Written to disk
- Publisher confirms: Wait for replication acknowledgment

29.4 Database Storage Engines

Storage engines choose data structures for disk efficiency.

B-Tree Storage (InnoDB, PostgreSQL)

B-trees optimized for disk with large block sizes:

Page structure (16KB typical):
- Page header (metadata, checksum)
- User data area
- Free space
- Slot directory (pointers to entries)

B-tree optimizations:
- Page directory for 2-level index
- Leaf page chaining for range scans
- Write-ahead log (WAL) for durability
- Buffer pool for caching

Double-write buffer: InnoDB writes to temporary area before final location. Prevents torn writes on crash.

LSM-Tree Storage (LevelDB, RocksDB, Cassandra)

Log-Structured Merge trees optimize write throughput:

Write path:
1. Write to WAL (durability)
2. Insert into memtable (in-memory skip list)
3. When memtable fills, sort and write to L0 SSTable

Compaction:
- L0 → L1: Sort by key, merge files
- L1 → L2: Key range partitioned, merge
- Classic: Size-tiered (Cassandra)
- Modern: Level-based (RocksDB)

Trade-offs vs B-trees:

• Writes: 3-10x faster (sequential writes)
• Reads: Slower (check multiple structures)
• Space: Higher (overwrite on read)

29.5 Load Balancing Algorithms

Load balancers distribute requests across backend servers. Each algorithm uses different data structures for state tracking.

Round Robin

Simple rotation with no state:

Server list: [A, B, C]
Request 1 → A
Request 2 → B
Request 3 → C
Request 4 → A (wrap)

Weighted round robin: Servers with higher weight receive more requests.

Least Connections

Track active connections per server:

class LeastConnections:
    def __init__(self):
        self.connections = {}  # server -> count

    def select(self):
        return min(self.connections, key=self.connections.get)

    def add_request(self, server):
        self.connections[server] += 1

    def remove_request(self, server):
        self.connections[server] -= 1

Problem: Doesn’t account for varying request durations.

Least Loaded with Load Scoring

Multi-metric scoring:

def score_server(server):
    cpu_score = server.cpu_usage / 100
    mem_score = server.memory_usage / 100
    conn_score = server.active_connections / server.max_connections

    # Weighted combination
    return (0.4 * cpu_score + 0.3 * mem_score + 0.3 * conn_score)

Consistent Hash for Load Balancing

Ensure session affinity without sticky sessions:

Key space: 0 to 2^32-1
Nodes placed at hash(node_ip) positions
Virtual nodes at hash(node_ip + ":replica" + i)
Request routed to first node clockwise from hash(request_id)

29.6 CDN and Caching Hierarchies

CDNs create multi-level caching hierarchies for content distribution.

Cache Invalidation Strategies

TTL-based expiration:

def is_valid(cached_item, max_age):
    return time.now() - cached_item.timestamp < max_age

Active invalidation: Purge signals propagate through cache hierarchy.

Probabilistic early expiration: Reduce cache stampedes:

def should_revalidate(item, beta=1.0):
    # Beta = fuzziness parameter
    grace_time = item.ttl * beta
    if time.now() - item.expires > grace_time:
        return random.random() < 0.5  # Probabilistic revalidate
    return False

LFU-D with Dynamic Aging

Frequency-based with aging to prioritize recency:

class LFUD:
    def __init__(self):
        self.freq = {}  # key -> frequency count
        self.min_freq = 0

    def access(self, key):
        self.freq[key] = self.freq.get(key, 0) + 1
        self.min_freq = min(self.freq.values())

    def evict(self):
        # Evict lowest frequency, age all frequencies
        for key in list(self.freq.keys()):
            self.freq[key] -= self.min_freq
            if self.freq[key] <= 0:
                del self.freq[key]
        self.min_freq = 0

29.7 Rate Limiting Data Structures

Rate limiting controls request throughput.

Token Bucket

class TokenBucket:
    def __init__(self, rate, capacity):
        self.rate = rate
        self.capacity = capacity
        self.tokens = capacity
        self.last_update = time.now()

    def allow(self, tokens=1):
        now = time.now()
        elapsed = now - self.last_update
        self.tokens = min(
            self.capacity,
            self.tokens + elapsed * self.rate
        )
        self.last_update = now

        if self.tokens >= tokens:
            self.tokens -= tokens
            return True
        return False

Token bucket vs Leaky bucket: Token bucket allows burstiness up to capacity; leaky bucket outputs at constant rate.

Sliding Window Log

More accurate rate limiting:

class SlidingWindowLog:
    def __init__(self, window_size):
        self.window_size = window_size
        self.requests = []  # Timestamps of requests

    def allow(self):
        now = time.time()
        # Remove old entries
        self.requests = [
            t for t in self.requests
            if now - t < self.window_size
        ]

        if len(self.requests) < self.max_requests:
            self.requests.append(now)
            return True
        return False

Fixed window vs Sliding window vs Sliding log: Trade-offs between accuracy, memory, and implementation complexity.

Where this connects

• Chapter 10: Multiway Search Trees and B-Trees. The B-trees inside every storage engine described here
• Chapter 14: Probabilistic Data Structures. The probabilistic structures these systems rely on

Chapter 30: Advanced System Patterns and Case Studies

30.1 Search Infrastructure: Inverted Index

Full-text search engines use inverted indexes for efficient keyword lookups.

Inverted Index Structure

Document collection:
Doc1: "data structures are fundamental"
Doc2: "data structures enable efficient algorithms"

Forward index (doc → terms):
Doc1 → ["data", "structures", "are", "fundamental"]
Doc2 → ["data", "structures", "enable", "efficient", "algorithms"]

Inverted index (term → docs):
"data"      → [Doc1, Doc2]
"structures"→ [Doc1, Doc2]
"are"       → [Doc1]
"fundamental" → [Doc1]
"enable"    → [Doc2]
"efficient" → [Doc2]
"algorithms"→ [Doc2]

Posting list: Each term points to a sorted list of document IDs.

BM25 Scoring

Probabilistic relevance ranking:

Score(D, Q) = Σ IDF(qi) × (tf × (k1 + 1)) / (tf + k1 × (1 - b + b × |D|/avgdl))

Where:
- tf = term frequency in document
- |D| = document length
- avgdl = average document length
- k1 = term frequency saturation (typically 1.2-2.0)
- b = length normalization (typically 0.75)
- IDF = log((N - n + 0.5) / (n + 0.5))

Fenced and Sharded Indexes

Sharding by document: Different shards contain different documents. Parallel query all shards, merge results.

Sharding by term (router): One shard responsible for a term range. Queries routed based on first term. Problem: hot terms cause imbalance.

30.2 Recommendation System Data Structures

Collaborative Filtering with Matrix Factorization

User-item matrix decomposition:

R ≈ U × V^T

R: m×n user-item rating matrix
U: m×k user latent factors
V: n×k item latent factors
k: latent dimension (typical 50-200)

Alternating Least Squares (ALS):

def als(R, k, iterations, reg=0.1):
    """`reg` is the L2 regularization weight, spelled `lambda` in the papers,
    which is a reserved word in Python."""
    m, n = R.shape
    U = random(m, k)
    V = random(n, k)
    I = identity(k)

    for _ in range(iterations):
        # Fix U, solve for V
        for j in range(n):
            users = R[:, j].nonzero()
            V[j] = solve(
                U[users].T @ U[users] + reg * I,
                U[users].T @ R[users, j]
            )
        # Fix V, solve for U
        for i in range(m):
            items = R[i, :].nonzero()
            U[i] = solve(
                V[items].T @ V[items] + reg * I,
                V[items].T @ R[i, items].T
            )
    return U, V

Approximate Nearest Neighbors

Vector search for embedding similarity:

class HNSW:
    def __init__(self, m=16, ef_construction=200):
        self.m = m
        self.ef = ef_construction
        self.graph = {}  # node_id -> [neighbors]
        self.layers = []  # layer -> [node_ids]

    def insert(self, vector, max_layers=6):
        # Random layer selection (geometric distribution)
        level = int(-log(random()) % max_layers)

        # Search from top layer to find insert position
        for l in reversed(range(level + 1)):
            candidates = self._search_layer(vector, ef=1, layer=l)
            # Connect to m nearest unconnected nodes
            self._connect(vector, candidates, l)

ANN benchmarks: HNSW, ScaNN, DiskANN, FAISS. Trade-offs: query speed vs recall vs memory.

30.3 Time Series Databases

Time series data requires specialized structures for append-heavy workloads and time-range queries.

Columnar Storage with Time Partitioning

Partitioning scheme:
/data/year=2024/month=01/day=15/hour=12/
    segment_000.parquet
    segment_001.parquet
    segment_002.parquet

Within segment (columnar):
| timestamp | cpu | memory | disk_io |
| 1705312800 | 45 | 32 | 1200 |
| 1705312801 | 47 | 31 | 1150 |

Benefits:

• Columnar: Efficient aggregation (only read needed columns)
• Time partitioning: Prune irrelevant partitions
• Segment size: Balance between query efficiency and write buffering

Downsampling and Aggregation

Tiered storage: Raw data → Downsampled → Long-term retention

Raw (second precision) → 1 hour rollup → 1 day rollup → 1 month rollup
Retention: 1 week         6 months        2 years          forever

Aggregation algorithms:

• LTTB: Largest Triangle Three Buckets for visual fidelity
• Min/max sketches: Approximate aggregates with space efficiency

30.4 Event Sourcing and CQRS

Event sourcing stores state as a sequence of events rather than current state.

Event Store Structure

class EventStore:
    def __init__(self):
        self.streams = {}  # aggregate_id -> [event]

    def append(self, aggregate_id, event):
        self.streams.setdefault(aggregate_id, []).append(event)

    def get_stream(self, aggregate_id, from_version=0):
        return self.streams.get(aggregate_id, [])[from_version:]

    def rebuild_state(self, aggregate_id):
        state = {}
        for event in self.get_stream(aggregate_id):
            state = apply_event(state, event)
        return state

Benefits: Complete audit trail, temporal queries, easy replay for debugging.

Challenges: Event schema evolution, eventual consistency, query complexity.

CQRS (Command Query Responsibility Segregation)

Separate read and write models:

Command side (write):
- Handle commands (not queries)
- Aggregate events into state
- Publish to event bus

Query side (read):
- Maintain read models optimized for specific queries
- Subscribe to events for projection updates
- Materialized views for fast access

30.5 Sharding Patterns

Horizontal partitioning across multiple databases.

Consistent Hash Ring with Virtual Nodes

Virtual node mapping:
Physical Node A → VNode_1, VNode_5, VNode_12, VNode_23
Physical Node B → VNode_3, VNode_8, VNode_15, VNode_19
Physical Node C → VNode_2, VNode_11, VNode_17, VNode_24

Shard calculation:
shard = hash(key) % (num_physical × num_vnodes)
owner = virtual_node_ring[shard]

Rebalancing: When adding nodes, only O(1/k) keys move where k is virtual node count.

Skip Hash for Hot Data

Hot data (top 1% of access):
- Replicated 3-5x across nodes
- Stored in memory or fast SSDs

Warm data (next 19%):
- Partitioned across cluster
- Standard replication factor (3)

Cold data (bottom 80%):
- Archived to cheaper storage
- Reduced replication (2)
- Accessed rarely

30.6 Consistency Patterns in Practice

Saga Pattern for Distributed Transactions

Choreography vs orchestration:

Choreography (event-driven):
OrderCreated → InventoryReserve → PaymentCapture → OrderConfirmed
            ↓              ↓              ↓
         (rollback)     (rollback)     (rollback)

Orchestration (centralized):
Saga Orchestrator:
  1. Send ReserveInventory
  2. Receive InventoryReserved
  3. Send CapturePayment
  4. Receive PaymentCaptured
  5. Send ConfirmOrder
  (On failure, send compensating transactions)

Two-Phase Commit (2PC)

Distributed transaction protocol:

Phase 1 - Prepare:
1. Coordinator asks all participants to prepare
2. Participants vote Yes/No (locks resources)
3. If all Yes, proceed to commit; otherwise abort

Phase 2 - Commit:
1. Coordinator sends commit to all participants
2. Participants apply changes, release locks
3. Coordinator confirms completion

Problems: Blocking, coordinator failure, latency.

30.7 Observability Data Structures

Distributed Tracing

Span graph for request flow:

class Span:
    def __init__(self, name, trace_id, span_id, parent_id=None):
        self.name = name
        self.trace_id = trace_id
        self.span_id = span_id
        self.parent_id = parent_id
        self.start_time = time.now()
        self.end_time = None
        self.tags = {}
        self.annotations = []

    def finish(self):
        self.end_time = time.now()

    def duration_ms(self):
        return (self.end_time - self.start_time) * 1000

Trace assembly: Child spans attached to parents via span_id/parent_id. Hierarchical tree represents causal relationship.

Metric Aggregation

Time-series aggregation with downsampling:

Raw metrics (every 10s):
[23, 25, 22, 28, 24, ...]

1-minute rollup:
avg: 24.4, max: 28, min: 22, p50: 24, p95: 27, p99: 28

1-hour rollup:
avg: 24.1, max: 45 (spike during incident), p99: 38

Cardinality management: High-cardinality labels (user IDs, request IDs) must be aggregated before storage.

Where this connects

• Chapter 29: System Design as Data Structure Composition. The component structures these patterns compose
• Chapter 19: Emerging and Specialized Structures. The vector-search structures behind modern recommendation

Chapter 31: Real-World Case Studies

Five systems, examined for the same thing: which data structures they chose, and what those choices bought and cost. Each one made a decision the others didn’t, and in every case the decision traces back to a structure from earlier in this book.

31.1 Google’s Spanner: Globally Distributed SQL

Spanner combines B-tree storage with distributed systems innovations:

Architecture:

Universe (global deployment)
  ↓
Zone (data center)
  ↓
Spanserver (process)
  ↓
Tablet (range of rows, ~100GB)
  ↓
Colossus (distributed file system)

TrueTime API: GPS and atomic clocks provide bounded clock uncertainty (±1ms to ±7ms). This enables:

• External consistency (linearizable transactions)
• Snapshot reads without coordination
• Consistent schema changes

Paxos consensus: Data replicated via Paxos between zones. Two-phase commit with participant coordinators.

The central idea is that TrueTime turns time into a data structure with an error bar. Ordinary clocks return a timestamp; TrueTime returns an interval [earliest, latest] guaranteed to contain the true time. That single change makes global ordering possible without global coordination.

The mechanism is called commit wait, and it is almost aggressively simple:

To commit a transaction at timestamp s:
  1. Acquire locks, pick s = TT.now().latest
  2. Do the work
  3. WAIT until TT.now().earliest > s      ← deliberately sleep
  4. Release locks, commit

After the wait, s is guaranteed to be in the past everywhere on Earth.
So any transaction that starts later gets a strictly larger timestamp.

Spanner waits out the clock uncertainty rather than trying to eliminate it. With ε ≈ 7ms of uncertainty, every commit sleeps roughly 7ms before releasing locks. Google chose to buy an ordering guarantee with latency, and then spent heavily on GPS receivers and atomic clocks in every datacenter to keep the price low, because the cost of the whole system is proportional to ε.

Structures in play: B-trees for tablet storage (via Colossus), a Paxos state machine per tablet group, two-phase locking, and MVCC. Every row version is timestamped, so a snapshot read at time t needs no locks at all and never blocks a writer. That last property is Chapter 17’s partial persistence, deployed globally.

The cost: writes pay a cross-region Paxos round trip plus commit wait, so write latency is tens to hundreds of milliseconds. Spanner is the right answer when you need global transactions and can tolerate that, and the wrong answer for a write-heavy local workload.

31.2 Amazon Dynamo: Highly Available Key-Value Store

Dynamo prioritizes availability over consistency:

Design decisions:

• “Always writable”: Sloppy quorum + hinted handoff
• Vector clocks for causality tracking
• Quorum guarantees configurable per request

Data distribution:

Consistent hashing ring (N=3, R=2, W=2):
- N: Number of replicas
- R: Minimum read replicas
- W: Minimum write replicas
- Quorum: max(R,W) > N/2

Anti-entropy: Merkle trees for background synchronization. Each replica maintains local Merkle tree of its key range; trees compared to detect divergence.

Dynamo is the deliberate opposite of Spanner, and the paper is unusually honest about why: for Amazon’s shopping cart, rejecting a write costs a sale. So Dynamo never rejects one. If the responsible node is unreachable, another node accepts the write and holds it with a hint to forward it later: sloppy quorum with hinted handoff.

The consequence is that two replicas can legitimately hold different values for the same key, and the system needs a way to tell “B replaced A” from “A and B happened concurrently”. That is what vector clocks provide:

Client writes cart to node A:        [(A,1)]
Client adds item, writes to A:       [(A,2)]           A,2 descends from A,1 → replaces
Partition. Client adds via B:        [(A,2), (B,1)]
Meanwhile client adds via C:         [(A,2), (C,1)]

Partition heals. Neither vector dominates the other
→ concurrent. Both versions are returned to the client.

Dynamo pushes reconciliation to the application, and for a shopping cart the resolution is a set union, which is why a deleted item famously sometimes reappears. That is the visible cost of choosing availability, and it is a deliberate trade, not a bug.

Merkle trees solve the other problem: detecting divergence without comparing everything. Each replica hashes its key range into a tree; two replicas compare root hashes, and if they match (the common case)they are identical and nothing more transfers. If they differ, they descend only into subtrees whose hashes disagree. Comparing two replicas of a million keys with one difference takes about 20 hash comparisons instead of a million. The same structure, for the same reason, is how Git compares trees and how BitTorrent verifies pieces.

Structures in play: consistent hashing with virtual nodes (Chapter 27), vector clocks, Merkle trees, and per-node LSM or B-tree storage. Dynamo’s design became DynamoDB, Cassandra, Riak, and Voldemort.

31.3 Apache Kafka: Distributed Log as First-Class Citizen

Kafka treats the log as the primary data structure:

Storage architecture:

Topic: "orders"
  ↓
Partitions (16):
  Partition 0: [0 → 1MB] [1MB → 2MB] ...
  Partition 1: [0 → 1.2MB] [1.2MB → 2.1MB] ...
  ...

Each partition stored as:
  - .log file (actual data)
  - .index file (offset → position)
  - .timeindex file (timestamp → offset)

Zero-copy I/O: Kafka uses kernel sendfile() to avoid copying data to user space. DMA transfers data from disk directly to network.

Page cache: Linux page cache used for hot data. Sequential writes cause read-ahead, sequential reads cause readahead.

Kafka’s insight is that an append-only log is a better primitive than a queue. A traditional message queue deletes a message once consumed, which forces it to track per-message delivery state and makes replay impossible. Kafka never deletes on consumption; it keeps an ordered, immutable log and lets each consumer track its own offset: a single integer.

That one decision produces most of Kafka’s properties:

• Multiple independent consumers read the same partition at different positions, without coordination.
• Replay is seeking backwards.
• Broker state per consumer is one integer, so brokers scale to enormous consumer counts.
• Writes are pure appends. Sequential disk I/O, which as Chapter 16 explains is often faster than random writes to memory, and vastly faster than random disk writes.

The .index file is a sparse index: an entry every few kilobytes, not per message. A lookup binary-searches it to find the nearest earlier offset, then scans forward. Sparse keeps the index small enough to stay in page cache, and the scan is sequential. The same “cheap sequential work beats expensive random work” reasoning throughout.

Zero-copy is worth understanding as an accounting exercise. A conventional send copies data four times: disk → kernel page cache → user buffer → socket buffer → NIC. sendfile() goes disk → page cache → NIC, eliminating two copies and two context switches. This is only possible because Kafka does not transform the bytes. It stores exactly what the producer sent, so the kernel can move them without user space ever seeing them. An immutable log makes the optimisation available.

The cost: ordering is guaranteed only within a partition, not across a topic. Anything needing global ordering must use a single partition and give up parallelism. That constraint shapes every Kafka data model.

31.4 Databricks Delta Lake: ACID on Data Lakes

Combines streaming (append-only log) with batch processing:

Transaction log: JSON entries recording changes:

{"add": "part-00000.snappy.parquet", "partitionValues": {"date": "2024-01-01"}, "size": 1234567}
{"remove": "part-00099.parquet"}

Optimistic concurrency: Delta Lake uses file-level locking. Transaction validation checks:

1. Read current protocol version
2. Verify read set files still exist
3. Write new files and transaction commit
4. If conflict, retry with exponential backoff

Delta Lake solves a problem created by cloud object storage: S3 gives cheap, durable, effectively infinite storage but no transactions and no atomic multi-file operations. A job writing 500 Parquet files that fails halfway leaves the table in a state no reader can interpret.

The fix is to stop treating the file listing as the source of truth. The transaction log is the table; the Parquet files are just content addressed by it. A reader replays the log to compute the current file set, and a file not named in the log does not exist as far as the table is concerned, so a failed job leaves orphaned files that are simply invisible, rather than corruption.

This makes the table state a persistent data structure in exactly the sense of Chapter 17: each log entry produces a new version, old versions remain valid, and unchanged files are shared between them. “Time travel” (querying the table as of last Tuesday)is not a feature bolted on but a direct consequence of the representation.

Replaying the entire log would get slow, so Delta periodically writes a checkpoint (a Parquet file holding the full state at version N), and readers start from the newest checkpoint and replay only the entries after it. This is the same log-plus-snapshot pattern used by Raft, Redis AOF with RDB, and every event-sourced system in Chapter 30.

Optimistic concurrency works here because the workload is right for it: writers are few and conflicts are rare. Each writer reads the current version, does its work, and attempts to commit version N+1 by atomically creating a file with that name. Exactly one wins; the loser checks whether the conflict was real (did anyone touch the files I read?) and retries if not. Pessimistic locking would be pure overhead at this conflict rate.

The cost: small, frequent writes produce many small files and log entries, degrading read performance until compaction runs. Delta Lake suits batch and micro-batch workloads, not per-record streaming.

31.5 Cloudflare’s Edge Cache: Global Caching Infrastructure

Anycast routing: All edge nodes announce same IP via BGP. Traffic routed to nearest PoP (Point of Presence).

Cache hierarchy:

User → Edge PoP (L1 cache, ~100GB)
           ↓ (miss)
        Regional DC (L2 cache, ~1TB)
           ↓ (miss)
        Origin Shield (L3 cache, ~10TB)
           ↓ (miss)
        Origin server

Cache key normalization:

• Strip query parameters (configurable)
• Normalize URL encoding
• Include vary headers in key
• TTL rules per content type

Two structural ideas do most of the work here.

Anycast makes routing itself the load balancer. Hundreds of PoPs announce the same IP prefix via BGP, and the internet’s own routing tables (the tries of Chapter 28)deliver each packet to the topologically nearest one. There is no load balancer to scale, no DNS TTL to wait out during a failover, and a PoP that goes down simply stops announcing, after which BGP reconverges automatically. The cost is that the routing tables decide, not you: BGP optimises for AS-path length, which is not always the lowest latency.

The cache hierarchy is the memory hierarchy again, at planetary scale and with the same arithmetic. Each tier is larger, slower, and further away, and each absorbs the misses of the tier above:

The origin shield exists for a specific failure mode: without it, a popular object expiring simultaneously across 300 edge PoPs sends 300 requests to the origin at once, a thundering herd. The shield collapses them into one. The general technique is request coalescing: concurrent misses for the same key wait on a single in-flight fetch rather than each issuing their own.

Cache key design is where correctness lives. Include too much in the key (a tracking parameter, a session cookie)and the hit rate collapses because every request is unique. Include too little and users are served each other’s content, which is a security incident rather than a performance problem. The Vary header is the standard mechanism, and getting it wrong is one of the more common ways to leak data between users.

31.6 What the Five Have in Common

Reading them side by side, the patterns are more instructive than any individual system:

Three observations worth carrying:

Every system is a composition, not an invention. Spanner is B-trees plus Paxos plus MVCC plus a clock. Dynamo is consistent hashing plus vector clocks plus Merkle trees. None of the components are new; the arrangement is. This is the claim Chapter 29 makes, and these systems are the evidence.

The interesting decision is always what to give up. Spanner and Dynamo faced the same problem and chose opposite sides of CAP, and both were right for their workload. A system that appears to give up nothing has usually hidden the cost somewhere you haven’t looked yet.

Sequential access wins repeatedly. Kafka’s append-only log, Delta Lake’s log, LSM-tree flushes, Merkle tree comparison: the same principle from Chapter 16, reappearing at every scale from cache lines to datacenters.

Where this connects

• Chapter 29: System Design as Data Structure Composition. The composition principle these systems demonstrate
• Chapter 27: Distributed Data Structures. The distributed primitives they are built from

Chapter 32: Synthesis and Future Directions

32.1 The Data Structure Spectrum

From fundamental to application-specific:

Abstraction Level
├── Fundamental: Array, List, Tree, Hash, Graph
│
├── Composite: Skip lists, Tries, Heaps, Bloom filters
│
├── Specialized: Segment trees, B-trees, LSM trees
│
├── Distributed: DHT, CRDT, Raft state machines
│
└── Application: Routing tables, Inverted indexes,
                Time series stores, Graph DBs

The layers are not just an organising convenience. each one is built by composing the layer beneath it, and tracing a structure down through the stack usually explains why it behaves the way it does.

A routing table is a trie is a tree is pointers into memory. An LSM tree is sorted runs plus a memtable plus Bloom filters, which are a bit array plus hash functions. A DHT is a hash function plus a ring plus a routing table plus failure detection. Nothing at the top of this diagram is novel at the bottom of it.

Read the other direction, the same diagram is a map of what changes as you ascend:

Complexity analysis is most useful at the top two rows and least useful at the bottom two. Nobody chooses between two distributed designs by comparing O(log n) to O(1); they compare round trips, failure modes, and what happens during a partition. The asymptotics have not become wrong, they have become the least interesting term.

32.2 Emerging Paradigms

Learned Data Structures

Machine learning models replacing traditional structures:

• Learned indexes: Replace B-trees with neural networks predicting data positions
• Learned cardinalities: Better statistics for query optimization
• Learned compression: Adaptive compression based on data distribution

Neural B-tree:

Input: key
Output: predicted position + confidence interval

Training: Supervised learning on key distributions
Prediction: Binary search within confidence bounds

The reframing is genuine: an index is a function from key to position, and a model can approximate a function. A B-tree assumes nothing whatsoever about the key distribution, which makes it robust and also means it throws away information. Real key distributions (timestamps, auto-increment IDs, sorted identifiers)are highly regular, and a model that captures that regularity beats a structure that ignores it.

The honest status, five years on from the original paper: learned indexes remain mostly research, and the parts that shipped are elsewhere. Updates are the hard problem. The original design was read-only, and while ALEX and the PGM-index support updates, distribution shift can force retraining. Worst-case bounds disappear, which matters for anything adversarial. And “neural network” oversells it: the models that work are staged linear regressions, because inference has to cost nanoseconds.

What has landed from this line of work is less glamorous and more useful: learned cardinality estimation in query optimisers, learned cache-eviction policies, and learned Bloom filters. Chapter 19 covers the details.

Quantum Data Structures

Quantum computing offers new primitives:

• Quantum search: O(√n) search (Grover’s algorithm)
• Quantum random access memory (QRAM): Sub-linear access with superposition
• Quantum fingerprints: Exponential space reduction for equivalence testing

Worth stating the caveats plainly, because this area attracts more enthusiasm than it currently earns.

Grover’s algorithm gives a quadratic speedup for unstructured search: O(√n) instead of O(n). That is real but modest, and it applies to unstructured search. A sorted array with binary search is already O(log n), which beats O(√n) comfortably. Grover helps where no structure exists to exploit, which is precisely the case where you would normally add an index.

QRAM is the deeper problem. Most quantum algorithms with impressive speedups assume a memory that can be queried in superposition, and no scalable QRAM has been built. The theoretical speedups are frequently accounted without the cost of loading classical data into quantum state, which can erase the advantage entirely.

The realistic near-term position: quantum computing will likely matter first for simulation, optimisation, and cryptography, not for data structures. The exception is cryptographic hashing: Grover halves the effective bit strength of a hash function, which is why post-quantum guidance recommends 256-bit hashes where 128 was sufficient. That is a live concern for Merkle trees and content-addressed storage.

32.3 The Road Ahead

Software-hardware co-design: As memory hierarchies deepen (NVM, CXL), data structures must adapt. Cache-oblivious structures gain importance.

Specialized accelerators: FPGAs and ASICs for network processing, search, and analytics push structure design toward hardware.

Declarative data structures: The boundary between algorithms and data structures blurs as query optimizers automatically choose structures based on workload patterns.

Two shifts already underway deserve to be added, because they are changing decisions today rather than eventually.

Vector search became infrastructure in about three years. Embedding models turned similarity search from a niche problem into a default component of application architecture, and the structures that serve it (HNSW graphs, IVF, product quantization)went from papers to production defaults faster than almost anything in this book’s history. Note what drove it: not a better algorithm, but a change in what data looked like. Structures follow workloads.

NVMe is quietly reopening settled questions. A great deal of received wisdom: B-trees over hash indexes on disk, LSM trees over in-place updates, “random I/O is catastrophic”. Was calibrated against spinning disks where a seek cost 10ms. On NVMe a random read costs about 10μs, a thousandfold improvement, and the gap between sequential and random access narrows from 10,000× to something closer to 10×. Several tradeoffs that were obvious in 2005 are now genuinely arguable. When the hardware assumptions under a piece of conventional wisdom change by three orders of magnitude, the wisdom deserves rechecking.

The general lesson across both: the structures that win are the ones that answer a question created by a hardware or workload shift. LSM trees won when write amplification on flash started to matter. HNSW won when embeddings created a new query type. Neither was primarily an algorithmic advance.

32.4 Principles for the Practitioner

1. Measure before optimizing: Profile against real workloads
2. Understand trade-offs: Every structure excels in some dimensions
3. Prefer simplicity: Complex structures have hidden costs
4. Plan for scale: Design for 10x growth
5. Embrace approximation: Probabilistic structures often suffice
6. Consider distribution: At scale, single-machine solutions fail
7. Document assumptions: Workload characteristics drive structure choice

Four of those are worth sharpening, because as stated they are easy to agree with and hard to act on.

Measure the right thing. “Profile” usually means a wall-clock profiler, which tells you where time goes but not why. If a function is slow and its arithmetic is trivial, the answer is memory, and you need hardware counters to see it. An instructions-per-cycle figure below 1.0 with high cache misses means the layout is wrong and no algorithmic tuning will help: see Chapter 22.

Prefer simplicity, and mean it. The most common real-world mistake is not picking an O(n log n) structure where O(n) existed. It is picking a sophisticated structure whose constant factors, memory overhead, and bug surface exceed the benefit. Fibonacci heaps are the standing example: optimal on paper, beaten by binary heaps in practice, and vastly harder to get right. A linear scan over a contiguous array beats almost everything below a few hundred elements.

“Design for 10× growth” is a claim about which dimension grows. Ten times the data is a different problem from ten times the write rate, which is different again from ten times the concurrent readers. B-trees handle the first, LSM trees the second, immutable structures the third. Designing for unspecified “scale” produces systems that are complex in the wrong direction.

Embrace approximation, after checking the error direction. A Bloom filter’s false positives are safe as a cache filter and unsafe as an access-control check. The question is never just “is approximate good enough” but “what does a mistake cost, and which way does this structure make them” (Chapter 14).

Three more that this book has argued throughout:

8. Identify the repeated question. Every algorithm asks one thing over and over. “which is nearest”, “have I seen this”, “would this create a cycle”. Name it, and the structure is usually obvious. Get it wrong and no optimisation will save you (Chapter 21).

9. Abstract the interface, document the cost. A List backed by an array and one backed by a linked list have identical signatures and completely different performance. Hiding the layout is good design; hiding the cost is how O(n²) loops get written by accident.

10. Write the invariant checker. For every structure there is a predicate that must hold after every operation. Written as code and asserted in debug builds, it converts a silent wrong answer a thousand operations later into a failure on the operation that caused it.

32.5 A Closing Thought

The through-line of these thirty-one chapters is that there are far fewer ideas here than there are structures. Almost everything in this book is one of a handful of moves, applied at a different scale:

• Divide the space so most of it can be discarded: binary search, trees, tries, KD-trees, sharding.
• Trade exactness for space: Bloom filters, HyperLogLog, sketches, learned indexes.
• Trade space for time, or the reverse: indexes, caches, memoization, compression.
• Batch the expensive thing: LSM trees, B-tree fanout, external sorting, request coalescing.
• Share what didn’t change: persistent structures, copy-on-write, Git, snapshots, Merkle trees.
• Randomize to defeat the adversary: skip lists, treaps, universal hashing, randomized pivots.
• Never mutate; append and reference: logs, event sourcing, immutable collections, Kafka, Delta Lake.

Each of those appears at every level of the spectrum in §32.1, from cache lines to continents. A B-tree fans out to reduce disk transfers; a CDN hierarchy fans out to reduce origin requests; both are the same move against a different cost. Recognising which move a system is making is usually faster than learning the system.

New structures will keep arriving, and most will not last. The survivors are the ones answering a question that new hardware or a new workload just created. But they will be built from these same moves, because the moves are responses to constraints that have not changed: memory is a hierarchy, coordination is expensive, and you cannot have everything at once.

That last constraint is the one this book opened with, in Chapter 1: there is no free lunch. Every structure is fast at something because it agreed to be slow at something else. Knowing what a structure gave up is knowing when to use it.

Where this connects

• Chapter 25: Complete Selection Guide and Complexity Reference. The selection guide, for putting this into practice
• Chapter 1: The Philosophy and Mathematics of Data Structures. Where the no-free-lunch argument started

Appendix A: Complexity Cheat Sheet

Two conventions for reading these tables:

• Average assumes random or well-distributed data. Worst is the adversarial case. Where they differ, the gap is usually the whole story. A hash table is O(1) average and O(n) worst, and which one you get depends on your hash function and your adversary.
• ★ marks amortized bounds: cheap on average across a sequence of operations, with occasional expensive ones. A dynamic array append is O(1)★ because the resize that costs O(n) happens rarely enough to average out.

A.1 Linear Structures

The linked-list rows come with the caveat that makes them much less useful than they look: insertion and deletion are O(1) only once you already hold the relevant node. Getting there is O(n), so an insert-at-position is O(n) overall.

A.2 Trees and Ordered Maps

Where L = key length, N = total characters stored across all keys, A = alphabet size.

Two rows worth reading carefully. Skip list space is O(n) expected, not O(n log n): with promotion probability p = ½, the expected total number of nodes across all levels is 2n. The O(log n) is the expected height, which is a different quantity. And splay trees have no per-operation guarantee at all: a single access can cost O(n), and only a sequence of m operations is bounded, at O(m log n). That makes them unsuitable for latency-sensitive work regardless of their excellent amortized behavior.

A.3 Hash-Based Structures

Where m = number of buckets. Cuckoo hashing is the notable row: it is one of the few hash schemes with a genuine O(1) worst-case lookup, because a key can only live in one of two positions. Insertion pays for it, and can fail and require a full rehash.

Java’s HashMap converts a bucket to a red-black tree past 8 entries, giving O(log n) rather than O(n) in the worst case: a defense against deliberate collision flooding.

A.4 Heaps and Priority Queues

Building a heap from n existing elements is O(n), not O(n log n): Floyd’s bottom-up heapify. This surprises people and is worth remembering.

Fibonacci heaps have the best bounds on this table and lose to binary heaps on most real workloads; see Chapter 19.

A.5 Graphs

For a graph with V vertices and E edges:

That last row is a common trap. Rollback requires undoing parent changes, which path compression makes impossible to track cheaply, so rollback DSU uses union by rank alone and costs O(log n), not O(α(n)).

α(n) is the inverse Ackermann function, below 5 for any n that fits in the observable universe.

A.6 Probabilistic and Specialized

A Bloom filter with 1% false-positive rate needs about 9.6 bits per element regardless of how large the elements are, which is the property that makes it useful.

A.7 Competitive Programming Structures

Where σ = alphabet size, m = pattern length, C = coordinate range.

Mo’s algorithm is offline and processes q queries in O((n + q)√n) total; the O(√n) figure is the amortized per-query share, not a bound on any single query.

A.8 Complexity Growth Reference

How the classes actually behave, for intuition about when each becomes infeasible:

Rough practical ceilings at roughly 10⁸ simple operations per second: O(n²) is fine to n ≈ 10,000; O(n log n) to n ≈ 10⁷; O(n) to n ≈ 10⁸; O(2ⁿ) to n ≈ 25; O(n!) to n ≈ 11.

Appendix B: When to Use What

B.1 The Short Answer

B.2 The Decision, in Four Questions

Most structure choices resolve with these, asked in order.

1. Do I ever need the elements in order?

This is the single most consequential question, and the one most often skipped. Ordered iteration, range queries, “the next key after X”, and “the smallest key” all require a tree or a sorted structure. A hash table can do none of them at any price.

The failure mode is not discovering this on day one. It is discovering it six months in, when someone asks for “all records between these two dates” and the answer requires replacing the container.

2. What is the read/write mix?

3. Where does it live?

4. How exact must it be?

If an approximate answer is acceptable, the space savings are usually one to five orders of magnitude, but check which way the errors go first (Chapter 14).

B.3 By Operation

The structure that makes each operation cheapest, with the cost of choosing it.

B.4 By Scale

The right answer changes with n, and the changes are larger than intuition suggests.

B.5 Common Mistakes

Using a linked list because insertion is O(1). It is O(1) only once you already hold the node. Finding it is O(n), and the traversal is cache-hostile. std::vector beats std::list for middle insertion at surprisingly large sizes: measure before believing otherwise.

Using a hash map when you needed order. See B.2, question 1. This is the most expensive mistake on this page because it surfaces late.

Reaching for a fancy structure at small n. A segment tree over 50 elements is slower than a loop, and considerably more code to get wrong.

Ignoring the worst case on untrusted input. A hash table is O(1) average and O(n) adversarial. If users can choose the keys, you need a keyed hash or a treeifying table (Chapter 12).

Optimizing before profiling, and profiling the wrong thing. If a function is slow and the arithmetic is trivial, the problem is memory, and only hardware counters will show it (Chapter 22).

Testing with random data. Real data arrives sorted far more often than random data does: by timestamp, by ID, by insertion order. Sorted input is the worst case for a naive BST and for quicksort with a fixed pivot. Test sorted, reverse-sorted, and all-identical deliberately.

B.6 Language Defaults

What to reach for first, per language, before writing anything custom.

Two traps worth remembering: Python has no ordered map or tree in the standard library. dict preserves insertion order, which is not the same as sorted order. And heapq is min-only while C++ and Rust default to max-heaps, which is a reliable source of inverted-comparator bugs when porting.

For fuller detail on what these are actually implemented as, see Chapter 22; for exact complexities, Appendix A.

Appendix C: Glossary

Complexity and Analysis

ADT (Abstract Data Type): A data type defined by its operations, not implementation. A stack is an ADT; an array-backed stack is an implementation.

Amortized: Average cost over a sequence of operations, where occasional expensive operations are paid for by many cheap ones. A dynamic array append is O(1) amortized because the O(n) resize happens rarely enough to average out. Distinct from average case, which is about input distribution rather than operation sequences.

Asymptotic: Describing behavior as input size grows without bound. Says nothing about small inputs, which is why an O(n log n) algorithm can lose to an O(n²) one at n = 50.

Big-O: An upper bound on growth. Θ is a tight bound and Ω a lower bound; most practical writing uses O loosely to mean Θ.

Expected: Average over the structure’s own random choices, not over inputs. A skip list is O(log n) expected regardless of input, because the randomness is internal.

Inverse Ackermann α(n): A function growing so slowly it is below 5 for any n that could physically exist. The bound on union-find with path compression.

Time / Space Complexity: How running time or memory grows with input size.

Worst case: The maximum over all inputs, including adversarial ones. The bound that matters when input is untrusted.

Structural Terms

Balanced Tree: A tree whose subtree heights differ by at most a constant factor, guaranteeing O(log n) height.

Cursor: A position indicator within a data structure.

Degenerate Tree: A tree that has degraded to essentially a linked list, the worst case for an unbalanced BST.

Fan-out: The number of children a node can have. High fan-out is what makes B-trees shallow.

Heap Property: Every parent compares greater (max-heap) or less (min-heap) than its children. Note this is a weaker invariant than sorted order.

Invariant: A property that must hold before and after every operation. Writing invariants as runnable assertions is the most effective way to catch structural bugs near their cause.

Leaf: A node with no children.

Sentinel: A dummy node that removes special cases (an empty-list check, a null-pointer test)by guaranteeing a node always exists.

Tombstone: A marker left in place of a deleted entry so that probe sequences in an open-addressed hash table are not broken.

Hashing

Collision: When two distinct keys hash to the same index. Unavoidable whenever the key space exceeds the table size.

Load Factor (α): Ratio of stored elements to capacity. Open addressing degrades sharply above ~0.7; chaining tolerates α > 1.

Open Addressing: Resolving collisions by probing for another slot within the table itself, rather than chaining externally.

Perfect Hashing: A collision-free hash for a known, fixed key set. Minimal perfect hashing maps n keys onto exactly n slots.

Universal Hashing: Choosing a hash function at random from a family, so that no fixed input is reliably bad. The defense against collision-flooding attacks.

Memory and Storage

Cache Line: The unit of transfer between memory and cache, typically 64 bytes. Reading one byte costs the same as reading its whole line.

Cache-Oblivious: Achieving optimal I/O performance without knowing the block size. By being well-organized at every scale simultaneously.

External Memory Model: A cost model counting block transfers rather than operations. Predicts real disk performance where the RAM model does not.

Locality: The tendency of an access pattern to touch nearby addresses. Sequential access has good locality; pointer chasing has none.

LSM Tree (Log-Structured Merge): A write-optimized structure that buffers writes in memory and flushes them as sorted immutable runs, converting random writes to sequential ones.

Page: The unit of transfer between memory and disk, typically 4KB.

Write Amplification: The ratio of bytes actually written to storage versus bytes logically written by the application.

Persistence and Concurrency

ABA Problem: A compare-and-swap succeeds because a pointer’s value is unchanged, even though the state it refers to has changed and changed back. Defended against with tagged pointers or hazard pointers.

CAS (Compare-and-Swap): An atomic hardware instruction that sets a memory location to a new value only if it currently holds an expected one. The universal primitive for lock-free programming.

Copy-on-Write: Sharing data until a write occurs, at which point the written portion is duplicated.

Linearizability: Every operation appears to take effect instantaneously at some moment between its call and return, consistent with real time. The standard correctness condition for concurrent objects, and notable for composing.

Lock-Free: Guaranteeing that some thread always makes progress. Weaker than wait-free, which guarantees every thread finishes in bounded steps.

MVCC (Multi-Version Concurrency Control): Keeping multiple versions of each row so readers see a consistent snapshot without blocking writers. Partial persistence, applied to databases.

Persistent: Preserving previous versions after modification. Partial persistence allows querying old versions; full allows updating them; confluent allows merging them. Unrelated to durable storage.

Path Copying: Achieving persistence by duplicating only the nodes on the path from root to the modification point, O(log n) per update in a balanced tree.

Structural Sharing: Reusing unchanged subtrees between versions of an immutable structure. What makes persistence affordable.

Distributed Systems

CAP Theorem: During a network partition, a distributed system must sacrifice either consistency or availability. See Appendix D for why “CA” is not a third option.

Consistent Hashing: Mapping keys and nodes onto a ring so that adding or removing a node remaps only ~1/n of keys, rather than nearly all of them.

CRDT (Conflict-Free Replicated Data Type): A structure whose merge is commutative, associative, and idempotent, so replicas converge without coordination.

DHT (Distributed Hash Table): A hash table partitioned across many machines, with a routing protocol for locating the responsible node.

Eventual Consistency: A guarantee that replicas converge given no further updates, with no bound on when.

Merkle Tree: A tree of hashes where each node hashes its children, allowing two large datasets to be compared (and their differences located)in logarithmic work.

Quorum: A subset of replicas that must acknowledge an operation. Overlapping read and write quorums (R + W > N) give strong consistency.

Vector Clock: A per-replica counter vector that distinguishes causally-ordered updates from genuinely concurrent ones.

Probabilistic and Compressed

Bloom Filter: A bit array with k hash functions giving approximate membership: false positives are possible, false negatives are not.

Count-Min Sketch: A fixed-size frequency estimator over a stream, which overestimates but never underestimates.

HyperLogLog: A cardinality estimator using the maximum leading-zero count of hashes, giving ~2% error in about 12KB regardless of set size.

Rank / Select: The two primitives underlying succinct structures. rank(i) counts 1-bits before position i; select(k) finds the position of the k-th 1-bit.

Succinct: Using space within a lower-order term of the information-theoretic minimum, while still supporting queries without decompressing.

Spatial and String

LCP Array: Longest Common Prefix between each pair of adjacent suffixes in a suffix array. Together they encode a suffix tree implicitly.

MBR (Minimum Bounding Rectangle): The smallest axis-aligned rectangle enclosing a set of objects. The key type in an R-tree, and overlap between sibling MBRs is what degrades R-tree queries.

Space-Filling Curve: A mapping from multi-dimensional coordinates to one dimension that mostly preserves locality, Z-order and Hilbert being the common ones. The basis of geohashing.

Suffix Array: The sorted list of a string’s suffix starting positions. Suffix-tree power at about 4 bytes per character rather than 20.

Trie: A tree keyed by character position, where lookup costs O(key length) independent of how many keys are stored.

Appendix D: Network and System Design Quick Reference

D.1 Distributed Consistency Levels