Understanding Binary Search Trees

二叉搜索树可以说是计算机科学中最基本的非平凡类数据结构。尽管它们起源于计算机时代，但直到今天，对它们的完全理解仍然是难以捉摸的。二叉搜索树的一个令人惊讶的方面是，它们的在线和离线平摊性能被认为是相同的。这个项目试图完全描述计算的二叉搜索树模型。这项工作将允许未来的数据结构研究人员要么使用已被证明是动态最优的二叉搜索树，要么知道他们的问题需要走出二叉搜索树的领域。

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.