今天我们要说的红黑树就是就是一棵非严格均衡的二叉树，均衡二叉树又是在二叉搜索树的基础上增加了自动维持平衡的性质，插入、搜索、删除的效率都比较高。红黑树也是实现 TreeMap 存储结构的基石。

红黑树就是非严格均衡的二叉搜索树。

---

一、红黑树规则特点

红黑树具体有哪些规则特点呢？具体如下：

• 节点分为红色或者黑色。

• 根节点必为黑色。

• 叶子节点都为黑色，且为 null。

• 连接红色节点的两个子节点都为黑色（红黑树不会出现相邻的红色节点）。

• 从任意节点出发，到其每个叶子节点的路径中包含相同数量的黑色节点。

• 新加入到红黑树的节点为红色节点。

规则看着好像挺多，没错，因为红黑树也是均衡二叉树，需要具备自动维持平衡的性质，上面的 6 条就是红黑树给出的自动维持平衡所需要具备的规则。

我们看一看一个典型的红黑树到底是什么样儿？

 首先解读一下规则，除了字面上看到的意思，还隐藏了哪些意思呢？

 ①从根节点到叶子节点的最长路径不大于最短路径的 2 倍

怎么样的路径算最短路径？从规则 5 中，我们知道从根节点到每个叶子节点的黑色节点数量是一样的，那么纯由黑色节点组成的路径就是最短路径。

什么样的路径算是最长路径？根据规则 4 和规则 3，若有红色节点，则必然有一个连接的黑色节点，当红色节点和黑色节点数量相同时，就是最长路径，也就是黑色节点（或红色节点）*2。

 ②为什么说新加入到红黑树中的节点为红色节点

从规则 4 中知道，当前红黑树中从根节点到每个叶子节点的黑色节点数量是一样的，此时假如新的是黑色节点的话，必然破坏规则。

但加入红色节点却不一定，除非其父节点就是红色节点，因此加入红色节点，破坏规则的可能性小一些，下面我们也会举例来说明。

什么情况下，红黑树的结构会被破坏呢？破坏后又怎么维持平衡，维持平衡主要通过两种方式【变色】和【旋转】，【旋转】又分【左旋】和【右旋】，两种方式可相互结合。

下面我们从插入和删除两种场景来举例说明。

---

二、 红黑树节点插入

 当我们插入值为 66 的节点时，红黑树变成了这样：

很明显，这个时候结构依然遵循着上述 6 大规则，无需启动自动平衡机制调整节点平衡状态。

如果再向里面插入值为 51 的节点，这个时候红黑树变成了这样：

 很明显现在的结构不遵循规则 4 了，这个时候就需要启动自动平衡机制调整节点平衡状态。

1、变色 

我们可以通过变色的方式，使结构满足红黑树的规则：

• 首先解决结构不遵循规则 4 这一点（红色节点相连，节点 49-51），需将节点 49 改为黑色。

• 此时我们发现又违反了规则 5（56-49-51-XX 路径中黑色节点超过了其他路径），那么我们将节点 45 改为红色节点。

• 哈哈，妹的，又违反了规则 4（红色节点相连，节点 56-45-43），那么我们将节点 56 和节点 43 改为黑色节点。

• 但是我们发现此时又违反了规则 5（60-56-XX 路径的黑色节点比 60-68-XX 的黑色节点多），因此我们需要调整节点 68 为黑色。

• 完成！

最终调整完成后的树为：

但并不是什么时候都那么幸运，可以直接通过变色就达成目的，大多数时候还需要通过旋转来解决。

 如在下面这棵树的基础上，加入节点 65：

 插入节点 65 后进行以下步骤：

这个时候，你会发现对于节点 64 无论是红色节点还是黑色节点，都会违反规则 5，路径中的黑色节点始终无法达成一致，这个时候仅通过【变色】已经无法达成目的。

我们需要通过旋转操作，当然【旋转】操作一般还需要搭配【变色】操作。旋转包括【左旋】和【右旋】。

2、旋转

左旋：逆时针旋转两个节点，让一个节点被其右子节点取代，而该节点成为右子节点的左子节点。

左旋操作步骤如下：首先断开节点 PL 与右子节点 G 的关系，同时将其右子节点的引用指向节点 C2；然后断开节点 G 与左子节点 C2 的关系，同时将 G 的左子节点的应用指向节点 PL。

右旋：顺时针旋转两个节点，让一个节点被其左子节点取代，而该节点成为左子节点的右子节点。 

右旋操作步骤如下：首先断开节点 G 与左子节点 PL 的关系，同时将其左子节点的引用指向节点 C2；然后断开节点 PL 与右子节点 C2 的关系，同时将 PL 的右子节点的应用指向节点 G。

无法通过变色而进行旋转的场景分为以下四种：

左左节点旋转 

这种情况下，父节点和插入的节点都是左节点，如下图(旋转原始图1)这种情况下，我们要插入节点 65。

规则如下：以祖父节点【右旋】，搭配【变色】。

按照规则，步骤如下：

左右节点旋转

这种情况下，父节点是左节点，插入的节点是右节点，在旋转原始图 1 中，我们要插入节点 67。

规则如下：先父节点【左旋】，然后祖父节点【右旋】，搭配【变色】。

按照规则，步骤如下：

右左节点旋转

这种情况下，父节点是右节点，插入的节点是左节点，如下图（旋转原始图 2）这种情况，我们要插入节点 68。

规则如下：先父节点【右旋】，然后祖父节点【左旋】，搭配【变色】。

按照规则，步骤如下：

右右节点旋转

这种情况下，父节点和插入的节点都是右节点，在旋转原始图 2 中，我们要插入节点 70。

规则如下：以祖父节点【左旋】，搭配【变色】。

按照规则，步骤如下：

红黑树插入总结如下图：

---

作者：梁洪  来源：51CTO技术栈

彻底搞懂红黑树 - 知乎