I am wondering how Tarjan's Top-Down red black tree algorithm fares against other red black tree algorithms (e.g. the one by Robert Sedgewick). Has anyone compared the results of various top-down and bottom-up algorithms? Please let me know as it would help in deciding which algorithm I need to have as the base algorithm as I plan to make it concurrent later on. (I would like a comparison not just between top-down vs. bottom-up but also between the various algorithms by these researchers as well!)
From what I could find, there have been little work in this area. There are some performance tests that have been ran between different balanced BST (AVL vs RB vs splay), but to my knowledge, those ran for variants of red-black trees are anecdotal: benchmark of one variant of RB tree against the "standard" implementation on one specific case.
So, if you're decided to implement a red-black tree, you should select a few variants, a language and benchmark them according to your use cases. You can find some open source implementations of different kinds of red-black trees across the net, here are a few main flavors that I'm aware of:
Those implementation are space efficient because they all have the common point of not using parent pointer. However, you should benchmark them properly, and optimize them if needed.