红黑树与Andersson树

Question

4

为什么有人会更喜欢红黑树而不是Anderssen树，因为后者比前者简单得多，据说在实践中可以实现几乎相同的性能？

- blazs

3

即使你提供的维基文章已经表明RBL具有更加稳定的性能。 - Esailija

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Fred Foo · Accepted Answer

据维基百科上所说，“红黑树在性能方面比AA树更加稳定，但是AA树更加扁平，因此搜索时间略快。” 因此，R-B树的第一个优点是其性能更易预测，使其成为库（例如最初的STL和由此派生的C++标准库）的良好数据结构。

其次，如果您查看该声明的来源，您会看到两个表格（第71页和72页），这些表格表明AA树需要更多比较来执行删除，并且在插入和删除时需要更多旋转以实现更扁平的树。因此，在这里存在一种折衷：当比较便宜而更新频繁时，红黑树可能优于AA树；否则，当比较昂贵但查找比更新频繁时，AA树可能获胜。

有趣的是，这种权衡与红黑树和AVL树之间的权衡非常相似。比较AVL树和AA树将更加有趣。