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*<p>* <a href="http://t-t-travails.blogspot.com/2008/07/treaps-versus-red-black-trees.html" rel="nofollow">http://t-t-travails.blogspot.com/2008/07/treaps-versus-red-b...</a>, <a href="http://t-t-travails.blogspot.com/2010/04/red-black-trees-revisited.html" rel="nofollow">http://t-t-travails.blogspot.com/2010/04/red-black-trees-rev...</a>