Review

We want to support fast insertions, deletions, and finds into a binary search tree.

Standard binary search trees don't cut it because operations take too long: as much as $\Theta(n)$ for stringy trees.

Balanced binary search trees remedy this, but are complex to implement, and rebalancing has a fair amount of overhead.

Splay trees are easy to implement, but tricky to analyze. They give bushy trees in an amortized sense, that we will discuss.