Bottom up Red/Black Trees: The simplicity of LLRB Trees, with none of the penalty.
On my shelf I have books by no less than 7 different authors that contain sections on implementing Red/Black Tree’s. Almost all of them begin with an introduction to 2-3-4 tree’s. In addition, almost all of them detail algorithms that restructure the tree both top down and bottom up during insertion, or briefly discuss bottom up insertion and then detail top-down algorithms. What is perhaps the most widely known version, which appears in CLRS, is an overly-complex iterative implementation requiring parent pointers to perform it’s bottom up balancing.
In response to this perceived complexity, both AA trees and Left-Leaning Red/Black trees were introduced, which simplified their implementations by enforcing asymmetry in their balancing. What do I mean by “enforcing asymmetry”? In a “Traditional” red black tree, a red node can appear as either a left or right child of a black node – or even as both if they are leaf nodes. In a “Left Leaning Red/Black Tree” however, a red node can only occur as the left child of a node. AA tree’s, an earlier adaptation of Red/Black trees perform this same trick, except slanting to the right. This reduces the number of cases we need to handle during restructuring essentially in half. But does it *really*?
Unfortunately this perceived simplicity is at the cost of performance. Despite having fewer cases to deal with when it comes to restructuring, they have to perform those few cases more often, as their are fewer valid asymmetric red/black tree’s than there are symmetric. Take as an example the two trees pictured above. Both tree’s were built from the same input, but the left leaning variety required 17 right rotations to the red/black tree’s 11 right rotations. They don’t fare any better for left rotations either, requiring 29 left rotations compared to the red/black tree’s 10 left rotations. That’s three times the work for a tree that ends up less balanced.
