26. Splay trees and the dynamic optimality conjecture
From Jeff Erickson
…Read more Less…
- Splay trees
- Amortized time via potential function
- Access Lemma ⇒ O(log n) amortized time per splay
- Generalized Access Lemma ⇒ static optimality
- What is a "dynamic BST"?
- Geometric view of dynamic BSTs: satisfied supersets
- GreedyFuture, GreedyPast, and GreedyBST
- One-sided greedy lower bound!