A. Andersson. Balanced search trees made simple.
In Proc. Workshop on Algorithms and Data Structures, pages 60--71. Springer Verlag, 1993.

As a contribution to the recent debate on simple implementations of dictionaries, we present new maintenance algorithms for balanced trees. In terms of code simplicity, our algorithms compare favourably with those for deterministic and probabilistic skip lists.

Full paper (postscript)
Full paper (pdf