在avl树的红色黑树

Question

在avl树的红色黑树

sur*_*ren 81 algorithm red-black-tree data-structures

除了节点中的红色和黑色外,AVL和红黑树都是自平衡的.选择红黑树而不是AVL树的主要原因是什么？红黑树有哪些应用？

Answer 1

Nik*_*nka 92

选择红黑树而不是AVL树的主要原因是什么？

红黑树和AVL树都是最常用的平衡二叉搜索树,它们支持插入,删除和查找保证O(logN) time.但是,两者之间有以下几点比较:

AVL树更加严格平衡,因此可以提供更快的查找效果.因此,对于查找密集型任务,使用AVL树.
对于插入密集型任务,请使用红黑树.
AVL树在每个节点存储平衡因子.这需要O(N).但是,如果我们知道将插入树中的键总是大于零,我们可以使用键的符号位来存储红黑树的颜色信息.因此,在这种情况下,红黑树需要java.util.TreeMap.
通常,AVL树的旋转比红黑树的旋转更难实现和调试.

红黑树的应用是什么？

红黑树更通用.它们在添加,删除和查找方面表现相对较好,但AVL树的查找速度更快,代价是添加/删除速度较慢.红黑树用于以下内容:

Java:java.util.TreeMap,java.util.TreeSet.
C++ STL:map,multimap,multiset.
Linux内核:完全公平的调度程序,linux/rbtree.h

`通常,AVL树的旋转比红黑树更难实现和调试.不是这样. (35认同)
存储在AVL树的每个节点中的平衡因子是两位(-1/0/+1).红黑树在每个节点中存储一位颜色信息.因此,总共两棵树都需要O(N)存储器来获取额外信息. (18认同)
为了迂腐,C++标准并没有强制要求`std :: map`和朋友使用任何特定的结构.这是留给实现的,虽然libstdc ++和Dinkumware至少使用了红黑树,看起来你在实践中是对的. (8认同)
"对于插入密集型任务,请使用红黑树." 为什么？AVL树插入最坏的情况下只旋转一次,而红黑树则需要两次旋转. (4认同)
值得一提的是，在 Java 8 中，如果存储桶中的链表长度超过 8，HashMap 将使用红黑树。 (2认同)
该数据应根据Ben Pfaff在2003年对BST性能的分析进行更新-AVL树具有更广泛的用途，并且性能更好。追踪Java，C ++和Linux内核选择较慢实现的确切历史原因将很有趣。 (2认同)
@Daniel 对于 AVL 树的平衡成本有很多 FUD；事实是，它们几乎完全相同，只是 AVL 树决定稍微更频繁地旋转。因此，顺序随机化的插入密集型工作负载最终可能会浪费工作。一般来说，我很确定 AVL 树在大多数情况下仍然更好，特别是因为即使在插入繁重的工作负载中，当项目已经排序时旋转也是有用的 - 并且数据通常已经排序。 (2认同)

Answer 2

jor*_*dan 10

试着阅读这篇文章

它提供了一些关于差异,相似性,性能等的好的见解.

这是文章的引用:

RB-Trees和AVL树一样,是自平衡的.它们都提供O(log n)查找和插入性能.

不同之处在于RB-Trees保证每次插入操作的O(1)旋转.这实际上是实际成本中的性能成本.

简化后,RB-Trees从概念上成为2-3个树,而不会带来动态节点结构的开销.物理RB树实现为二叉树,红/黑标志模拟2-3行为

就我自己的理解而言,AVL树和RB树在性能方面并不是很遥远.RB树只是B树的变体,并且平衡的实现方式与AVL树不同.

AFIAK，AVL 树每次插入也有 O(1) 旋转。对于 RB 树和 AVL - 一次插入可能有 1 或 0 次旋转。如果发生旋转，算法就会停止。如果它没有发生，通常，算法会继续从树的底部到根检查/重绘节点。因此，有时旋转 O(1) 会更好，因为它消除了扫描剩余项目 O(log(n))。因为平均而言，AVL 树会产生更多的旋转，所以 AVL 树通常比 RB-tree 2 log(N) 具有更好的平衡 ~1.44 log(N)。 (2认同)

Answer 3

Dav*_*mon 8

多年来，我们对性能差异的理解有所改善，现在在 AVL 上使用红黑树的主要原因是无法获得良好的 AVL 实现，因为它们不太常见，也许是因为它们没有包含在 CLRS 中。

这两种树现在都被认为是等级平衡树的形式，但红黑树在现实世界的测试中始终慢约 20%。甚至在插入顺序数据时慢 30-40% 。

所以研究过红黑树而不研究AVL树的人往往会选择红黑树。红黑树的主要用途在Wikipedia 条目中有详细说明。

有趣的！在我的阅读中，libavl 的文章似乎在说 AVL 和 RB 是正面交锋的，并且总体而言两者都不是很明显（哪个更好取决于工作量）。我没有看到任何声称 AVL 总体上快 20% 的说法。 (2认同)

归档时间：	13 年，2 月前
查看次数：	46002 次
最近记录：	6 年，5 月前