Comment by Polyisoprene

I believe Splay trees are usually mentioned as an alternative.