红黑树的插入和删除

首先介绍红黑树的性质：

1. 节点不是红色就是黑色。
2. 根节点为黑色。
3. 叶子结点 (最底层不存放数据的节点) 都为黑且为 NULL 。
4. 红色节点的父节点和子节点都为黑色，即不会存在两个连续的红色节点。
5. 从任一节点到叶子结点的所有路径都包含相同数量的黑色节点。

# 红黑树 插入

配合红黑树插入 (av597092394) 食用。

插入节点的颜色根据以下原则：如果插入的为根节点，则为黑色，其余情况一开始为红色 (插入红色如出现连续的两个红色节点，只需要旋转和变色进行调整)。

红黑树插入操作分为 12 种情况，以下分开讨论。

1. 插入节点的父节点为黑色的 (4 种)
   • 直接插入，不作调整。
2. 插入节点的父节点为红色的 (8 种)
   • 插入节点的叔父节点是不是红色 (4 种)
     • LL / RR: 变色 + 父节点右旋 / 父节点左旋
     • LR / RL: 变色 + 父节点左旋 & 祖节点右旋 / 父节点右旋 & 祖节点左旋
   • 插入节点的叔父节点是红色 (4 种)
     • 插入节点的父节点和叔父节点变为黑色，祖父节点变红色，并以此递归。

# 红黑树 删除

配合红黑树删除 (av556364744) 食用。

1. 红色节点直接删除
2. 黑色节点
   1. 有 2 个红色子节点
      • 会转化为对其子节点的删除，不作考虑
   2. 有 1 个红色节点
      • 用唯一的红色子节点来替代被删除的节点并变为黑色
   3. 黑色叶子结点
      1. 删除节点为根节点
         • 直接删除
      2. 删除节点的兄弟节点为黑色
         • 兄弟节点有红色子节点 (借用兄弟子节点修复)
           1. 为左节点
              • 删除节点后其父节点单旋，中心节点染为父节点颜色，子节点染黑
           2. 为右节点
              • 删除节点后双旋，中心节点染为父节点颜色，子节点染黑
           3. 左右节点都有
              • 当做为左节点处理 (也可当成为右节点处理)
         • 兄弟节点没有红色子节点 (父节点向下合并)
           1. 父节点是红色节点
              • 父节点染黑，兄弟节点染红
           2. 父节点是黑色
              • 兄弟节点染红，父节点当做被删除的情况递归
      3. 删除节点的兄弟节点为红色
         • 删除节点的其父节点单旋，兄弟节点染黑，父节点染红
         • 转为兄弟节点为黑色的情况处理