红黑树算法和应用 红黑树的原理插入

1.红黑树的概念

红黑树是一种自平衡的二叉查找树，是一种高效的查找树。它是由 Rudolf Bayer 于1978年发明，在当时被称为对称二叉 B 树(symmetric binary B-trees)。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的红黑树。红黑树具有良好的效率，它可在 O(logN) 时间内完成查找、增加、删除等操作。因此，红黑树在业界应用很广泛，比如 Java 中的 TreeMap，JDK 1.8 中的 HashMap、C STL 中的 map 均是基于红黑树结构实现的。考虑到红黑树是一种被广泛应用的数据结构，所以我们很有必要去弄懂它。

2.红黑树的性质

红黑树是一棵二叉树， 有五大特征：

特征一： 节点要么是红色，要么是黑色（红黑树名字由来）。

特征二： 根节点是黑色的

特征三： 每个叶节点(nil或空节点)是黑色的。

特征四： 每个红色节点的两个子节点都是黑色的（相连的两个节点不能都是红色的）。

特征五： 从任一个节点到其每个叶子节点的所有路径都是包含相同数量的黑色节点。

3.红黑树铺垫：左旋和右旋3.1 左旋

左旋的示意图可以参考下面这张图

左旋

左旋的伪代码《算法导论》：参考上面的示意图和下面的伪代码，理解“红黑树T的节点x进行左旋”是如何进行的。

LEFT-ROTATE(T, x) 01 y ← right[x] // 前提：这里假设x的右孩子为y。下面开始正式操作 02 right[x] ← left[y] // 将 “y的左孩子” 设为 “x的右孩子”，即 将β设为x的右孩子 03 p[left[y]] ← x // 将 “x” 设为 “y的左孩子的父亲”，即 将β的父亲设为x 04 p[y] ← p[x] // 将 “x的父亲” 设为 “y的父亲” 05 if p[x] = nil[T] 06 then root[T] ← y // 情况1：如果 “x的父亲” 是空节点，则将y设为根节点 07 else if x = left[p[x]] 08 then left[p[x]] ← y // 情况2：如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子” 09 else right[p[x]] ← y // 情况3：(x是它父节点的右孩子) 将y设为“x的父节点的右孩子” 10 left[y] ← x // 将 “x” 设为 “y的左孩子” 11 p[x] ← y // 将 “x的父节点” 设为 “y”

左旋的动态图可以见下图：

3.2 右旋

右旋的示意图可以参考下面这张图

右旋的伪代码《算法导论》：参考上面的示意图和下面的伪代码，理解“红黑树T的节点y进行右旋”是如何进行的。

RIGHT-ROTATE(T, y) 01 x ← left[y] // 前提：这里假设y的左孩子为x。下面开始正式操作 02 left[y] ← right[x] // 将 “x的右孩子” 设为 “y的左孩子”，即 将β设为y的左孩子 03 p[right[x]] ← y // 将 “y” 设为 “x的右孩子的父亲”，即 将β的父亲设为y 04 p[x] ← p[y] // 将 “y的父亲” 设为 “x的父亲” 05 if p[y] = nil[T] 06 then root[T] ← x // 情况1：如果 “y的父亲” 是空节点，则将x设为根节点 07 else if y = right[p[y]] 08 then right[p[y]] ← x // 情况2：如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子” 09 else left[p[y]] ← x // 情况3：(y是它父节点的左孩子) 将x设为“y的父节点的左孩子” 10 right[x] ← y // 将 “y” 设为 “x的右孩子” 11 p[y] ← x // 将 “y的父节点” 设为 “x”

右旋的动态图可以见下图：

4.红黑树的插入

红黑树的插入总体可以分为7种情况：

• 1.插入的节点是根节点
• 2.插入的节点的父节点是黑色
• 3.插入的节点的父节点是红色，叔叔节点也是红色
• 4.插入的节点的父节点是红色，叔叔节点是黑色
• 4.1 左左插入
• 4.2 左右插入
• 4.3 右右插入
• 4.4 右左插入

其中第四点可以细分为4种情况，所以加上前三种一共是7种。下面依次来看。

