  An optimal binary search tree for an access sequence on elements is a static
tree that minimizes the total search cost. Constructing perfectly optimal
binary search trees is expensive so the most efficient algorithms construct
almost optimal search trees. There exists a long literature of constructing
almost optimal search trees dynamically, i.e., when the access pattern is not
known in advance. All of these trees, e.g., splay trees and treaps, provide a
multiplicative approximation to the optimal search cost.
  In this paper we show how to maintain an almost optimal weighted binary
search tree under access operations and insertions of new elements where the
approximation is an additive constant. More technically, we maintain a tree in
which the depth of the leaf holding an element $e_i$ does not exceed
$\min(\log(W/w_i),\log n)+O(1)$ where $w_i$ is the number of times $e_i$ was
accessed and $W$ is the total length of the access sequence.
  Our techniques can also be used to encode a sequence of $m$ symbols with a
dynamic alphabetic code in $O(m)$ time so that the encoding length is bounded
by $m(H+O(1))$, where $H$ is the entropy of the sequence. This is the first
efficient algorithm for adaptive alphabetic coding that runs in constant time
per symbol.
