(Mathematical expressions are simplified in this html-dokument. They should be readable enough to get the flavour.)
We consider the problem of updating a binary search tree in $O(\log n)$
amortized time while using as few comparisons as possible. We show that a
tree of height $\lceil\log (n+1)+1/\!\sqrt{\log(n+1)}\rceil$
can be maintained in
$O(\log n)$ amortized time such that the difference between the longest and
shortest paths from the root to an external node is at most $2$.
We also study the problem of sorting and searching in the {\it slow write}
model of computation, where we have a constant size cache of fast memory
and a large amount of memory with a much slower writing time than reading
time. In such a model, it is important to sort using only $\Theta(n)$ writes
into the slower memory. We say that such algorithms are {\it write optimal},
and we introduce a $O(n\log n)$ time, write-optimal sorting algorithm that
requires only $n\log n+O(n)$ comparisons in the worst case. No previous
sorting algorithm that performs $n\log n+o(n\log n)$ comparisons in the worst
case had previously been shown to be write optimal.
The above results are based on a class of trees called $k$-stratum trees, which
can be viewed as a generalization of stratified search trees.