红黑树：TreeMap 的平衡之舞

红黑树是什么

红黑树是一种自平衡的二叉搜索树，TreeMap 的底层就是它。

为什么需要红黑树？因为普通的 BST 在极端情况下会退化成链表。

普通 BST（已排序数据插入）：
  1
   \
    2
     \
      3
       \
        4     ← 查找变成 O(n)

红黑树（自动平衡）：
      2（黑）
     / \
   1(红) 3(红)    ← 保持平衡，查找始终 O(log n)

---

红黑树的五大规则

1. 节点非红即黑
2. 根节点是黑色
3. 红节点的子节点必须是黑色（不能连续两个红节点）
4. 每条路径的黑色节点数相同
5. 叶子节点（NIL）都是黑色

这五条规则保证了：从根到最深叶子 ≤ 最浅叶子 2 倍。

---

插入操作：变色 + 旋转

插入新节点时，首先作为普通 BST 插入，然后通过「变色」和「旋转」恢复平衡。

插入场景 1：在红父节点下插入红子节点 → 需要调整
插入场景 2：在黑父节点下插入红子节点 → 无需调整

旋转

左旋：
      P                P
     /                /
    N      →         NR
     \              /
      NR           N

右旋（对称）：
      P                P
        \              /
         N    →      NL
        /              \
      NL                N

调整过程

// 简化逻辑
void insert(int val) {
    // 1. 作为普通 BST 插入（红节点）
    root = bstInsert(root, val); // 新节点默认为红色

    // 2. 检查是否违反红黑树规则
    //    如果父节点是红色，需要调整

    // 3. 调整：变色 + 旋转
    while (parentOf(node).isRed()) {
        if (parent == grandparent.left) {
            // 父是祖父的左子
            if (uncle.isRed()) {
                // 变色：父、叔变黑，祖父变红
                parent.setBlack();
                uncle.setBlack();
                grandparent.setRed();
                node = grandparent;
            } else {
                // 旋转 + 变色
                if (node == parent.right) {
                    rotateLeft(parent);
                }
                rotateRight(grandparent);
            }
        }
    }
    root.setBlack();
}

---

删除操作

删除比插入更复杂，需要考虑多种场景：

1. 删除红节点 → 直接删除，不影响黑色高度
2. 删除黑节点 → 需要调整平衡

---

红黑树 vs 普通 BST

特性	普通 BST	红黑树
查找	O(log n) 平均，O(n) 最坏	O(log n)
插入	O(log n) 平均，O(n) 最坏	O(log n)
删除	O(log n) 平均，O(n) 最坏	O(log n)
平衡	需手动维护	自动平衡

---

为什么选择红黑树

红黑树 vs 其他平衡树：

树类型	平衡方式	查找效率	插入效率
AVL 树	严格平衡（左右高度差 ≤ 1）	更快	更慢
红黑树	近似平衡（最长路径 ≤ 2 倍最短）	稍慢	更快

Java 选择红黑树：因为 TreeMap 的插入/删除更频繁（缓存、索引等场景），牺牲一点点查找效率换取更好的插入/删除性能。

---

总结

要点	说明
五大规则	红黑相间、根黑、叶黑、路径黑高相同
自平衡	插入/删除时变色 + 旋转
时间复杂度	查找/插入/删除都是 O(log n)
vs AVL	红黑树平衡要求更宽松，插入更快

---

相关链接

• TreeMap 底层实现
• TreeSet 底层实现