1、红黑树介绍

1.1、什么是红黑树？

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

1.2、为什么有红黑树？

​ 红黑树和上面的平衡二叉树类似，本质上都是为了解决排序二叉树在极端情况下退化成链表导致检索效率大大降低的问题。

1.3、红黑树和AVL树的区别？

AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多；
红黑是弱平衡的，用非严格的平衡来换取增删节点时候旋转次数的降低；
所以简单说，搜索的次数远远大于插入和删除，那么选择AVL树，如果搜索，插入删除次数几乎差不多，应该选择RB树。

比如，下图是一个红黑树，但不是AVL树。

2、红黑树的特性

特性：

• 性质1：每个节点要么是红色，要么是黑色。
• 性质2：根节点永远是黑色的。
• 性质3：所有的叶子节点都是空节点（即null），并且是黑色的。
• 性质4：每个红色节点的两个子节点都是黑色。（从每个叶子到根的路径上不会有两个连续的红色节点。）
• 性质5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。

3、红黑树插入

​ 红黑树的插入过程和二叉查找树插入过程基本类似，不同的地方在于，红黑树插入新节点后，需要进行调整，以满足红黑树的性质。 默认新插入的节点颜色为红色。

情况1：

​ 插入的新节点 N 是红黑树的根节点，这种情况下，我们把节点 N 的颜色由红色变为黑色，性质2（根是黑色）被满足。

情况2：

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

情况3：

​ N的父节点为红色（根据性质3，N的祖父节点必为黑色）。

• N的叔父节点为红色。这种情况，将N的父节点和叔父节点的颜色都改为黑色，若祖父节点是跟节点就将其改为黑色，否则将其颜色改为红色，并以祖父节点为插入的目标节点从情况1开始递归检测。

• N的叔父节点为黑色， 且N和N的父节点在同一边（即父节点为祖父的左儿子时，N也是父节点的左儿子。父节点为祖父节点的右儿子时。N也是父节点的右儿子）。以父节点为祖父节的左儿子为例，将父节点改为黑色，祖父节点改为红色，然后以祖父节点为基准右旋。（N为父节点右儿子时做相应的左旋。）

• N的叔父节点为黑色，切N和N的父节点不在同一边（即父节点为祖父的左儿子时，N是父节点的右儿子。父节点为祖父节点的右儿子时。N也是父节点左右儿子）。以父节点为祖父节点的左儿子为例。以父节点为基准，进行左旋，然后以父节点为目标插入节点进入情况3的b情况进行操作。

4、红黑树删除

情况1：

​ 替换节点是红色节点 即替换的节点是红色节点，删除之后不影响红黑树的平衡，只需要把替换节点的颜色设成被删除节点的颜色即可重新平衡。

​ 处理: 删除节点D，查找到替换节点R，R设成D节点的颜色，再替换D节点位置。

情况2：

​ 替换节点是黑色节点、且是其父节点的左子节点。 替换节点是黑色节点时，删除之后破坏了红黑树的平衡，需要考虑自平衡处理。而此又细分为 4 种场景。

• 替换节点的兄弟节点是红色。删除黑色节点，左子树中黑色节点数减少一个，可以通过一些操作，达到间接借用红色的兄弟节点来补充左子树中黑色节点数。

​ 处理： 替换节点的父节点 P 设置红色、兄弟节点 S 设置成黑色，再对节点 P 左旋操作，变成场景 2.4。

• 替换节点的兄弟节点是黑色且兄弟节点的右子节点是红色、左子节点任意颜色。同样是间接借用兄弟节点的红色右子节点补充到左子树中，达到红黑树的平衡。

​ 处理： 替换节点的兄弟节点 S 设置成父节点P的颜色，兄弟节点的右子节点 SR 设置为黑色，父节点P设置为 黑色，再对节点 P 左旋操作。此时节点R替换到删除节点位置之后，红黑树重新达到平衡状态。

• 替换节点的兄弟节点是黑色且兄弟节点的左子节点是红色，右子节点是黑色。

​ 处理： 替换节点的兄弟节点 S 设置成红色，兄弟节点的左子节点 SL 设置为黑色，再对节点 S 右旋操作，转换到了场景 2.2，再进行场景 2.2 的操作。

• 替换节点的兄弟节点的左右子节点都是黑色。兄弟节点的子节点不能借用，就只能借用兄弟节点了。

​ 处理： 替换节点的兄弟节点 S 设置成红色，以父节点 P 当作替换节点，然后自底向上处理。

情况3： 替换节点是黑色节点、且是其父节点的右子节点。（与场景 2 镜像）

• 替换节点的兄弟节点是红色。
  处理：替换节点的父节点 P 设置红色、兄弟节点 S 设置成黑色，再对节点 P 右旋操作，变成场景3.4。

• 替换节点的兄弟节点是黑色且兄弟节点的左子节点是红色、右子节点任意颜色。

  处理：替换节点的兄弟节点 S 设置成父节点 P 的颜色，兄弟节点的左子节点 SL 设置为黑色，父节点P 设置为黑色，再对节点 P 右旋操作。此时节点 R 替换到删除节点位置之后，红黑树重新达到平衡状态。

• 替换节点的兄弟节点是黑色且兄弟节点的右子节点是红色、左子节点为黑色。

处理：替换节点的兄弟节点 S 设置成红色，兄弟节点的右子节点 SL 设置为黑色，再对节点S左旋操作，转换到了场景 3.2，再进行场景 3.2 的操作。

• 场景 3.4：替换节点的兄弟节点的左右子节点都是黑色。 处理：替换节点的兄弟节点 S 设置成红色，以父节点 P 当作替换节点，然后自底向上处理。

5、参考资料

1、《通俗易懂的红黑树图解(上)》

2、《通俗易懂的红黑树图解(下)》