metrics. To our knowledge, this is the first time when tools developed for the $k$-server problem are used in BSTs. As an application of our $k$-finger results, we show that BSTs can efficiently serve queries that are *close to some recently accessed item*. This is a (restricted) form of the *unified property* (Iacono, 2001) that was previously not known to hold for any BST algorithm, online or offline.
author:
- Parinya Chalermsook
- Mayank Goswami
- László Kozma
- Kurt Mehlhorn
- Thatchaphol Saranurak
bibliography:
- 'article.bib'
title: 'Multi-finger binary search trees'
---

Introduction
============

The binary search tree (BST) is the canonical comparison-based implementation of the dictionary data type for maintaining ordered sets. Dynamic BSTs can be re-arranged after every access via rotations and pointer moves starting from the root. Various ingenious techniques have been developed for dynamically maintaining balanced BSTs, supporting search, insert, delete, and other operations in time $O(\log{n})$, where $n$ is the size of the dictionary (see e.g. [@Knuth3 §6.2.2], [@Mehlhorn84 §5]).

In several applications where the access sequence has strong *locality of reference*, the worst-case bound is too pessimistic (e.g. in list merging, adaptive sorting, or in various geometric problems). A classical technique for exploiting 