【C/C++】可视化解析红黑树插入与删除全流程

基于可视化方法分析红黑树的插入/删除流程

📥 一、红黑树插入操作

1️⃣ 插入流程总览

红黑树插入 = 二叉搜索树插入 + 插入后修复（保持5大性质）

插入过程步骤：

1. 插入新节点为红色；
2. 普通 BST 插入；
3. 检查是否破坏红黑树性质；
4. 修复：通过旋转和着色恢复红黑树性质。

2️⃣ 插入示意图与三种场景

✅ 示例结构（插入前）：

      10(B)
     /
   5(R)

➕ 插入 1（红色）

      10(B)
     /
   5(R)
  /
1(R)

违背性质：5 连续红色节点出现了

📚 修复场景分类（插入）

🧠 插入情况图解

🔴 情况 1：父红 + 叔红

      G(B)             G(R)
     /   \     =>     /   \
   P(R)  U(R)        P(B) U(B)
   /
 N(R)

• G: 祖父
• P: 父
• U: 叔
• N: 新节点

➡️ 颜色翻转，向上继续修复

🔁 情况 2：父红 + 叔黑 + 内拐

      G(B)             G(B)            G(B)
     /                 /                /
   P(R)              N(R)            N(R)
     \     =>       /     =>       /
     N(R)         P(R)          P(B)
                                /
                              NULL

➡️ 先旋转父节点，把内拐变外拐，再进入情况 3

🔁 情况 3：父红 + 叔黑 + 外拐

      G(B)              P(B)
     /     =>          /   \
   P(R)              N(R)  G(R)
  /
N(R)

➡️ 单旋 + 着色即可修复

📤 二、红黑树删除操作

红黑树删除更复杂，因为：

• 删除红节点：无需额外处理；
• 删除黑节点：可能破坏“黑高一致性”，需要复杂修复。

1️⃣ 删除基本流程

1. 按 BST 方式删除节点（含替换节点）；

2. 如果删除的是红色节点：无需修复；

3. 如果删除的是黑色节点：

   • 需要修复黑色平衡；
   • 引入“额外黑”，进行兄弟场景分类处理。

2️⃣ 删除修复场景分类

🧠 删除图解

🔴 情况 1：兄弟红（先旋转换色）

     P(B)                   S(B)
    /   \        =>        /   \
   N    S(R)             P(R)  SR
        /   \            /  \
      SL   SR          N   SL

➡️ S 旋转上来，把红兄弟转为黑兄弟（继续向下修复）

🟢 情况 2：兄弟黑 + 子黑

     P(B)              P(B)
    /   \    =>       /   \
   N    S(B)         N    S(R)
        /  \
      BL  BR

➡️ S 染红，P 继续下沉额外黑

✅ 插入 vs 删除 对比总结