1 Introduction
1.1 Related Work
2 Notation and Preliminaries
2.1 The Distributional Master Theorem
3 Jumplists
3.1 Dangling-Min BSTs
4 Spine Search
5 Median-of-k Jumplists
6 Insert and Delete
7 Analysis
7.1 Search Costs
7.2 Insertion Costs
7.3 Deletion Costs
7.4 Memory Requirements
8 Conclusion
8.1 Future Work
Appendix
A Index of Notation
A.1 Generic Mathematical Notation
A.2 Stochastics-related Notation
A.3 Notation for Jumplists and Analysis
B Comparison of Jumplist Definitions
C Algorithms
C.1 Rebalance
C.2 Insert
C.3 Delete
C.4 Pseudocode
D Omitted proofs
References