Fre*_*Foo
5
"据说"(在维基百科上)"[a]红黑树的表现比AA树更稳定,但AA树往往更平坦,这导致搜索时间略快." 因此RB树的第一个优势是它们的性能更容易预测,使它们成为库的良好数据结构(例如从中衍生出来的原始STL和C++标准库).
其次,如果你查看语句的来源,你会看到两个表(第71页和第72页)表明AA树需要更多的比较来进行删除,并且插入和删除的旋转要多得多,以便实现更平坦的树木.所以这里有一个权衡:当比较便宜但更新频繁时,红黑树可能胜过AA树; 否则,当比较昂贵但查找比更新更频繁时,AA树可能会赢.
有趣的是,这种权衡与红黑树和AVL树之间的权衡非常相似.AVL树和AA树的比较会更有趣.