红黑树

**一棵高度为 $h$ 的二叉搜索树**，他可以**支持任何一种基本动态集合操作**，如搜索、查找一个元素的前驱结点、查找一个元素的后继节点、查找树中的最小值、查找树中的最大值、插入、删除操作等，**其时间复杂度均为 $O(h)$**，因此，**如果搜索树的高度较低时**，**这些集合操作会执行得较快**，然而，**如果树的高度较高时**，**这些集合操作可能并不比在链表上执行得快**，**红黑树是许多“****平衡****”搜索树中的一种**，**可以保证在最坏情况下基本动态集合操作的时间复杂度为 $O(lgn)$**。

## 1 含义

1. **红黑树是一棵二叉搜索树**，他**在每个节点上增加了一个存储位来表示节点的颜色**，**可以是 RED 或 BLACK**，**通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束**，**红黑树确保没有一条路径会比其他路径长出 2 倍**，因而是**近似平衡的**。
2. **树中每个节点包含 5 个属性**，分别为 $color$、$key$、$left$、$right$、$p$（父节点），**如果一个节点没有子节点或父节点**，**则该节点相应指针属性的值为 $NIL$**，**我们可以把这些 $NIL$ 视为指向二叉搜索树的叶节点**（外部节点）**的指针**，**而把带关键字的节点视为树的内部节点**。
3. 一棵红黑树是满足下面红黑性质的二叉搜索树：

1. **每个节点是红色的**，**或是黑色的**。
   2. **根节点是黑色的**。
   3. **每个叶节点**（$NIL$）**是黑色的**。
   4. **如果一个节点是红色的**，**则他的两个子节点都是黑色的**。
   5. **对每个节点**，**从该路径到其所有后代叶节点的简单路径上**，**均包含相同数目的黑色节点**。

![](/media/202201/2022-01-09_210750_208866.png)

> 注：非 $NIL$ 节点旁边的数字为该节点对应的黑高。
      >
4. **为了便于处理红黑树代码中的边界条件**，**使用一个哨兵来代表 $NIL$**：

1. **对于一棵红黑树 $T$**，**哨兵 $T.nil$ 是一个与树中普通节点有相同属性的对象**，**他的 $color$ 属性为 BLACK**，**而其他属性 $p$**、$left$、$right$、$key$**可以设为任意值**，**所有指向 $NIL$ 的指针都用指向哨兵 $T.nil$ 的指针替换**。
   2. **使用哨兵后**，**就可以将节点 $x$ 的 $NIL$ 孩子视为一个普通节点**，**其父节点为 $x$**，**尽管可以为树内的每一个 $NIL$ 新增一个不同的哨兵节点**，**使得每个 $NIL$ 的父节点都有这样的良定义**，**但这种做法会浪费空间**，**取而代之的是**，**使用一个哨兵 $T.nil$ 来代表所有的 $NIL$**（所有的叶节点和根节点的父节点），**哨兵的属性 $p$**、$left$、$right$**和**$key$**的取值并不重要**，**尽管为了方便起见可以在程序中设定他们**。

![](/media/202201/2022-01-09_210952_813615.png)
5. 我们通常将注意力放在红黑树的内部节点上，因为他们存储了关键字的值，因此在后面的叙述中，所画的红黑树都忽略了叶节点。

![](/media/202201/2022-01-09_211053_902175.png)
6. **从某个节点 $x$ 出发**（不含该节点）**到达一个叶节点的任意一条简单路径上的黑色节点个数称为该节点的黑高**，记为 $bh(x)$，根据性质 5，黑高的概念是明确定义的，因为**从该节点出发的所有下降到其叶节点的简单路径的黑节点个数都相同**，于是**定义红黑树的黑高为其根节点的黑高**。
7. **一棵有 $n$ 个内部节点的红黑树的高度至多为 $ 2lg(n + 1) $**。

## 2 操作

### 2.1 旋转

