AVL 树和红黑树有什么区别？各自适合什么场景？
简化版
两者都是自平衡 BST，核心区别在平衡的严格程度：AVL 严格平衡（高度差 ≤ 1），树更矮、查找更快，但插入删除维护成本高（删除最坏 O(log n) 次旋转）；红黑树弱平衡（最长路径 ≤ 2 倍最短），树略高、查找略慢，但插入删除的旋转是常数级（插入 ≤2、删除 ≤3 次），更新更快。查多写少用 AVL，增删频繁的通用场景用红黑树——所以工业界库大多用红黑树。
详细版
| 维度 | AVL 树 | 红黑树 |
|---|---|---|
| 平衡标准 | 严格：左右高度差 ≤ 1 | 弱：最长路径 ≤ 2×最短路径 |
| 树高 | ≤ 1.44·log₂n（更矮） | ≤ 2·log₂n（略高） |
| 查找速度 | 更快 | 略慢 |
| 插入旋转 | 最多 1 次 | 最多 2 次 |
| 删除旋转 | 最坏 O(log n) 次 | 最多 3 次 |
| 每节点额外存 | 高度 / 平衡因子（整数） | 颜色（1 bit） |
| 维护成本 | 高（尤其删除） | 低 |
| 适用 | 查多写少（如字典、只读多） | 增删频繁的通用容器 |
完整版教学
一、根本差异：平衡的严格程度
这是理解两者一切区别的钥匙。
- AVL 追求「尽量平衡」：任意节点左右子树高度差不能超过 1。这让树非常接近完美平衡，高度最矮，查找路径最短。
- 红黑树追求「够用就好」：只保证最长路径不超过最短路径的 2 倍，允许一定程度的不平衡。树稍高，但换来了「大多数插入删除只需变色、少量旋转」的低维护成本。
一句话：AVL 用更高的维护成本换更快的查找；红黑树用略慢的查找换更低的维护成本。
二、查找性能
因为 AVL 更矮（1.44 log n vs 2 log n），查找 AVL 更快。但两者都是 O(log n)，实际差距在常数级，除非查找极其密集，否则感知不明显。
三、插入/删除性能（关键区别）
- 插入：AVL 最多 1 次旋转，红黑树最多 2 次，都很少，差别不大。
- 删除：这是分水岭。AVL 删除可能因为「旋转导致子树变矮」而连锁旋转，最坏 O(log n) 次；红黑树删除的旋转有常数上界（≤3）。所以在删除频繁时，红黑树的更新明显更省。
此外，AVL 要维护整数高度/平衡因子（需要 O(log n) 次更新沿途高度），红黑树只维护 1 bit 颜色，变色是 O(1) 的局部操作。
四、空间与实现
- 空间：红黑树每节点只多存 1 bit 颜色，AVL 要存高度（或平衡因子），红黑树更省。
- 实现复杂度：红黑树的插入删除分类更多、更繁琐（尤其删除的双黑情况），代码更难写；AVL 逻辑相对直白。但红黑树写好一次就一劳永逸地用在库里。
五、如何选择
- 查找远多于插入删除（如构建一次、大量查询的字典/索引）→ AVL，享受更快的查找。
- 插入删除频繁的通用场景 → 红黑树，更新成本低、综合性能好。
- 工业界的默认选择是红黑树：Java 的
TreeMap/TreeSet、HashMap（链表转红黑树）、C++ STL 的map/set、Linux 内核的进程调度和内存管理，用的都是红黑树，因为通用容器的读写比例难以预知，红黑树的「均衡」更稳妥。 - 数据库索引则用另一类平衡树 B/B+ 树（面向磁盘、多路），那是另一个话题。
六、常见误区与追问
| 考点 | 正确口径 |
|---|---|
| AVL | 更严格平衡，查找更稳定 |
| 红黑树 | 近似平衡，更新旋转较少 |
| 选择 | 读多偏 AVL，写多和工程库常偏红黑树 |
AVL: |leftHeight - rightHeight| <= 1
RedBlack: longestPath <= 2 * shortestPathAVL 和红黑树不是谁绝对更好，而是在查询稳定性和更新成本之间取舍。
- 误区：红黑树不是平衡树。 红黑树是近似平衡树，通过颜色性质保证高度 O(log n)。
- 误区：AVL 一定比红黑树更快。 AVL 查找通常更稳定，但插入删除可能旋转和高度维护更多。
- 误区：两者都适合哈希等值查找替代品。 它们的优势是有序性、范围遍历、前驱后继，而不是纯等值平均 O(1)。
- 追问：Java TreeMap 为什么用红黑树？ TreeMap 需要有序 Map，同时更新操作常见，红黑树在工程上折中好。
- 追问：AVL 的高度为什么更低？ 它用严格高度差约束每个节点，红黑树只限制黑高和红节点连续性。
- 追问：如何一句区分应用场景？ 查询极多且更新少可考虑 AVL；通用有序容器和写多场景常用红黑树。
七、加强记忆
AVL vs 红黑树，根本差异是平衡严格度：AVL 严格（高度差 ≤1，更矮、查找快，但删除最坏 O(log n) 次旋转、维护贵）；红黑树弱平衡（最长 ≤2 倍最短，略高、查找略慢，但插入 ≤2、删除 ≤3 次旋转、只存 1 bit 颜色、维护省）。查多写少用 AVL，增删频繁的通用容器用红黑树——所以 TreeMap、STL map、Linux 内核都选红黑树。