ABSTRACT:

The red-black tree model for implementing balanced search trees, introduced by Guibas and Sedgewick 30 years ago, is now found throughout our computational infrastructure. Red-black trees are the underlying data structure in the symbol-table implementation in C++, Java, Python, BSD Unix, and many other modern systems. However, current implementations have sacrificed some of the original design goals, so a new look is worthwhile. In this talk, we describe a new variant of red-black trees that leads to substantially simpler code, less than one-fourth as much code as in implementations in common use. Can we analyze average-case performance for this new, simpler version?