AVL树 vs 红黑树

概述

AVL 树（AVL Tree） 与 红黑树（Red-Black Tree） 是两种最经典的自平衡二叉搜索树。AVL 树由 Adelson-Velsky 和 Landis 于 1962 年发明，是最早的自平衡 BST；红黑树由 Bayer 于 1972 年发明、Guibas 和 Sedgewick 于 1978 年命名。两者都保证 $O(\lg n)$ 的操作复杂度，但平衡策略和性能特征有显著差异。

核心差异

特性	AVL 树	红黑树
平衡策略	严格平衡：左右子树高度差不超过 1	宽松平衡：最长路径不超过最短路径的 2 倍
平衡因子	每个节点维护 $h(left)-h(right)\in \{-1,0,1\}$	每个节点维护颜色位（红/黑）
树高上界	$\approx 1.44\lg (n+2)-0.328$（更矮）	$\le 2\lg (n+1)$（较高）
查找性能	更快（树更矮，比较次数更少）	稍慢（树较高）
插入旋转次数	最多 2 次（单旋或双旋）	最多 2 次
删除旋转次数	最多 $O(\lg n)$ 次	最多 3 次
插入总时间	$O(\lg n)$（旋转 $O(1)$，但需回溯更新高度）	$O(\lg n)$
删除总时间	$O(\lg n)$（旋转可能 $O(\lg n)$ 次）	$O(\lg n)$（旋转最多 3 次）
实现复杂度	中等（需维护平衡因子，4 种旋转情况）	较高（插入 3 种情况，删除 4 种情况）
额外存储	每个节点 1 个整数（平衡因子）或 1 个高度值	每个节点 1 位（颜色）

树高对比

对于 $n$ 个节点的树：

• AVL 树：高度 $h\le 1.44\lg (n+2)-0.328\approx 1.44\lg n$

  • 这是由于 AVL 树的严格平衡条件，使得树接近完美平衡。
  • Fibonacci 树是最不平衡的 AVL 树，高度达到上界。

• 红黑树：高度 $h\le 2\lg (n+1)$

  • 红黑树允许适度不平衡，最坏情况下最长路径是最短路径的 2 倍。
  • 实际中红黑树的平均高度约为 $1.0\sim 1.5\lg n$。

直观理解： AVL 树比红黑树更矮更紧凑，因此查找时比较次数更少。但红黑树在修改操作（尤其是删除）时需要更少的旋转。

旋转对比

操作	AVL 树	红黑树
插入	最多 2 次旋转（LL/RR 单旋或 LR/RL 双旋）	最多 2 次旋转
删除	最多 $O(\lg n)$ 次旋转（沿路径逐层修复）	最多 3 次旋转
旋转类型	4 种：LL、RR、LR、RL	2 种：左旋、右旋（配合变色）

关键差异： AVL 树在删除时可能需要 $O(\lg n)$ 次旋转，因为删除一个节点后，不平衡可能沿路径向上传播，每一层都可能需要旋转。而红黑树的删除修复最多只需 3 次旋转，因为修复过程通过变色将问题快速上移，最终在常数次旋转内解决。

适用场景

选择 AVL 树的场景

1. 查找密集型应用：查找操作远多于插入/删除操作（如字典、静态数据库索引）。
2. 需要最快的查找性能：AVL 树更矮，查找路径更短，比较次数更少。
3. 数据基本稳定：插入和删除操作较少，删除时的 $O(\lg n)$ 旋转不是问题。

选择红黑树的场景

1. 插入/删除密集型应用：频繁的修改操作（如实时数据流、事件调度）。
2. 需要稳定的修改性能：红黑树的插入和删除都有常数次旋转的保证。
3. 通用有序容器：作为标准库的有序 Map/Set 实现。

工程实践：为什么主流标准库选择红黑树

C++ STL

std::map 和 std::set 使用红黑树作为底层实现。原因：

• 删除操作最多 3 次旋转，性能稳定可预测。
• 在实际应用中，插入和删除操作与查找操作同样频繁。
• 红黑树的宽松平衡在实际中已经足够高效。

Java

TreeMap 和 TreeSet 使用红黑树。原因与 C++ 类似。

Java 8 的 HashMap

Java 8 中，当 HashMap 的单个桶中元素超过 8 个时，会将链表转换为红黑树，将最坏查找时间从 $O(n)$ 降为 $O(\lg n)$。这里选择红黑树而非 AVL 树，是因为：

• 红黑树在删除时旋转次数更少（HashMap 需要支持删除操作）。
• 红黑树的实现相对成熟稳定。

为什么不选 AVL 树

AVL 树在查找性能上优于红黑树，但在工程实践中，标准库选择红黑树的主要原因是：

1. 修改操作更高效：尤其是删除操作，红黑树的 $O(1)$ 旋转 vs AVL 树的 $O(\lg n)$ 旋转。
2. 实际差距不大：红黑树的高度上界为 $2\lg n$，实际平均高度约为 $1.0\sim 1.5\lg n$，与 AVL 树的 $1.44\lg n$ 差距不大。
3. 常数因子：红黑树每个节点只需 1 位额外存储，AVL 树需要存储平衡因子或高度（通常为整数）。
4. 历史惯性：红黑树在早期标准库中被采用后，形成了生态惯性。

参见

• 红黑树 — 红黑树的完整定义与性质
• 旋转 — 红黑树中的旋转操作
• RB-INSERT-FIXUP — 红黑树插入修复
• RB-DELETE-FIXUP — 红黑树删除修复
• 二叉搜索树 — BST 的基本定义
• 散列表-vs-二叉搜索树 — 散列表与 BST 的对比