Suggested Final Project Topics

Why they're worth studying: RAVL trees were motivated by practical performance concerns in data-

base implementation and a software bug that caused significant system failures. They also have some very

interesting theoretical properties and use an interesting type of potential function in their analysis. If

you're interested in exploring the intersection of theory and practice, this may be a good structure to ex-

plore.

B

+

 Trees

B

+

-trees are a modified form of B-tree that are used extensively both in databases and in file system de-

sign. Unlike B-trees, which store keys at all levels in the tree, B+ trees only store them in the leaves. That,

combined with a few other augmentations, make them extremely fast in practice.