(3) a multiplicative-weights scheme for learning a tree metric in an online fashion.

The fact that “vanilla” BSTs can, with a low overhead, simulate a much more powerful computational model further indicates the strength and versatility of the BST model. As an application, we show that our online BST algorithms satisfy a restricted form of the *unified property*; previously no (online or offline) BST was known to satisfy such a property.

If there is a constant-competitive BST algorithm, then it must match our $k$-finger bounds. The two most promising candidates, Splay and Greedy BST (see e.g. [@in_pursuit]) were only shown (with considerable difficulty) to satisfy variants of the one-finger, i.e. lazy finger property. To obtain our online BSTs competitive for other values of $k$, we combine sophisticated tools developed for other online problems, as well as our refinement of a previous (highly nontrivial) construction for simulating multiple fingers. These facts together may hint at the formidable difficulty (more pessimistically: the low likelihood) of attaining dynamic optimality by simple and natural BST algorithms such as Splay or Greedy.

##### BST and finger models. Main results. {#bst-and-finger-models.-main-results. .unnumbered}

Now, we introduce the formal statements of our results. In the dynamic BST model 