红黑树 vs AVL树
核心区别
| 维度 |
红黑树 |
AVL树 |
| 平衡严格度 |
较宽松（允许黑高差，无连续红节点） |
严格（左右子树高度差 ≤1） |
| 树高 |
最多 2log₂(N+1) ≈ O(logN) |
更平衡，树高 ≈ 1.44log₂(N+2)-1.328 ≈ O(logN) |
| 插入旋转次数 |
最多 2 次 |
可能需要 O(logN) 次 |
| 删除旋转次数 |
最多 3 次 |
可能需要 O(logN) 次 |
| 查找速度 |
稍慢（树高略高） |
更快（树高更平衡） |
| 插入/删除效率 |
更高（旋转次数少） |
更低（旋转次数多） |
| 适用场景 |
插入删除频繁的场景（如Java TreeMap） |
查找频繁、插入删除少的场景 |
详细对比
平衡机制
- 红黑树：通过红黑着色 + 5条性质保证树高，不严格要求高度差
- AVL树：通过平衡因子（左子树高 - 右子树高）严格限制高度差 ≤1
旋转操作
- 红黑树：插入最多 2 次旋转，删除最多 3 次旋转
- AVL树：插入/删除可能需要多次旋转（沿回溯路径向上调整）
空间开销
- 红黑树：每个节点需额外 1 bit 存储颜色（红/黑）
- AVL树：每个节点需额外存储平衡因子或树高（通常 1 byte）
应用场景
| 场景 |
推荐选择 |
Java TreeMap/TreeSet |
红黑树（插入删除频繁） |
| 数据库索引（读多写少） |
AVL树（查找更快） |
| 实时系统（要求稳定查找时间） |
AVL树（树高更平衡） |
| 通用场景（插入删除+查找） |
红黑树（综合性能更好） |
相关概念