首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >avl树上的红黑树

avl树上的红黑树
EN

Stack Overflow用户
提问于 2012-12-13 12:17:49
回答 2查看 71K关注 0票数 137

除了节点中的红色和黑色之外,AVL和红色黑色树都是自平衡的。选择红黑树而不是AVL树的主要原因是什么?红黑树的应用是什么?

EN

回答 2

Stack Overflow用户

发布于 2017-10-12 03:45:08

多年来,我们对性能差异的理解有所提高,现在使用红黑树而不是AVL的主要原因是无法获得良好的AVL实现,因为它们稍微不太常见,可能是因为它们没有在CLRS中涵盖。

这两种树现在都被认为是rank-balanced trees的形式,但是红黑相间的树在about 20% in real world tests中总是更慢。当使用sequential data is inserted时,速度甚至要慢30-40%。

因此,研究过红黑树但不研究AVL树的人倾向于选择红黑树。Wikipedia entry for them上详细介绍了红黑树的主要用途。

票数 8
EN

Stack Overflow用户

发布于 2015-10-15 17:41:07

程序员通常不喜欢动态分配内存。avl树的问题是,对于"n“个元素,您至少需要log2(log2(n))...( height ->log2(n))位来存储树的高度!因此,当您处理大量数据时,您无法确定在每个节点上分配多少位来存储高度。

例如,如果您使用4字节int (32位)来存储高度。最大高度可以是: 2^32,因此可以在树中存储的元素的最大数量是2^(2^32) --(看起来很大,但在这个数据时代,我想没有什么是太大的)。因此,如果你超过了这个限制,你必须动态分配更多的空间来存储高度。

这是我所在大学的一位教授提出的答案,我觉得这是合理的!希望我说的有道理。

编辑:与红黑树相比,AVL树更加平衡,但它们在插入和删除期间可能会导致更多的旋转。因此,如果您的应用程序涉及许多频繁的插入和删除,那么应该首选Red Black树。如果插入和删除操作不太频繁,而搜索操作更频繁,则AVL树应该比Red Black树更好。--源GEEKSFORGEEKS.ORG

票数 -3
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/13852870

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档