表现 – 红黑树与安德森树

表现 – 红黑树与安德森树,第1张

概述为什么有人会更喜欢 Red-black tree到 Anderssen tree,因为后者比前者简单得多,据说它在实践中达到了几乎相同的性能? “据说”(在维基百科上)“[a]红黑树表现比AA树更稳定,但AA树往往更平坦,这导致搜索时间略快.”因此,R-B树的第一个优势是它们的性能更容易预测,使它们成为库的良好数据结构(例如从中衍生出来的原始STL和C标准库). 其次,如果你看一下source 为什么有人会更喜欢 Red-black tree到 Anderssen tree,因为后者比前者简单得多,据说它在实践中达到了几乎相同的性能?解决方法 “据说”(在维基百科上)“[a]红黑树的表现比AA树更稳定,但AA树往往更平坦,这导致搜索时间略快.”因此,R-B树的第一个优势是它们的性能更容易预测,使它们成为库的良好数据结构(例如从中衍生出来的原始STL和C标准库).

其次,如果你看一下source for the statement,你会看到两张表(第71页和第72页)表明AA树需要进行更多的比较以进行删除,并且插入和删除的旋转要多得多,以便实现更平坦树木.所以这里有一个权衡:当比较便宜但更新频繁时,红黑树可能胜过AA树;否则,当比较昂贵但查找比更新更频繁时,AA树可能会赢.

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

总结

以上是内存溢出为你收集整理的表现 – 红黑树与安德森树全部内容,希望文章能够帮你解决表现 – 红黑树与安德森树所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/web/1129420.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-30
下一篇 2022-05-30

发表评论

登录后才能评论

评论列表(0条)

保存