Suggested Final Project Topics

Why they’re worth studying: Queaps combine a number of beautiful theoretical ideas – repurposing a

2-3-4 tree to act as a queue, analyzing data structures with respect not to the worst case but to the actual

performance – etc. This would be a great way to combine lots of clever ideas from this class together into

a single spot, and we’d be curious to see how well it holds up in practice!

Multisplay Trees

Tango trees (described earlier in the section on balanced trees) combine together multiple red/black trees

and are never worse than a factor of O(log log n) than the best possible binary search tree. If you replace

the red/black trees with splay trees, you get the multisplay tree, which is also never worse than a factor of

O(log log n) from the best possible binary search tree. However, due to some of the properties of splay

trees, we also know that multisplay trees have a number of other useful, amazing properties.