AVL树与红黑树对比

一、AVL树回顾

1.1 严格平衡

AVL树要求任何节点的左右子树高度差不超过1。

1.2 树高上限

[ h \leq 1.44 \log_2(n+2) - 0.328 ]

最多比完全二叉树高约44%。

二、红黑树(Red-Black Tree)

2.1 定义与性质

1. 每个节点是红色或黑色
2. 根节点是黑色
3. 所有叶子(NIL)是黑色
4. 红色节点的子节点必须是黑色（无连续红节点）
5. 从任一节点到其叶子的所有路径包含相同数目的黑色节点

2.2 树高上限

[ h \leq 2 \log_2(n+1) ]

最长路径不超过最短路径的2倍。

三、核心对比

3.1 平衡严格性

特性	AVL树	红黑树
平衡条件	高度差 ≤ 1	黑高相同，最长 ≤ 2×最短
树高	≤ 1.44 log n	≤ 2 log n
查询效率	更快（树更矮）	稍慢

3.2 旋转开销

操作	AVL树	红黑树
查找	( O(\log n) )	( O(\log n) )
插入	( O(\log n) )，最多2次旋转	( O(\log n) )，最多2次旋转
删除	( O(\log n) )，最多 ( O(\log n) ) 次旋转	( O(\log n) )，最多3次旋转

关键差异：

• AVL删除可能需要回溯旋转到根
• 红黑树旋转次数更稳定

3.3 实现复杂度

• AVL：需要维护高度或平衡因子
• 红黑树：需要维护颜色，逻辑更复杂

四、红黑树的平衡操作

4.1 插入平衡

新节点插入为红色（不违反黑高条件），然后修复可能的红红冲突。

情况分类：

1. 叔叔是红色 → 变色
2. 叔叔是黑色，且新节点与父节点同侧 → 旋转
3. 叔叔是黑色，且新节点与父节点异侧 → 双旋

4.2 颜色翻转

  黑(B)              红(R)
 /   \      →       /   \
红(R) 红(R)        黑(B) 黑(B)

4.3 左旋右旋

与AVL类似，但旋转后需要调整颜色。

五、Java中的应用

5.1 TreeMap / TreeSet

基于红黑树实现。

TreeMap<Integer, String> map = new TreeMap<>();
// 插入、删除、查找都是 O(log n)

5.2 为什么选择红黑树

• Java标准库选择红黑树：插入删除更稳定
• Linux内核的CFS调度器也使用红黑树

六、选择指南

场景	推荐
查询远多于增删	AVL树
增删查频率相近	红黑树
频繁删除	红黑树
对常数敏感	AVL树（树更矮）
实现复杂度敏感	红黑树（插入删除更稳定）

七、总结

AVL树和红黑树都是自平衡BST，核心差异在于平衡的严格程度：

• AVL更严格 → 查询快，但旋转多
• 红黑树更宽松 → 旋转少，查询稍慢

实际中，由于旋转是常数时间，而查询更多见，两者性能差异不大。红黑树因插入删除更稳定，被更广泛采用。