A new class of balanced search trees : half-balanced binary search tress H. J. Olivié RAIRO. Inform. théor., 16 1 (1982) 51-71 Published online: 01 February 2017 DOI: 10.1051/ita/1982160100511