在avl树的红色黑树
AVL和红黑树都是自平衡的，除了红色和黑色的节点。 select红黑树而不是AVL树的主要原因是什么？ 红黑树有什么用途？
select红黑树而不是AVL树的主要原因是什么？
红黑树和AVL树是最常用的平衡二叉search树，它们支持保证O(logN) time插入，删除和查找。 但是，两者之间有以下几点比较：
- AVL树更加严格的平衡，因此提供更快的查找。 因此，对于查找密集型任务，使用AVL树。
- 对于插入密集型任务，请使用红黑树。
- AVL树存储每个节点的平衡因子。 这需要
O(N) extra space。 但是，如果我们知道将要插入树中的键总是大于零，我们可以使用键的符号位来存储红黑树的颜色信息。 因此，在这种情况下，红黑树需要O(1) extra space。 - 一般来说，AVL树的旋转比红黑树更难实现和debugging。
红黑树有什么用途？
红黑树更通用。 他们在添加，删除和查找方面做得相对较好，但AVL树以较慢的添加/删除为代价，查找速度更快。 红黑树用于以下：
- Java：java.util.TreeMap，java.util.TreeSet。
- C ++ STL：map，multimap，multiset。
- Linux内核：完全公平的调度程序，linux / rbtree.h
尝试阅读这篇文章
它提供了一些有关差异，相似性，性能等方面的很好的见解。
这里有一篇文章的引用：
RB树和AVL树都是自平衡的。 它们都提供O（log n）查找和插入性能。
不同的是RB-Trees保证每个插入操作的O（1）旋转。 这实际上是在实际执行中花费性能的成本。
简化的RB树从概念上是从2-3树中获得这个优点，而不会带来dynamic节点结构的开销。 物理RB树被实现为二叉树，红/黑旗模拟2-3行为
就我自己的理解而言，AVL树和RB树在性能方面并不是很遥远。 RB树只是B树的一个变体，平衡的实现与AVL树不同。
程序员通常不喜欢dynamic分配内存。 avl树的问题是，对于“n”个元素，您需要至lesslog2（log2（n））…（height-> log2（n））位来存储树的高度！ 所以当你处理大量的数据时，你不能确定在每个节点上存储多less位来存储高度。
例如，如果使用4个字节的int（32位）来存储高度。 最大高度可以是：2 ^ 32，因此树中可以存储的元素的最大数量是2 ^（2 ^ 32） – （似乎非常大，但是在这个数据时代，我估计没有太大的值）。 因此，如果你超过这个限制，你必须dynamic分配更多的空间来存储高度。
这是我大学教授提出的一个答案，对我来说似乎是合理的！ 希望我有道理。
编辑：与红黑树相比，AVL树更加平衡，但是在插入和删除过程中可能会引起更多的旋转。 所以如果你的应用程序涉及很多频繁的插入和删除，那么红黑树应该是首选。 如果插入和删除的频率较低，search操作更频繁，那么AVL树应优先于红黑树。 – 来源GEEKSFORGEEKS.ORG
AVL树的重新平衡应该符合下面的属性。 （维基参考 – AVL树 ）
在AVL树中，任意节点的两个子子树的高度最多相差一个; 如果在任何时候它们相差超过一个，则重新平衡以恢复这个财产。
所以这意味着AVL树的整体高度不会发生变化，即AVL树的查找效果会更好。 而且由于要做额外的操作（旋转）而不让高度发疯，所以树修改操作可能会花费很大的代价。
其他的答案在这里总结了RB和AVL树的优点和缺点，但是我发现这个区别特别有趣：
AVL树不支持不断的摊销更新成本 [但红黑树]
来源： Mehlhorn＆Sanders（2008） （第7.4节）
因此，虽然RB和AVL树都保证O（log（N））查找，插入和删除的最坏情况时间，但插入或删除节点后恢复AVL / RB属性可以在O（1） 分摊时间红黑树。
我们对性能差异的理解多年来有所改善，现在使用红黑树超过AVL的主要原因是没有获得良好的AVL实现，因为它们稍微不太常见，也许是因为它们不在CLRS中。
现在，这两棵树被认为是平衡树木的forms，但在现实世界的testing中，红黑树木一直比现在慢20％左右 。 甚至在插入顺序数据时速度降低30-40％。
所以研究过红黑树而不是AVL树的人倾向于select红黑树。 红黑树的主要用途详见Wikipedia条目 。
