红黑树

朝花夕拾
  • Wiki
  • 中文Wiki
  • 推荐文档

红黑树的4条性质

  1. 任何节点非黑即红
  2. 所有叶子节点(NULL节点)都是黑色节点
  3. 一个红色节点没有红色子节点
  4. 从任何节点到其后代所有叶子节点(NULL节点)的每条路径都有相同数量的黑色节点

插入

所有插入操作都是在叶子结点进行的,插入节点默认为红色。

插入的6种情况及处理方法

  • 1️⃣ 空树 👉 创建树,插入节点作为根节点,颜色改为黑色
  • 2️⃣ 节点已经存在 👉 无需做处理
  • 3️⃣ 父节点是黑色 👉 由于插入节点是红色,直接插入不会影响平衡
  • ⤵ 父节点红
    • 4️⃣ 叔叔节点为红色 👉 父亲和叔叔设置为黑色,祖父设置为红色,并把祖父当成插入节点向上递归
    • ⤵ 叔叔节点不存在或为黑色
      • 5️⃣ 插入节点与父节点顺边 👉 父亲、祖父颜色反转,对祖父做旋转
      • 6️⃣ 插入节点与父节点反边 👉 旋转成顺边处理,得到情况5 ⤴

插入情况图示

插入情况图示

删除

  1. 当删除的节点有两个子节点时,用右树最左节点或左树最右节点进行替换后,可以把情况转换成删除替换节点,这类替换节点只能是有0个或有1个子节点;
  2. 有一个子节点时,改节点必然是黑色,子节点是红色。(如果改节点是红色,则违反性质4;如果唯一子节点也是黑色,也会违反性质4)
  3. 没有子节点时,这种情况最复杂,需要看兄弟节点那边的情况;

删除的8种情况及处理方法

  • 1️⃣ 空树 👉 无需做处理
  • 2️⃣ 节点不存在 👉 无需做处理
  • 3️⃣ 节点是红色 👉 直接删除
  • ⤵ 节点是黑色
    • 4️⃣ 有子节点 👉 把子节点改为黑色,并用子节点替换
    • ⤵ 没有子节点
      • 5️⃣ 兄弟节点是红色 👉 父节点变红,兄弟节点变黑,对父节点旋转,得到情况8 ⤵
      • ⤵ 兄弟节点是黑色
        • 6️⃣ 兄弟节点顺边子节点是红色 👉 将父节点和兄弟的顺边子节点设置为黑,兄弟节点设置为父节点颜色,并向替换节点方向旋转兄弟节点
        • ⤵ 兄弟节点顺边子节点是黑色
          • 7️⃣ 兄弟节点对边子节点是红色 👉 将兄弟对边子节点设为黑,兄弟节点设为红,对兄弟节点顺边旋转,得到情况6 ⤴
          • 8️⃣ 兄弟节点对边子节点是黑色 👉 将兄弟节点设置为红,把父亲节点作为新的处理节点递归 ⤴

删除情况图示

删除情况图示