main page — CS 650 Advanced Data Structures
Unit 2: Adaptive Trees
This unit covers:
- move-to-root heuristics for binary search trees
- splay trees
- lazy search trees
Material
- preliminary slides
- Video 2-1 (2026-04-27):
Move-to-root heuristics
- Video 2-2 (2026-04-28):
Move-to-Root Analysis
- Video 2-3 (2026-04-28):
Splay Trees
- Video 2-4 (2026-04-28):
Splay Tree Analysis prelude
- Video 2-5 (2026-05-04):
Splay Tree Analysis: Access Lemma
- Video 2-6 (2026-05-04):
Splay Tree Analysis: Adaptive Properties
- Video 2-7 (2026-05-05):
Biased Search Trees
- Video 2-8 (2026-05-05):
Online Algorithms and Competitive Analysis
- Video 2-9 (2026-05-05):
Dynamic Optimality I: The Splay Tree Conjecture
- Video 2-10 (2026-05-05):
Dynamic Optimality II: Properties of BSTs
- Video 2-11 (2026-05-05):
Geometric View of BSTs
Further sources
The move-to-root heuristics and splay trees were introduced in the following papers, and the presentation follows their original presentation:
- Allen and Munro. Self-Organizing Binary Search Trees (1978)
- Sleator and Tarjan. Self-Adjusting Binary Search Trees (1985)
The intro to online algorithms and competitive analysis is inspired by
- Cormen et al., Introduction to Algorithms, 3rd Edition (2009)
Dynamic optimality definitions follow the diligent setup in Lászlò Kozma’s PhD thesis with lots of summaries and open problems on dynamic optimality of BSTs.
The presentation of the geometry view follows:
- Erik Demaine, Advanced Data Structures (MIT OpenCourseWare, 2012)
Lectures on Dynamic Optimality