• 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