红黑树(上):红黑树的性质与增删操作分析


1 红黑树简介

为了降低 二叉排序树 的高度,提高查询效率,数学家们提出了一种高度平衡的二叉排序树,即 平衡二叉树 (又称 AVL 树)。AVL 树引入了平衡因子的概念,要求所有节点的平衡因子的绝对值不超过 1,这样便保证了查询效率稳定在 $O(\log n)$ 的水平。然而,为了维持这种平衡,AVL 树需要频繁的进行再平衡操作,这会对插入和删除操作的性能造成较大的影响。为了平衡查询操作和增删操作的效能,数学家们又提出了一种新的自平衡二叉查找树——红黑树。

红黑树并没有通过平衡因子来强限定二叉树的平衡性,而是引入了红黑节点的五条性质来维持一种近似平衡的树结构,进而提升了增删操作的性能,同时对查询操作也没有特别大的影响。

学习过程中我们可以通过使用该网站上的工具来加深理解:Red/Black Tree Visualization

2 红黑树的性质

红黑树在保持二叉排序树性质的基础上,增加了以下五条性质:

  1. 每个节点要么是红色,要么是黑色。

  2. 根节点必须是黑色的。

  3. 叶节点(NULL 节点)都是黑色的。

    这里的叶子节点并非度为 0 的节点,而是指度为 0 的节点中指向左右子节点的空指针

  4. 如果一个节点是红色的,则它的子节点必须是黑色的。

    这个性质可以衍生出以下两个含义:

    • 红节点的父节点也必然是黑节点
    • 根节点到叶子节点的所有路径上,不能有连续的两个红节点
  5. 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

红黑树插入或删除节点后,有一定概率需要调整节点,以满足红黑树的五条性质。

下图展示了按照自然顺序插入 10 个元素后所形成的标准红黑树。可以看出,在这种极端情况下,红黑树的平衡性不如 AVL 树好,但远优于普通的二叉排序树:

红黑树示例

(下文为了方便,就不再展示 NULL 叶子节点了)

3 红黑树插入操作

默认情况下,向红黑树插入新节点时,新节点会被标记为红色。这是因为,如果新节点是黑色的,它将在当前路径上增加一个黑色节点,从而破坏红黑树的黑平衡(性质 5)。为了重新平衡树,需要进行额外的调整操作,这会增加操作的复杂度。相比之下,如果新插入节点是红色的,则不会破坏红黑树的黑平衡,只需要通过变色和旋转操作调整即可。总的来说,直接插入红节点时,红黑树仍然满足性质 1、2、3、5,只有性质 4 可能不满足。

接下来我们详细介绍红黑树插入节点的各种场景。

  • 场景一:插入根节点

    如果发现红黑树是一颗空树,则直接作为黑色根节点插入:

    插入红黑树根节点
  • 场景二:插入节点的父节点是黑节点

    如果插入节点的父节点是黑节点,则不需要进行任何操作:

    插入节点的父节点是黑节点
  • 场景三:插入节点的父节点是红节点,且有红色叔节点

    如果新插入的红节点的父节点也是红节点,且存在红色叔节点,只需将新插入节点的父节点和叔节点染成黑色,将祖父节点染成红色即可。如果祖父节点是红黑树的根节点,还需要再将祖父节点染黑,以满足性质 2:

    LL 型场景,且存在红色叔节点
    LL 型场景,且存在红色叔节点
    RR 型场景,且存在红色叔节点
    RR 型场景,且存在红色叔节点
    LR 型场景,且存在红色叔节点
    LR 型场景,且存在红色叔节点
    RL 型场景,且存在红色叔节点
    RL 型场景,且存在红色叔节点
  • 场景四:LL、RR 型场景,且无红色叔节点

    如果新插入的红节点是红色父节点的左子节点,且红色父节点是祖父节点的左子节点,同时不存在红色叔节点,则需要对新插入节点的父节点和祖父节点进行右旋处理。旋转完成后,需要将新插入节点的原父节点染成黑色,原祖父节点染成红色。

    LL 型场景,且无红色叔节点
    LL 型场景,且无红色叔节点

    RR 型场景与 LL 型场景对称,只需要将右旋操作改为左旋即可:

    RR 型场景,且无红色叔节点
    RR 型场景,且无红色叔节点
  • 场景五:LR、RL 型场景,且无红色叔节点

    如果新插入的红节点是红色父节点的右子节点,红色父节点是祖父节点的左子节点,同时新节点不存在红色叔节点,则需要先对父子节点进行左旋处理,再对旋转上去的新节点与原祖父节点进行右旋处理。最后,将新插入节点染成黑色,将原祖父节点染成红色:

    LR 型场景,且无红色叔节点
    LR 型场景,且无红色叔节点

    总的来说,就是让父节点与祖父节点分别做新插入节点的左右子节点,然后新插入的节点最终被染黑,祖父节点和父节点最终为红色。

    RL 型场景与 LR 型场景对称,先对父子节点做右旋处理,再对旋转上去的新节点与祖父节点做左旋处理,染色操作与 LR 型场景一致:

    RL 型场景,且无红色叔节点
    RL 型场景,且无红色叔节点

4 红黑树删除操作

红黑树的删除操作与二叉排序树的删除操作基本相同,但在某些情况下需要进行再平衡操作,以确保删除节点后的红黑树仍然符合红黑树的所有性质。

  • 场景一:删除只有一个节点的树

    如果红黑树中只有唯一的根节点,直接删除即可。

  • 场景二:删除叶子节点

    • 如果被删除的叶子节点是红色节点,直接删除即可:

      删除红色叶子节点
      删除红色叶子节点
    • 如果被删除的叶子节点是黑色节点,则需要先用这个节点做“幻影叶子节点”进行再平衡操作,再删除这个节点。

  • 普通场景:删除非叶子节点

    • 如果被删除节点只存在左子节点或右子节点,则用这个唯一的子节点代替被删除的节点:
      • 如果被删除的节点是红色节点,则不需要再做其他操作;
      • 如果被删除的节点是黑色节点,则需要从被删除节点的子节点开始进行再平衡操作。
    • 如果被删除节点同时存在左右子节点,则用其左子树中的最大节点(即前驱节点)的内容覆盖被删除节点,然后将这个左子树中的最大节点移除:
      • 如果被移除的左子树最大节点是红色节点,则按照二叉排序树的规则正常删除即可;
      • 否则需要从它的子节点开始进行再平衡操作(如果没有子节点,就用它本身作为幻影子节点)。

删除过程的再平衡操作相比插入过程更加复杂,我们将在下节的代码实现中再详细分析。