Suggested Final Project Topics

Why they're worth studying: Scapegoat trees use a weight-balancing scheme commonly used in other

balanced trees, but which we didn't explore in this course. They're also amazingly easy to implement, and

you should probably be able to easily get performance numbers comparing them against other types of

trees (say, AVL trees or red/black trees.)

Splay Tree Variations

Splay trees tend to work well in practice, but splaying can be quite expensive. Since splay trees have been

introduced, there have been a number of variations proposed that attempt to match many of the theoreti-

cal guarantees of splay trees but with lower constant factors. These range from simple variations like only

splaying every kth operation to probabilistically splaying on each access.