Several state-of-the-art implementations of red-black trees are presented and evaluated. The techniques yield implementations of C++ standard-compatible set and map associative containers, which guarantee logarithmic worst-case performance, provide iterators with strict invalidation rules, and lower storage requirements to three, sometimes two, pointers per node. Lowering the storage requirements is important on modern platforms, where the efficiency of an implementation is more and more dependent on smaller storage and depends intricately on several factors, not all related to instruction count (such as efficient memory cache utilization). The code is entirely available online, including the various test drivers.

@report{BK2006R,
  author = {Herv\'{e} Br\"{o}nnimann and Jyrki Katajainen},
  title = {Efficiency of various forms of red-black trees},
  type = {CPH STL Report},
  number = {2006-2},
  institution = {Department of Computer Science, University of Copenhagen},
  year = {2006},
  pagetotal = {13},
}