Binary search trees are arguably the most fundamental nontrivial class of data structures in computer science. Despite their origins at the dawn of computing, a complete understanding has remained elusive to this day. A surprising aspect of binary search trees is that their online and offline amortized performance are conjectured to be identical. This project seeks to completely characterize the binary search tree model of computation. This work will allow future researchers in data structures either to use a binary search tree that has been shown to be dynamically optimal or to know that their problem requires stepping outside the realm of binary search trees.
