We will now examine ways to guarantee O(lg n) running time for these operations in all BSTs.
The first of these mechanisms is called a "Splay" Tree. Splay trees do not guarantee that every operation will be O(lg n),
but instead strive to make the amortized running time of m operations be O (m lg n). Some operations will be as bad
as O(n), but over time, O(lg n) running time is achieved.
Notes for class 17 are available in both HTML and postscript formats.