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.

Andersson trees are simple and easy to implement balanced binary search trees that are based on the foundations of red black trees. Consequently, Andersson trees have similar performance and structuring properties as red black trees without the difficult implementation.