1. 概述
在本教程中，我们将讨论两种自平衡二叉树结构：AVL树和红黑树（Red-Black Tree）。我们将介绍它们的特性、操作，并通过示例进行说明。
最后，我们会重点分析它们之间的核心区别，帮助你理解在不同场景下如何选择合适的数据结构。
2. AVL树简介
要理解AVL树，我们先回顾一下二叉树和二叉搜索树（BST）的基本概念。
在普通的二叉搜索树中，如果树退化为链表（如左偏或右偏树），其操作的时间复杂度将从 O(log n) 退化为 O(n)，影响效率。
AVL树是一种自平衡的二叉搜索树。它通过维护每个节点的“平衡因子”来保证树的整体高度平衡。
✅ 平衡因子 = 左子树高度 - 右子树高度
平衡因子的取值必须为 -1、0 或 1
当插入或删除节点导致某个节点的平衡因子超出这个范围时，AVL树会通过旋转操作（左旋、右旋、左右旋、右左旋）重新平衡树结构。
下图展示了一个左偏树的示例：
AVL树的核心优势在于，其操作的时间复杂度始终为 **O(log n)**，即使在最坏情况下也是如此。
3. AVL树的特性
- 高度平衡树：AVL树的高度保持在 O(log n)
- 最大节点数：对于高度为 H 的AVL树，最多有 $2^{H+1} - 1$ 个节点
- 最小节点数：通过递推公式 $N(H) = N(H - 1) + N(H - 2) + 1$ 计算，其中 $N(0) = 1, N(1) = 2$
- 平衡因子：每个节点必须满足平衡因子为 -1、0 或 1
- 旋转操作：
- 左旋（Left Rotation）
- 右旋（Right Rotation）
- 左右旋（Left-Right Rotation）
- 右左旋（Right-Left Rotation）
AVL树每次插入或删除节点后都需要重新计算平衡因子并进行旋转操作，以确保树的平衡性。
4. AVL树的操作
4.1 查找
AVL树的查找操作与BST相同：
- 从根节点开始，比较目标值与当前节点的大小
- 根据比较结果向左或右子树递归查找
- 时间复杂度：O(log n)
4.2 插入
插入操作步骤如下：
- 若树为空，插入为根节点
- 否则按BST规则插入新节点
- 插入后自底向上更新平衡因子
- 若某节点平衡因子超出 [-1, 1] 范围，则进行旋转操作
✅ 插入时间复杂度也为 O(log n)
示例：插入节点序列 [14, 17, 11, 78, 53, 4, 13, 12]
插入顺序如下图所示：
插入12后，树不平衡，需进行左旋 + 右旋操作。
4.3 删除
删除操作流程如下：
- 按照BST规则找到并删除节点
- 删除后检查平衡因子
- 若不平衡，进行旋转操作
✅ 删除时间复杂度也为 O(log n)
示例：删除节点 [8, 13, 12]
删除12后树不平衡，需进行右旋操作：
5. 红黑树简介
红黑树也是一种自平衡二叉搜索树，但与AVL树不同，它是一种近似平衡树。
红黑树通过以下规则保证树的平衡：
- 每个节点是红色或黑色
- 根节点是黑色
- 叶子节点（NIL节点）是黑色
- 如果一个节点是红色，其子节点必须是黑色
- 从任一节点到其每个叶子的所有路径都包含相同数量的黑色节点
红黑树相比AVL树更易于实现，且插入和删除操作所需的旋转次数较少。
6. 红黑树的特性
- 每个节点有颜色属性（红或黑）
- 根节点和叶子节点均为黑色
- 红色节点的子节点必须为黑色
- 从任意节点到其所有叶子节点的路径中，黑色节点的数量相同
- 若红黑树有 n 个节点，其最大高度为 $2 \log(n+1)$
红黑树的节点结构通常包含以下字段：
class Node {
int key;
Node left, right, parent;
Color color; // RED or BLACK
}
7. 红黑树的操作
7.1 查找
与BST相同，从根节点开始比较，时间复杂度为 O(log n)
7.2 插入
插入流程如下：
- 若树为空，插入为根节点并设为黑色
- 否则按BST规则插入新节点，初始颜色为红色
- 检查父节点颜色，若为红色，检查叔叔节点颜色
- 根据颜色和结构进行旋转和重新染色
⚠️ 插入时最多需要两次旋转操作即可恢复平衡
7.3 删除
删除流程如下：
- 按BST规则删除节点
- 若删除的是红色节点，不影响平衡
- 若删除的是黑色节点，可能破坏红黑树性质，需进行旋转和染色操作
✅ 删除时最多也需要两次旋转操作
8. AVL树与红黑树的对比
| 特性 | AVL树 | 红黑树 |
|---|---|---|
| 平衡程度 | 严格高度平衡 | 近似高度平衡 |
| 实现复杂度 | 较高 | 较低 |
| 插入/删除性能 | 相对较慢（旋转多） | 相对较快（最多两次旋转） |
| 查找性能 | 更快（高度更小） | 略慢 |
| 节点颜色 | 无 | 有（红/黑） |
| 平衡因子 | 有 | 无 |
| 应用场景 | 数据库索引 | 语言标准库（如Java TreeMap） |
9. 总结
本教程我们详细介绍了AVL树和红黑树的结构、操作及其核心区别：
- AVL树强调严格平衡，适合查找频繁、插入删除较少的场景
- 红黑树强调近似平衡，适合插入删除频繁的场景
- AVL树插入/删除时旋转次数较多，性能略差
- 红黑树最多两次旋转即可恢复平衡，性能更优
✅ 根据具体场景选择合适的数据结构是关键。例如，Java的TreeMap使用红黑树实现，而数据库索引多使用AVL树。
理解它们的差异，有助于你在实际开发中做出更高效、更合理的技术选型。