(Mathematical expressions are simplified in this html-dokument. They should be readable enough to get the flavour.)
We focus on the problem of maintaining binary search trees with
an optimal and near-optimal number of incomplete levels.
For a binary search tree with one incomplete level and
a height of exactly
ceiling(log (n+1)), we improve the amortized
insertion cost to O(log^3 n).
A tree with 2 incomplete levels and a near-optimal height of
ceiling(log (n+1)+epsilon) may be maintained with
O(log^2 n) amortized restructuring work per update.
The amount of restructuring work is decreased to O(log n)
by increasing the number of incomplete levels to 4,
while the height is still kept as low as
ceiling(log (n+1)+epsilon).
This yields an improved amortized bound on the dictionary problem.
Trees of optimal and near-optimal height may be
represented as a pointer-free structure in an array of size O(n).
In this way we obtain an array
implementation of a dictionary with O(log n) search cost
and O(log^2 n) update cost,
allowing interpolation search to improve the expected search time.