除了节点中的红色和黑色之外,AVL和红色黑色树都是自平衡的。选择红黑树而不是AVL树的主要原因是什么?红黑树的应用是什么?
发布于 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上详细介绍了红黑树的主要用途。
发布于 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
https://stackoverflow.com/questions/13852870
复制相似问题