1. **搜索树的插入和删除操作在含 $n$ 个关键字的红黑树上**，**运行花费时间为 $O(lgn)$**，由于**这两个操作对树做了修改**，结果**可能违反红黑树的性质**，**为了维护这些性质**，**必须要改变树中某些节点的颜色以及指针结构**。
2. **指针结构的修改是通过旋转来完成的**，**这是一种能保持二叉搜索树性质的搜索树局部操作**，下图给出了两种旋转，即左旋和右旋：
   1. **当在某个节点 $x$ 上做左旋时**，**假设他的右孩子为 $y$ 而不是 $T.nil$**，$x$**可以为其右孩子不是 $T.nil$ 节点的树内任意节点**。
   2. **左旋以 $x$ 到 $y$ 的链为“支轴”进行**，**他使 $y$ 成为该子树新的根节点**，$x$**成为 $y$ 的左孩子**，**$y$ 的左孩子成为 $x$ 的右孩子**。

![](/media/202201/2022-01-09_211204_682570.png)
3. 具体实例如下：
   1. 下图给出了一个左旋的例子，该操作可以在 $O(1)$ 时间内完成，在旋转操作中只有指针改变，其他所有属性都保持不变，修改前的树和修改后的树进行中序遍历时，会产生相同的关键字列表。

![](/media/202201/2022-01-09_211730_846698.png)

### 2.2 插入

1. 我们**可以在 $O(lgn)$ 时间内完成向一棵含 $n$ 个节点的红黑树中插入一个新节点**。
2. **在插入新节点 $z$ 时**，**需要将 $z$ 着为红色**，此时**红黑树的性质可能会被破坏**：

1. **性质 1 和性质 3 继续成立**，**因为新插入的红节点的两个子节点都是哨兵 $T.nil$**。
   2. **性质 5**，**即从一个指定节点开始的每条简单路径上的黑节点的个数都是相等的**，**也会成立**，**因为节点 $z$ 代替了哨兵**（黑色），**并且节点 $z$ 本身是有哨兵孩子的红节点**。
   3. **性质 2 和性质 4 会被破坏**，**即根节点需要为黑色以及一个红节点不能有红孩子**，这两个性质可能被破坏是因为 $z$**被着为红色**：
      1. **如果 $z$ 是根节点**，**则破坏了性质 2**。
      2. **如果 $z$ 的父节点是红节点**，**则破坏了性质 4**。
3. **如果红黑树的性质发生变化后**，**我们需要对节点进行重新着色并旋转**，**直到修改后的树满足红黑树的性质**，**实际需要考虑 6 种情况**，而**其中三种与另外三种是对称的**，**主要取决于 $z$ 的父节点 $z.p$ 是 $z$ 的祖父节点 $z.p.p$ 的左孩子**，**还是右孩子**，**这里我们只考虑 $z.p$ 是左孩子的三种情况**：

1. **$z$ 父亲的兄弟节点**（或称为“叔节点”）$y$**是红色的**：

1. **这种情况在 $z.p$ 和 $y$ 都是红色时发生**，**此时性质 4 被违反**。
      2. **因为 $z.p.p$ 是黑色的**，**所以将 $z.p$ 和 $y$ 都着为黑色**，**以此解决 $z$ 和 $z.p$ 都是红色的问题**，**将 $z.p.p$ 着为红色以保持性质 5**。
      3. **然后把 $z$ 的祖父 $z.p.p$ 作为新的 $z$ 以继续迭代**，即**指针 $z$ 在树中上移两层**。
      4. **现在性质 4 的破坏只可能发生在新的红色节点 $z$ 和他的父节点之间**，**条件是如果父节点也为红色的**。

![](/media/202201/2022-01-09_211929_029267.png)
   2. **$z$ 的叔节点 $y$ 是黑色的且 $z$ 是一个右孩子**：
   3. **$z$ 的叔节点 $y$ 是黑色的且 $z$ 是一个左孩子**：

