avl树上的红黑树

Question

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

Answer 1

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

red-black trees和AVL trees都是最常用的balanced binary search trees，它们都支持在有保证的O(logN) time中插入、删除和查找。但是，两者之间有以下比较点：

• AVL树更加严格平衡，因此提供了更快的查找速度。因此，对于查找密集型任务，使用AVL树。
• 对于插入密集型任务，使用红黑树。
• AVL树存储每个节点的平衡因子。这会占用O(N)额外的空间。但是，如果我们知道将插入树中的键总是大于零，我们可以使用键的符号位来存储红黑树的颜色信息。因此，在这种情况下，红黑树不会占用额外的空间。

红黑树有什么应用？

红黑相间的树更具通用性。它们在添加、删除和查找上做得相对较好，但AVL树具有更快的查找速度，但代价是添加/删除速度较慢。红黑树用于以下情况：

java.util.TreeSet

• C++

• Java：java.util.TreeMap，java.util.TreeSet

• C++ STL (在大多数实现中)：map，multimap，multiset

• Linux内核:完全公平的调度器，linux/rbtree.h

Answer 2

尝试读取此article

它提供了一些关于不同、相似、性能等方面的很好的见解。

下面是这篇文章中的一句话：

AVL树和

树一样，都是自平衡的。它们都提供O(log )查找和插入性能。

不同之处在于，RB树保证每次插入操作O(1)次旋转。这就是实际实现中性能的实际成本。

简化后，RB树在概念上是2-3棵树，无需携带动态节点结构的开销，从而获得了这一优势。在物理上，RB树被实现为二叉树，红色/黑色标志模拟2-3行为

据我所知，AVL树和RB树在性能方面并不是很远。RB树仅仅是B树的变体，并且平衡的实现方式与AVL树不同。

Answer 3

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

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

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