locality is *finger search*. In finger search trees, the cost of an access is typically $O(\log{d})$,[^1] where $d$ is the difference in rank between the accessed item and a *finger* ($d$ may be much smaller than $n$). The finger indicates the starting point of the search, and is either given by the user, or (more typically) it points to the previously accessed item. Several special purpose tree-like data structures have been designed to support finger search.[^2]

In 1983, Sleator and Tarjan [@ST85] introduced Splay trees, a particularly simple and elegant “self-adjusting” BST algorithm. In 2000, Cole et al. [@finger1; @finger2] showed that Splay matches (asymptotically) the efficiency of finger search, called in this context the *dynamic finger* property. This is remarkable, since Splay uses no explicit fingers; every search starts from the root. The result shows the versatility of the BST model, and has been seen as a major (and highly nontrivial) step towards “dynamic optimality”, the conjecture of Sleator and Tarjan that Splay trees are constant-competitive.

BSTs can also adapt to other kinds of locality. The *working set* property [@ST85] requires the amortized cost of accessing $x$ to be $O(\log{t})$, where $t$ is the number of distinct items accessed 