注意：这里要说明的是，因为新插入的节点如果默认是黑色的话，很容易使得红黑树性质5得不到满足，因此默认我们插入的新节点为红色。

1.插入的节点是根节点

假如将要插入的新节点是N，这种情况下，我们把节点 N 的颜色由红色变为黑色，性质2（根是黑色）被满足。同时 N 被染成黑色后，红黑树所有路径上的黑色节点数量增加一个，性质5（从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点）仍然被满足。

2.插入的节点的父节点是黑色

N 的父节点是黑色，这种情况下，性质4（每个红色节点必须有两个黑色的子节点）和性质5没有受到影响，不需要调整。

3.插入的节点的父节点是红色，叔叔节点也是红色

N 的父节点是红色（节点 P 为红色，其父节点必然为黑色），叔叔节点 U 也是红色。由于 P 和 N 均为红色，所有性质4被打破，此时需要进行调整。这种情况下，先将 P 和 U 的颜色染成黑色，再将 G 的颜色染成红色。此时经过 G 的路径上的黑色节点数量不变，性质5仍然满足。但需要注意的是 G 被染成红色后，可能会和它的父节点形成连续的红色节点，此时需要递归向上调整。

4.插入的节点的父节点是红色，叔叔节点是黑色4.1插入的节点的父节点是红色，叔叔节点是黑色(左左)

N 的父节点为红色，叔叔节点为黑色。N 是 P 的左孩子，且节点 P 是 G 的左孩子。此时对 G 进行右旋，调整 P 和 G 的位置，并互换颜色。经过这样的调整后，性质4被恢复，同时也未破坏性质5。

4.2插入的节点的父节点是红色，叔叔节点是黑色(左右)

N 的父节点为红色，叔叔节点为黑色。节点 N 是 P 的右孩子，且节点 P 是 G 的左孩子。此时先对节点 P 进行左旋，调整完之后，我们发现就将"左右"这个情况转化成了左左的情况。进而继续使用左左的方法继续调整。

4.3插入的节点的父节点是红色，叔叔节点是黑色(右右)

N 的父节点为红色，叔叔节点为黑色。N 是 P 的右孩子，且节点 P 是 G 的右孩子。此时对 G 进行左旋，调整 P 和 G 的位置，并互换颜色。经过这样的调整后，性质4被恢复，同时也未破坏性质5。

4.4.插入的节点的父节点是红色，叔叔节点是黑色(右左)

N 的父节点为红色，叔叔节点为黑色。节点 N 是 P 的左孩子，且节点 P 是 G 的右孩子。此时先对节点 P 进行右旋，调整完之后，我们发现就将"右左"这个情况转化成了右右的情况。进而继续使用右右的方法继续调整。

第四点是最为复杂，我们总结如下：

左左：爸爸变黑色，爷爷变红色爷爷右旋

左右：爸爸左旋，左旋之后爸爸成了儿子（也就是新插入的红色节点），之后和【左左插】一样爸爸变黑色，爷爷变红色爷爷右旋

右右：爸爸变黑色，爷爷变红色爷爷左旋

左右：爸爸右旋，右旋之后爸爸成了儿子（也就是新插入的红色节点），之后和【右右插】一样爸爸变黑色，爷爷变红色爷爷左旋

5.红黑树的删除

红黑树的删除相对于插入而言，更为复杂一些，我们还是要像插入那样，根据情况依次进行分析。A. 删除的是叶子节点且该叶子节点是红色的 —> 无需修复，因为它不会破坏红黑树的5个特性

B. 删除的是叶子节点且该叶子节点是黑色的 —> 很明显会破坏特性5，需要修复。

C. 删除的节点（为了便于叙述我们将其称为P）下面有一个子节点 S，对于这种情况我们通过 将P和S的值交换的方式，巧妙的将删除P变为删除S，S是叶子节点，这样C这种情况就会转 换为A, B这两种情况：C1： P为黑色，S为红色 —> 对应 A 这种情况C2: P为黑色或红色，S为黑色 — > 对应 B 这种情况

D. 删除的节点有两个子节点，对于这种情况，我们通过将P和它的后继节点N的值交换的方 式，将删除节点P转换为删除后继节点N，而后继节点只可能是以下两种情况：

