Red-black trees versus Andersson trees

Question

Why would anyone prefer Red-black tree to Anderssen tree, since the latter is much simpler than the former and it is said that it achieves practically the same performance in practice?

Answer 1

"It is said" (on the Wikipedia) that "[a] red-black tree is more consistent in its performance than an AA tree, but an AA tree tends to be flatter, which results in slightly faster search times." So R-B trees have as a first advantage that their performance is easier to predict, making them a good data structure for libraries (such as the original STL and C++ standard libraries derived from that).

Secondly, if you look at the source for the statement, you'll see two tables (p. 71 and 72) that indicate that AA trees need more comparisons to do deletions, and substantially more rotations for both insertion and deletion, in order to achieve the flatter trees. So there's a trade-off here: when comparisons are cheap but updates are frequent, a red-black tree might outperform an AA tree; otherwise, when comparisons are expensive but lookups are more frequent than updates, the AA tree might win.

Interestingly, this tradeoff is very similar to that between red-black trees and AVL trees. A comparison of AVL trees and AA trees would be even more interesting.