除了节点中的红色和黑色外，AVL和红黑树都是自平衡的。选择红黑树而不是AVL树的主要原因是什么？红黑树有哪些应用？
选择红黑树而不是AVL树的主要原因是什么？
红黑树和AVL树都是最常用的平衡二叉搜索树，它们支持保证O(logN) time中的插入，删除和查找。但是，两者之间有以下几点比较：
O(N) extra space。但是，如果我们知道将插入树中的键总是大于零，我们可以使用键的符号位来存储红黑树的颜色信息。因此，在这种情况下，红黑树需要O(1) extra space。红黑树的应用是什么？
红黑树更通用。它们在添加，删除和查找方面表现相对较好，但AVL树的查找速度更快，代价是添加/删除速度较慢。红黑树用于以下内容：
试试看这个article
它提供了一些关于差异，相似性，性能等的好的见解。
这是文章的引用：
RB-Trees和AVL树一样，是自平衡的。它们都提供O（log n）查找和插入性能。
不同之处在于RB-Trees保证每次插入操作的O（1）旋转。这实际上是实际成本中的性能成本。
简化后，RB-Trees从概念上成为2-3个树，而不会带来动态节点结构的开销。物理RB树实现为二叉树，红/黑标志模拟2-3行为
就我自己的理解而言，AVL树和RB树在性能方面并不是很遥远。 RB树只是B树的变体，并且平衡的实现方式与AVL树不同。
多年来，我们对性能差异的理解有所改善，现在使用红黑树而不是AVL的主要原因是无法获得良好的AVL实施，因为它们稍微不那么常见，可能是因为它们不在CLRS中。
这两棵树现在被认为是rank-balanced trees的形式，但是红色的黑树一直被about 20% in real world tests放慢。或者甚至比sequential data is inserted慢30-40％。
所以研究过红黑树而不是AVL树的人倾向于选择红黑树。 Wikipedia entry for them详细介绍了红黑树的主要用途。
程序员通常不喜欢动态分配内存。 avl树的问题是对于“n”元素，你需要至少log2（log2（n））...（height-> log2（n））位来存储树的高度！因此，当您处理大量数据时，您无法确定在每个节点上存储高度的分配位数。
例如，如果使用4个字节int（32位）来存储高度。最大高度可以是：2 ^ 32，因此你可以在树中存储的元素的最大数量是2 ^（2 ^ 32） - （似乎非常大，但在这个数据时代，我猜不会太大）。因此，如果你超过这个限制，你必须动态分配更多的空间来存储高度。
这是我大学教授提出的答案，这对我来说似乎是合理的！希望我有道理。
编辑：与红黑树相比，AVL树更加平衡，但它们可能会在插入和删除过程中引起更多旋转。因此，如果您的应用程序涉及许多频繁的插入和删除，那么应该首选红黑树。如果插入和删除频率较低且搜索操作更频繁，那么AVL树应优先于红黑树。 - 来源GEEKSFORGEEKS.ORG
这里的其他答案总结了RB和AVL树的利弊，但我发现这种差异特别有趣：
AVL树不支持不变的摊销更新成本[但红黑树做]
资料来源：Mehlhorn & Sanders (2008)（第7.4节）
因此，虽然RB和AVL树都保证O（log（N））最坏情况下的查找，插入和删除时间，但在插入或删除节点后恢复AVL / RB属性可以在O（1）amortized time中进行红色 - 黑树。
AVL树的重新平衡应满足以下属性。 （Wiki参考 - AVL Tree）
在AVL树中，任何节点的两个子子树的高度最多相差一个;如果它们在任何时候相差多于一个，则重新平衡以恢复此属性。
因此，这意味着AVL树的整体高度不会疯狂，即AVL树的查找效果会更好。并且由于要进行额外的操作（旋转）以使高度不高，树修改操作可能有点昂贵。