I'm impressed that there is still room to eke performance improvements out by fiddling with the base data structure, the original author has been working on refining it for quite a while*

* http://t-t-travails.blogspot.com/2008/07/treaps-versus-red-b..., http://t-t-travails.blogspot.com/2010/04/red-black-trees-rev...