平衡树（AVL / 红黑树）

⚖️ BST 的致命伤——以及怎么治

上一节我们学 BST 时遇到了一个问题：如果按顺序插入数据，BST 会退化成链表——查找从 O(log n) 变成 O(n)。

插入 1, 2, 3, 4, 5 到 BST 的结果：
1
 \
  2
   \
    3
     \
      4
       \
        5    ← 这不是一棵树——这是链表！

为什么 BST 会出现这个问题？ 因为 BST 只保证了”左 < 父 < 右”，但没有”保持树的形状”的机制——它不知道什么是”平衡”。

平衡树（Balanced Tree） 就是解决了这个问题：在插入和删除后，通过旋转（Rotation） 操作让树始终保持平衡，从而保证所有操作都是 O(log n)。

🏗️ 类比：叠叠乐积木

未平衡的 BST = 你把积木一个个竖直往上叠——从侧面看就是一根直线，一阵风就倒了（退化了）。

平衡树 = 你每放一个积木，就调整一下位置让重心居中——这样堆出来的塔既高又稳。

---

🌲 AVL 树——严格平衡

什么是 AVL 树？

AVL 树（Adelson-Velsky and Landis）是最早被发明的平衡树。它的规则很简单：

每个节点的左右子树高度差不超过 1。

高度差的定义：
平衡因子（Balance Factor）= 左子树高度 - 右子树高度

AVL 树要求：-1 ≤ 平衡因子 ≤ 1

✅ 平衡：
      A (h=3)
     / \
  (h=2) (h=2)

✅ 平衡：
      A (h=3)
     / \
  (h=3) (h=2)   ← 差值为 1，允许

❌ 不平衡：
      A (h=3)
     / \
  (h=4) (h=1)   ← 差值为 3，需要旋转

AVL 的四种旋转

当插入或删除导致平衡因子超出范围时，AVL 通过旋转恢复平衡。四种情况：

① LL 不平衡（左左）→ 右旋

     失衡节点 Z
     /
    Y (左子)
   / 
  X (新插入在左子的左子树)

右旋：把 Y 提到 Z 的位置，Z 变成 Y 的右子。

    Y                    Y
   / \        →         / \
  X   Z               X   Z

🧩 类比：一个人拉另一个人往上托

② RR 不平衡（右右）→ 左旋

和 LL 对称。

③ LR 不平衡（左右）→ 先左旋再右旋

    Z
   / 
  Y
   \
    X (新插入在左子的右子树)

先对 Y 左旋变成 LL 情况，再右旋。

④ RL 不平衡（右左）→ 先右旋再左旋

和 LR 对称。

💡 一句话记住四种旋转：看新节点插入的位置相对于”最下面的失衡节点”的关系——在左子的左子 → 右旋；在右子的右子 → 左旋；在左子的右子 → 左右旋；在右子的左子 → 右左旋。

AVL 树的特性

特性	值
查找	O(log n) —— 严格保证
插入	O(log n) —— 需要旋转恢复平衡
删除	O(log n) —— 也可能需要旋转
平衡程度	严格（高度差 ≤ 1）

---

🌳 红黑树——没那么严格，但够用

红黑树（Red-Black Tree）是另一种平衡树，规则更”宽松”——不要求高度差 ≤ 1，而是保证”最长路径不超过最短路径的两倍”。

红黑树的五条规则

每个节点是红色或黑色。

1. 根节点是黑色
2. 叶子节点（NIL）是黑色
3. 红色节点的子节点必须是黑色（红色节点不能相邻）
4. 从任意节点到它的叶子节点，经过的黑色节点数量相同

红黑树示例（R=红, B=黑）：
        10(B)
       /   \
      5(R)  15(R)
     / \    /  \
    2(B)7(B)12(B)20(B)

验证规则：

• 根 10 是黑色 ✅
• 红色节点 5 的子节点 2 和 7 都是黑色 ✅
• 红色节点 15 的子节点 12 和 20 都是黑色 ✅
• 从根到任意叶子：经过的黑色节点数相同 ✅

红黑树的调整

插入新节点时（默认红色），可能违反规则。修复方式有三种：

1. 变色：把红色变黑色，黑色变红色
2. 左旋：和 AVL 的左旋一样
3. 右旋：和 AVL 的右旋一样

一个常见的插入修复场景：

# 新插入的节点是红色
# 如果它的叔叔（父节点的兄弟）也是红色 → 变色
# 如果叔叔是黑色 → 旋转 + 变色

红黑树 vs AVL 树

对比	AVL	红黑树
平衡程度	严格（高度差 ≤ 1）	宽松（最长 ≤ 2×最短）
查找速度	更快（更平衡）	稍慢
插入/删除效率	慢（旋转更多）	快（旋转更少）
实现复杂度	较简单	较复杂

💡 实际选择：

• 查询多、修改少的场景 → AVL 更优（查询快，同时修改代价能接受）
• 通用场景 → 红黑树更优（修改操作多时，旋转更少）
• C++ STL map/set、Java TreeMap、Linux 内核的完全公平调度器 都用红黑树

---

🏢 实际应用

# C++ 中，map 用红黑树实现
std::map<int, string> students;
students[1] = "张三";  // 插入 O(log n)
students[2] = "李四";
auto it = students.find(1);  // 查找 O(log n)
// 遍历时按键排序输出

# Java 中，TreeMap 用红黑树
TreeMap<Integer, String> map = new TreeMap<>();
map.put(2, "B");
map.put(1, "A");  
map.put(3, "C");
// map.keySet() → [1, 2, 3] 自动排序

Python 中没有内建的红黑树——因为 Python 的 dict 用哈希表，list 用动态数组。但在需要有序映射的场景下，可以：

• 用 bisect 模块在有序列表中查找（但插入 O(n)）
• 用第三方库 sortedcontainers（底层实现是平衡树）

---

📊 树结构复杂度全览

树类型	查找	插入	删除	特点
BST（未平衡）	O(n) 最坏	O(n) 最坏	O(n) 最坏	简单，但有退化风险
AVL	O(log n)	O(log n)	O(log n)	严格平衡，查找最快
红黑树	O(log n)	O(log n)	O(log n)	平衡宽松些，插入删除快
B+ 树	O(log n)	O(log n)	O(log n)	多路，适合磁盘存储

---

📝 小结

概念	一句话
AVL 树	每个节点左右子树高度差 ≤ 1——严格平衡
红黑树	五条颜色规则保证大致平衡——更少的旋转
旋转	左旋、右旋——恢复平衡的核心操作
LL/RR/LR/RL	AVL 四种不平衡情况，对应不同旋转
应用选择	查多选 AVL，写多选红黑树

🎯 思考题：在红黑树中，如果一个红色节点有两个黑色子节点，这两个黑色子节点的子节点必须是什么颜色？为什么？

为什么先学这个？ 树是组织层次数据的基础。接下来从树进入更一般的结构——图的表示。