4 Red-Black Trees
Algebraic Data Types 50
Pattern Matching and Recursion 51
Tree Diagrams 53
Insertion 56
Balancing 59
Collection 63
Performance 70
5 The Copy-On-Write Optimization
Basic Definitions 75
Rewriting Simple Lookup Methods 77
Tree Diagrams 79
Implementing Copy-On-Write 79
Insertion 82
Implementing Collection 85
Examples 93
Performance Benchmarks 95
6 B-Trees
B-Tree Properties 102
Basic Definitions 105
The Default Initializer 106
Iteration with forEach 109
Lookup Methods 110
Implementing Copy-On-Write 111
Utility Predicates 113
Insertion 113
Implementing Collection 117
Examples 127
Performance Summary 128