1. **在情况 2 和情况 3 中**，**$z$ 的叔节点 $y$ 是黑色的**，**通过 $z$ 是 $z.p$ 的右孩子还是左孩子来区别这两种情况**。
      2. **在情况 2 中**，**节点 $z$ 是他的父节点的右孩子**，**可以用一个左旋来将此情况转变为情况 3**，**此时节点 $z$ 为左孩子**，**因为 $z$ 和 $z.p$ 都是红色的**，**所以该旋转对节点的黑高和性质 5 都无影响**。
      3. **在情况 3 中**，**改变某些节点的颜色并做一次右旋**，**以保持性质 5**。

![](/media/202201/2022-01-09_211953_944909.png)

### 2.3 删除

1. **红黑树只有在黑色节点被删除的时候才需要进行调整**，**因为只有这种情况下才会引起对性质 5 的违反**（或许还有性质 4）。
2. 红黑树也是一种二叉搜索树，因此在**删除红黑树的一个节点的时候**，**首先要执行二叉搜索树的删除过程**，**然后再针对删除后可能会违反的红黑树性质**，**通过重新旋转和着色等一系列操作来修正该树**，**使之重新成为一棵红黑树**。

#### 2.3.1 二叉搜索树删除

1. 二叉搜索树删除节点有三种情况：
   1. **如果节点 $z$ 没有孩子节点**，**那么只需要简单的将其删除即可**，**并修改父节点**，**用 $NIL$ 来替换 $z$**。
   2. **如果节点 $z$ 只有一个孩子节点**，**那么将孩子节点提升到 $z$ 的位置**，**并修改 $z$ 的父节点**，**用 $z$ 的孩子替换 $z$**。

![](/media/202201/2022-01-09_212542_780292.png)
      ![](/media/202201/2022-01-09_212550_927430.png)
   3. **如果 $z$ 有两个孩子节点**，**那么找 $z$ 的后继节点 $y$**（一定在 $z$ 的右子树中）：

1. **如果 $y$ 是 $z$ 的右孩子**，**那么用 $y$ 替换 $z$**，**并仅留下 $y$ 的右孩子**。

![](/media/202201/2022-01-09_212645_392347.png)
      2. **如果 $y$ 位于 $z$ 的右子树但并不是 $z$ 的右孩子**，**在这种情况下**，**先用 $y$ 的右孩子替换 $y$**，**然后再用 $y$ 替换 $z$**。

![](/media/202201/2022-01-09_212652_613813.png)

#### 2.3.2 删除后红黑树的调整