D1: N是叶子节点 — > 对应情况 A 或 B

D2: N有一个子节点 ---- > 对应情况 C

看下面的例子，通过下面的例子分别来看看ABCD 四个点

1.假设我们要删除3这个点，可以看到删除的是叶子节点且该叶子节点是红色的，就是对应的规则A，我们无须修复。

2.假设我们要删除1这个点，可以看到删除的是叶子节点且该叶子节点是黑色的，对应规则B，后面要分析进行修复。

3.假设我们要删除9这个点，可以看到它的下面只有有一个子节点 S，对应规则C，这个时候，我们只要将9和10的值互换，这个时候就转化成了删除叶子节点。

4.假设我们要删除6这个节点，那么就会寻找6的后继节点7，将两者的值互换，由于此时后继节点转化成了叶子节点，这就又转化为了规则A和规则B。当然后继结点也可能不是叶子节点，这样后继结点的下面还有一个子节点，这样就转化成了规则C。

所以我们发现，无论多复杂的情况，都可以转化为删除叶子节点，而删除红叶色节点不需要修改红黑树，而修改黑色叶子节点需要修改红黑树，因此我们重点讨论删除叶子节点是黑色的情况。

删除叶子节点是黑色的节点

注意：5.1-5.5 这五种情况将具体讲解如何删除。在给例子时，我们是假设要删除的黑色节点是父节点的左子树。其实如果删除的黑色节点是父节点的右子树，则和左子树形成轴对称图形，其变换原理是类似的，就不再画出。

5.1.兄弟节点是黑色的，且有一个右节点(一定是红色的)

5.1也可以再分为两种情况，但是两种情况的处理是一样的方式。

step1：将父节点的颜色赋给兄弟节点。

step2：将父节点和兄弟节点都置为黑色。

step3：对父节点进行左旋。

还有另外两种情况和上述两种情况是轴对称的情况，可以参考上面的过程。

5.2. 兄弟节点是黑色的，且有一个左节点(一定是红色的)

5.2也可以再分为两种情况，但是两种情况的处理是一样的方式。

step1：将左孩子设置为黑色。

step2：将兄弟节点设置为红色。

step3：对兄弟节点进行右旋。

step4：经过step1-3之后，就将5.2转化成了5.1的情况处理了。

还有另外两种情况和上述两种情况是轴对称的情况，可以参考上面的过程。

5.3. 兄弟节点是黑色的，且有两个节点(一定是红色的)

5.3也可以再分为两种情况，但是两种情况的处理是一样的方式。

step1：将父节点颜色赋给兄弟节点

step2：将兄弟节点的右孩子设置为黑色。

step3：对父节点设置为黑色

step4：对父节点进行右旋

还有另外两种情况和上述两种情况是轴对称的情况，可以参考上面的过程。

5.4 兄弟节点是黑色的,没有子节点

5.4也可以再分为两种情况，但是两种情况的处理是一样的方式。step1：将兄弟节点设置为红色，将父节点设置为当前节点递归，直到根节点，或遇到红色节点。

还有另外两种情况和上述两种情况是轴对称的情况，可以参考上面的过程。

5.5 兄弟节点是红色的

step1：将兄弟节点设为黑色

step2：将兄弟节点的左孩子设为红色

step3：对父节点左旋

还有另外一种情况和上述情况是轴对称的情况，可以参考上面的过程。

实现代码

理解原理后代码实现起来会相对简单一些。这里给出一个参考文章。

参考文章

https://blog.csdn.net/net_wolf_007/article/details/79706498

参考资料

1.https://www.bilibili.com/video/BV1KA41187v6?from=search&seid=14951139765609390496(这个视频是讲是讲删除讲的比较好的)

2.https://zhuanlan.zhihu.com/p/22800206(这篇文章是讲删除讲的比较好的)

3.https://blog.csdn.net/net_wolf_007/article/details/79706498(这篇文章是讲实现讲的比较好的)

4.https://www.cs.usfca.edu/~galles/visualization/RedBlack.html 在线演示5.https://www.cnblogs.com/skywang12345/p/3245399.html

,