Left-Leaning Red-Black Trees

Red-Black Trees were originally designed by taking a 2-3-4 tree and unrolling the big nodes into a cluster of simpler binary tree nodes. The 2-3-4 node operations are mapped to binary tree operations. Now Robert Sedgewick presented a new tree called Left-Leaning Red-Black Tree.

A Red-Black tree has a lot of cases you have to consider, especially if you delete a node. This makes the code complex. Left-Leaning Red-Black Trees are a simpler variant of Red-Black Trees. They are simpler to implement (less code) while maintaining the nice features of Red-Black Trees. Less code means faster insertion and deletion, but there are no benchmarks yet.

Once Bob released his new book this would be a nice improvement for csync in the future. You can take a look at the slides of his talk.