@Mr Crash: Have you read http://attractivechaos.wordpress.com/2008/10/02/comparison-of-binary-search-trees/ ?