Suggested Final Project Topics

Why they're worth studying: Despite their nice theoretical guarantees, splay trees aren't often used in

practice due to a combination of their amortized-efficient guarantees and the practical costs of splaying. If

you're interested in exploring that annoying gap between theory and practice, consider checking these

variations out!

The Geometric Lower Bound

There's been a recent development in the quest for the optimal binary search tree: a lower bound called

the geometric lower bound based on casting binary search tree lookups in a geometric setting. This lower

bound has been used to design a new type of dynamic binary search tree that is conjectured to be optimal

and looks quite different from the other trees we've studied this quarter.