红黑树

---

1. 定义

红黑树是一种 自平衡二叉搜索树（BST），通过节点颜色（红色或黑色）和一些规则保证树的高度大致平衡，从而保证查找、插入、删除操作的效率。

1. 节点是红色或黑色
2. 根节点是黑色
3. 所有叶子节点（NIL）是黑色
4. 红色节点的子节点必须是黑色（即红色节点不能连续出现 → 防止退化）
5. 从任意节点到其每个叶子的简单路径上，黑色节点数量相同（黑高相同）

2. 特点

• 近似平衡：通过颜色和规则保证树高度 = O(log n)
• 二叉搜索树性质：左 < 根 < 右
• 操作效率稳定：查找、插入、删除平均和最坏情况均为 O(log n)
• 比 AVL 树更“宽松”：允许局部不严格平衡，因此旋转次数比 AVL 树少

3. 旋转与调整

红黑树通过 颜色翻转和旋转 来恢复平衡。
主要操作：

1. 左旋（Left Rotate）
2. 右旋（Right Rotate）
3. 颜色翻转（Color Flip）

插入调整流程

1. 新节点插入为 红色
2. 检查父节点颜色：
   • 父节点黑 → 无需调整
   • 父节点红 → 违反性质，需要旋转或颜色翻转

删除调整流程

• 删除可能导致黑高不一致
• 需要通过旋转 + 颜色调整修复

相比 AVL 树：红黑树不严格保证高度差 ≤ 1，而是保证路径上的黑色节点数一致 → 高度 ≤ 2 * log(n+1)
所以它查找效率仍为 O(log n)，但插入删除旋转次数比 AVL 树少

---

4. 对比 AVL 树

特性	AVL 树	红黑树
平衡方式	严格平衡，高度差 ≤ 1	宽松平衡，依靠黑高规则
旋转次数	插入/删除可能频繁旋转	插入/删除旋转次数较少
查找效率	高（O(log n)）	高（O(log n)）
插入删除效率	相对较慢（频繁旋转）	相对较快（旋转次数少）
应用场景	查找远多于写入	写入较多、性能均衡要求高

---

5. 小结

• 红黑树 = 自平衡二叉搜索树 + 颜色规则
• 通过 旋转 + 颜色调整 保持树高度近似平衡
• 插入删除比 AVL 树更高效，查找效率略低但仍为 O(log n)
• 常用于 Java 的 TreeMap、TreeSet、C++ STL 的 map/set 等