performance - 红黑树与安德森树

Question

为什么有人会喜欢 Red-black tree至 Anderssen tree ，因为后者比前者简单得多，据说它在实践中达到了几乎相同的性能？

Answer 1

“据说”(在维基百科上)“[a] 红黑树的性能比 AA 树更一致，但 AA 树往往更平坦，这导致搜索时间稍快。 “所以 R-B 树的第一个优势是它们的性能更容易预测，这使它们成为库的良好数据结构(例如从中派生出的原始 STL 和 C++ 标准库)。

其次，如果您查看 source for the statement ，您会看到两个表(第 71 页和第 72 页)，它们表明 AA 树需要更多的比较来进行删除，并且需要更多的旋转来插入和删除，以获得更平坦的树。所以这里有一个权衡:当比较便宜但更新频繁时，红黑树可能优于 AA 树；否则，当比较代价高昂但查找比更新更频繁时，AA 树可能会获胜。

有趣的是，这种权衡与 red-black trees and AVL trees 之间的权衡非常相似. AVL 树和 AA 树的比较会更有趣。