A. Andersson and T. W. Lai. Fast updating of well-balanced trees.
In Proc. Scandinavian Workshop on Algorithm Theory, pages 111--121. Springer Verlag, 1990.

(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.

Full paper (postscript)
Full paper (pdf)