  It is shown that the online binary search tree data structure GreedyASS
performs asymptotically as well on a sufficiently long sequence of searches as
any static binary search tree where each search begins from the previous search
(rather than the root). This bound is known to be equivalent to assigning each
item $i$ in the search tree a positive weight $w_i$ and bounding the search
cost of an item in the search sequence $s_1,\ldots,s_m$ by $$O\left(1+ \log
\frac{\displaystyle \sum_{\min(s_{i-1},s_i) \leq x \leq
\max(s_{i-1},s_i)}w_x}{\displaystyle \min(w_{s_i},w_{s_{i-1}})} \right)$$
amortized. This result is the strongest finger-type bound to be proven for
binary search trees. By setting the weights to be equal, one observes that our
bound implies the dynamic finger bound. Compared to the previous proof of the
dynamic finger bound for Splay trees, our result is significantly shorter,
stronger, simpler, and has reasonable constants.
