问红黑树和AVL树是否具有相同的平衡条件？

EN

AVL树的平衡条件不同于红黑树的平衡条件。在某种意义上，AVL树比红黑树更平衡。

在AVL树中，对于每个节点v，v的右子树的高度和v的左子树的高度之间的差必须至多为1。与红黑树相比，这是一个非常严格的平衡属性。在红黑树中，从根到叶的任何简单路径的长度都不允许超过其他路径的两倍。这个属性是由five color conditions产生的，二分查找树必须满足才能被认为是有效的红黑树。

您的示例红黑树在AVL意义上确实是不平衡的，因为根的左子树的高度与其右子树的高度之间的差是2。然而，该树在红黑意义上是平衡的，因为它满足五个红黑颜色条件。

AVL平衡条件意味着the height of an AVL tree is bounded by roughly 1.44log(n)，而没有什么能阻止红黑树的高度变大:红黑树平衡条件只意味着高度上的a bound of 2log(n)。

AVL树往往比红黑树短，这一事实似乎表明它们必须表现得更好。事实并非如此: AVL树的搜索速度确实更快，因为它比红黑树更平衡。但AVL树如此平衡的原因是，保持它的平衡在计算上比保持红黑树平衡要困难。特别地，与相应的红黑树中的这些操作相比，AVL rotations使得在AVL树中的插入和删除更慢。