1. 下面我们主要讲述一下在**被删节点为黑色节点**时删除后应该重新调整，使之达到平衡，设 $x$ 为被删节点的替换节点，$x$**一定是平衡的**，而 $x$**的父节点由于删除了一个黑色节点**，**会导致左右子树的不平衡**，假设这里 $x$**节点为红色节点**，**则直接将 $x$ 节点变成黑色**，**这时整棵树是平衡的**，**若 $x$ 是黑色**，**要实现平衡**，**有如下四种情况**：
   1. **$x$ 的兄弟节点 $w$ 是红色的**：![delfixup-case1](/media/202201/2022-01-09_2127390.1735109556133213.png)
      1. **删除节点后**，$x$**的父节点 $x.p$ 经过 $x$ 到达叶子节点的路径的黑高产生变化**，**以 $x.p$ 为根的树不再平衡**。
      2. **这时 $x$ 是平衡的**，**但是因为节点 $B$ 的左子树被删去了一个黑色节点**，**导致节点 $B$ 的左子树黑高少了 1**，**所以节点 $B$ 是不平衡的**，此时，$bh_a = bh_b = bh_r - 1$，$bh_r = bh_d = bh_e = bh_f$。
      3. 因此，**可以对节点 $B$ 进行一次左旋**，**然后修改节点 $B$ 和节点 $D$ 的颜色**，**转变成情况 2**、**3**、**4 进行处理**（上图转换后，$x$ 仍为 $A$ 节点，$B$ 节点仍是不平衡的）。
   2. **$x$ 的兄弟节点 $w$ 是黑色的**，**并且 $w$ 的两个子节点都是黑色的**：![delfixup-case2](/media/202201/2022-01-09_2127570.5031716318790875.png)
      1. **与情况 1 一样**，**在删除节点后**，**左图节点 $B$ 不平衡**，**其中 $bh_a = bh_b = bh_r = bh_d = bh_e = bh_f$**，$B$**节点左子树的黑高为 $bh_a + 1$**，**右子树的黑高为 $bh_r + 2$**，**左子树黑高小于右子树黑高**。
      2. **可以直接修改节点 $D$ 为红色**，**这样就可以使节点 $B$ 达到平衡**，**但是这又会使得节点 $B$ 的黑高比原来少 1**，**会引起节点 $B$ 往上的树不平衡**：
         1. **若此时 $B$ 节点为红色**（即上图 Case 2.1 所示），**则直接将 $B$ 节点修改为黑色**，**此时 $B$ 的黑高又恢复如初**，**不影响其他树的平衡**。
         2. **若节点 $B$ 为黑色**，**则需要从该节点开始继续向上回溯调整树的黑高**，**此时 $B$ 节点成为新的 $x$ 节点**。
   3. **$x$ 的兄弟节点 $w$ 是黑色的，而且 $w$ 的左孩子是红色的，$w$ 的右孩子是黑色的**：![delfixup-case3](/media/202201/2022-01-09_2128130.7805155272727132.png)
      1. **这个和插入节点时的情况 2 类似**，**可以通过旋转将其转变为情况 4 进行处理**，这里也有两种子情况：
         1. **$x.p$ 为红色**。
         2. **c$x.p$ 为黑色**。
      2. 简单证明一下**节点 $w$ 右旋转后节点 $w$ 的红黑性质不会被破坏**：
         1. **旋转前**，**节点 $w$ 是平衡的**，**所以 $bh_r = bh_d = bh_e + 1 = bh_f + 1$**。
         2. **旋转后**，**节点 $w$ 指向了节点 $C$**，**此时**：
            1. **节点 $w$ 的左子树黑高为 $bh_r$**，**右子树的黑高为 $bh_e + 1 = bh_r$**，**所以节点 $w$ 依然是平衡的**。
            2. **再看节点 $D$**，**左子树的黑高为 $bh_d$**，**右子树的黑高为 $bh_e + 1 = br_d$**，**所以节点 $D$ 也是平衡的**。
         3. **所以**，**这一旋转操作不会影响节点 $B$ 的右子树的红黑性质**，**仅仅将其转变成情况 4 进行处理而已**。
   4. $x$**的兄弟节点 $w$ 是黑色的**，**并且 $w$ 的右孩子是红色的**，对于这种情形，可以分为如下 4 种子情形：
      1. $x.p$**为黑色**，**并且 $w$ 的左孩子为黑色的**：![delfixup-case41](/media/202201/2022-01-09_2128310.904806696068503.png)

1. **因为删除节点导致节点 $B$ 不平衡**，其中 $bh_a = bh_b = bh_r = bh_d$，$bh_e = bh_f = bh_a + 1$。
         2. **对节点 $B$ 进行左旋转后**，**将 $D$ 修改为与 $B$ 相同的颜色**（即更改成为其父节点的颜色），**修改 $B$ 的颜色为黑色**（节点 B 的颜色可以直接修改，不用考虑当前 $B$ 为红色还是黑色），**节点 $E$ 的颜色也修改成黑色**，**可以证得节点 $B$ 已经达到平衡**，**同时节点 $D$ 也达到平衡**，**并且该树从根开始的黑高在删除前和删除并旋转操作后不变**，**因此不会影响到其他树的平衡**，**也就是说**，**执行完情况 1 的操作之后**，**整棵树已经平衡了**。
      2. $x.p$**为黑色**，**并且 $w$ 的左孩子为红色的**：![delfixup-case42](/media/202201/2022-01-09_2128440.4447865951244143.png)

1. 通过上图可知，$bh_a = bh_b$，$bh_r = bh_d = bh_e = bh_f = bh_a + 1 = bh_b + 1$。
         2. **对节点 $B$ 进行左旋转后**，**将 $D$ 修改为与 $B$ 相同的颜色**（即更改成为其父节点的颜色），**然后将节点 $B$ 和节点 $E$ 的颜色直接修改为黑色**，**可以证得旋转后节点 $B$ 是平衡的**，**节点 $D$ 也是平衡的**，**并且该树从根开始的黑高在删除前和删除并旋转操作后不变**，**因此不会影响到其他树的平衡**，**也就是说**，**执行完情况 2 的操作之后**，**整棵树已经平衡了**。
      3. $x.p$**为红色**，**并且 $w$ 的左孩子为黑色的**：![delfixup-case43](/media/202201/2022-01-09_2128570.8714210914954738.png)

1. 通过上图可知，$bh_a = bh_b = bh_r = bh_d$，$bh_e = bh_f = bh_a + 1$。
         2. **对节点 $B$ 进行左旋转后**，**将节点 $D$ 修改为与 B 相同的颜色**（即更改成为其父节点的颜色），**然后将节点 $B$ 和节点 $E$ 的颜色直接修改为黑色**，**可以证得旋转后节点 $B$ 是平衡的**，**节点 $D$ 也是平衡的**，**并且该树从根开始的黑高在删除前和删除并旋转操作后不变**，**因此不会影响到其他树的平衡**，**而除非旋转操作后**，$x$**节点为根节点**，**违反性质 2**，**但是我们在 $x$ 为根节点时就会退出循环**，**并且会直接再将 $x$ 染成黑色**，**此时整棵树就平衡了**。
      4. $x.p$**为红色**，**并且 $w$ 的左孩子为红色的**：![delfixup-case44](/media/202201/2022-01-09_2129220.204914929014143.png)

1. 通过上图可知，$bh_r = bh_d = bh_e = bh_f$，$bh_a = bh_b = bh_r - 1$。
         2. **对节点 $B$ 进行左旋转后**，**将节点 $D$ 修改为与 B 相同的颜色**（即更改成为其父节点的颜色），**然后将节点 $B$ 和节点 $E$ 的颜色直接修改为黑色**，**可以证得旋转后节点 $B$ 是平衡的**，**节点 $D$ 也是平衡的**，**并且该树从根开始的黑高在删除前和删除并旋转操作后不变**，**因此不会影响到其他树的平衡**，**而除非旋转操作后**，$x$**节点为根节点**，**违反性质 2**，**但是我们在 $x$ 为根节点时就会退出循环**，**并且会直接再将 $x$ 染成黑色**，**此时整棵树就平衡了**。

> 注：上述的 1、2、3、4 四种情况是针对节点 $x$ 是一棵左子树而言的，当 $x$ 是一棵右子树时其操作与上述操作完全对称。
         >

## 3 时间复杂度

1. **红黑树插入需要 $O(lgn)$ 次**，**对插入节点后的调整所做的旋转操作不会超过 2 次**（注：这里的 2 次指的是单次回溯）。
2. **红黑树删除沿树回溯至多 $O(lgn)$ 次**，**对删除节点后的调整所做的旋转操作不会超过 3 次**（注：这里的 3 次指的是单次回溯）。

## 参考文献

1. 《算法导论（第三版）》
2. [红黑树的原理及实现](https://ivanzz1001.github.io/records/post/data-structure/2018/06/24/ds-red-black-tree)。
3. [关于红黑树(R-B tree)原理，看这篇如何](https://www.cnblogs.com/LiaHon/p/11203229.html)。