原创码字不易，转载请注明出处，谢谢~

红黑树系列2——红黑树的删除（码字中，待发表）

红黑树系列3——红黑树的应用（码字中，待发表）

红黑树系列4——红黑树的代码实现（码代码中，待发表）

红黑树动态建立，删除网站（强强强强烈推荐，根据网页上自己构建和删除几遍红黑树，比看文章有用太多太多）：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

目录

一、红黑树的建立

1、建立红黑树

例子1、解决连续右右红色节点

例子2、解决连续左左红色节点

例子3、解决连续右左红色节点

例子4、解决连续左右红色节点

一、红黑树的建立

红黑树是一棵自平衡二叉搜索树。有以下四个性质。我总结为：三黑，一红，一相同。

三黑：

1）根节点是黑色节点

2）红色节点的两个孩子（左孩子和有孩子节点）节点是黑色

3）最终的叶子节点是黑色（这里指null节点，只谈概念时，可以忽略null叶子节点）

一红：

1）新插入的节点是红色

一同：

1）从任意一个节点出发，到达其孩子节点的所有路径中。每个路径中，包含的黑色节点个数相同。举例如下：根节点4，有5个叶子节点，分别是：1，3，5，7，9。从根节点4出发，分别到达5个叶子节点，均包含1个黑色节点。

1、建立红黑树

首先，在建立红黑树的时候，必须切记一点：红黑树的建立过程，就是解决连续两个红色节点的过程。只要记住这一点，红黑树建立过程中的所有旋转和变色问题迎刃而解。

下面给出四个例子，只要能够明白例子1和例子2，就能自己摸清楚红黑树的建立过程。例子3和例子4可以作为自己练习。

例子1、解决连续右右红色节点

假设初始序列为：1，2，3，4，5，6，7，8，9，10。共10个数字，顺序输入，建立一棵红黑树。

1）输入1。建立根节点。根据红黑树的三黑性质之一的：根节点为黑色。则将1置为黑色。

2）输入2。根据红黑树的一红性质：新插入节点为红色。插入的节点2为红色。因为2比1大，因此插入到1的右孩子节点。没有出现连续红色节点的时候，就正常插入节点即可。只有出现连续的红色节点时，才需要通过旋转或者变色建立红黑树。因此，红黑树的建立过程，就是解决连续红色节点的过程。

3）输入3。新插入节点为红色，且3比2大，因此插入到2的右孩子节点。此时，需要解决右右连续红色节点（节点2，3为连续的右右红色节点）问题。

解决思路为：父节点2没有兄弟节点，通过先旋转，再变色解决。以2为中心节点，进行左旋，变为下图2。然后节点2和自己的左孩子节点1交换颜色。

4）输入4。新插入节点为红色。且比3大，因此插入到3的右孩子节点，下图1。此时，需要解决右右连续红色节点（节点3，4）的问题。

解决思路为：父节点3有兄弟节点1，且与3颜色相同，则直接通过变色解决。即，父节点3和其兄弟节点1变为黑色，祖父节点变为红色（这里有两次变色：父节点和其兄弟先变色，然后祖父节点变色）。变色之后，成为下图2。成为图2后，发现根节点不是红色了，根据红黑树的三黑性质之一：根节点为黑色。将根节点变为黑色。

5）输入5。新插入节点为红色。且比4大，因此插入到5的右孩子节点。此时，需要解决右右连续红色节点的问题。

解决思路为：父节点4没有兄弟节点，通过先旋转，再变色解决。以父节点4为中心节点，进行左旋，得到下图2。然后父节点4与左孩子3交换颜色，得到下图3。

注意：此时，此时可以发现规律1。我们看到下图1中的节点3-4-5，与上述3）中的情况一致，且解决方法完全一致。即：先以父节点为中心，进行左旋转，然后交换父节点与左孩子节点的颜色。

6）输入6。新插入节点为红色。且比5大。因此插入到5的右孩子节点。此时，需要解决右右连续红色节点的问题。

解决思路为：父节点5有兄弟节点3，且与5颜色相同，则直接通过变色解决。即，父节点3和其兄弟节点1变为黑色，祖父节点变为红色（这里有两次变色：父节点和其兄弟先变色，然后祖父节点变色）。

注意：此时，可以总结出规律2。我们看到下图1中的节点4-5-6，与上述4）中图1的2-3-4一致，且解决方法完全一致。即：父节点和它的兄弟先变色，然后祖父节点再变色。

7）输入7。新插入节点为红色。且比6大。因此插入到6的右孩子节点。此时，需要解决右右连续红色节点的问题。

解决思路为：父节点6没有兄弟节点。所以通过旋转，变色。以父节点6为中心节点，进行左旋，然后父节点6与左孩子交换颜色。（与输入输入3和输入5的处理思路完全一致）

8）输入8。新插入节点为红色。且比7大。因此插入到7的右孩子节点。此时，需要解决右右连续红色节点的问题。

解决思路为：父节点7有兄弟节点。且颜色相同，因此通过变色即可解决。（与步骤4，6的思路一致。只不过步骤4多了一步，将根节点变为黑色）。变色之后，发现，依然出现了连续红色节点4和6。

解决思路为：6的父节点4有兄弟节点1，但是颜色不一致。此时需要做的是：以父节点4为中心节点，进行左旋，得到下图3；然后将父节点4与其左孩子节点2进行换色，得到下图4。

注意：此时，我们遇到了一种新的情况，就是父节点有兄弟节点，但是兄弟节点与其颜色不同。但是从解决方法可以看到，解决方法和父节点没有兄弟节点的方法完全一致。即：先以父节点为中心，进行左旋转，然后交换父节点与左孩子节点的颜色。

9）输入9。新插入节点为红色。且比8大。因此插入到8的右孩子节点。此时，需要解决右右连续红色节点的问题。

解决思路为：父节点8没有兄弟节点。所以通过先旋转，再变色。以父节点8为中心节点，进行左旋，然后父节点8与左孩子7交换颜色。

10）输入10。新插入节点为红色。且比9大。因此插入到9的右孩子节点。此时，需要解决右右连续红色节点的问题。

解决思路为：父节点9有兄弟节点。且颜色相同，因此通过变色即可解决。此时，发现依然存在连续的6和8是红节点。

解决思路为：父节点6有兄弟节点，且颜色相同，则通过变色解决解决。父节点6与其兄弟节点4均变为黑色，然后祖父节点变为红色。因根节点必须为黑色，所以根节点4变为黑色。

通过上述例子，在解决连续红色节点的过程中，我们总结了三条规律：

1）如果父节点有同色的兄弟节点，则通过两次变色解决连续红色节点问题：父节点和其兄弟先变色；祖父节点再变色。

2）如果父节点有不同色的兄弟节点，则通过先旋转，再变色解决连续红色节点问题：先以父节点为中心节点左旋；然后父节点与其左孩子交换颜色。

3）如果父节点没有兄弟节点，则假设其有一个黑色兄弟。按照上述2）进行处理。（其实如果将所有的null节点标注出来的话，就不存没有兄弟节点的节点。null节点的作用就是将红黑树变为满二叉树）

最后，需要注意红黑树的特性之一：根节点必须为黑色。下面给出例子2。通过例子2，我们会发现，依然可以总结出上述总结的三条规律。

例子2、解决连续左左红色节点

假设初始序列为：10，9，8，7，6，5，4，3，2，1。共10个数字，顺序输入，建立一棵红黑树。

1）输入10。根节点，为黑色。红黑树性质中的三黑之一：根节点为黑色。

2）输入9。插入节点9为红色，且比10小，所以插入到左孩子。没有出现连续红色节点的时候，就正常插入节点即可。只有出现连续的红色节点时，才需要通过旋转或者变色建立红黑树。因此，红黑树的建立过程，就是解决连续红色节点的过程。

3）输入8。插入节点8为红色，且比9小，所以插入到左孩子。出现了连续红色左左节点。解决思路参考例子1中，总结的规律2和3，只是将其中的左旋变为右旋，并与右孩子交换颜色。

解决思路：父节点9没有兄弟节点，根据规律3，假设有黑色兄弟节点。两兄弟的颜色不一致，根据规律2，则通过先旋转，再变色的方法。以父节点9为中心节点，右旋；然后再与其右孩子10交换颜色。

4）输入7。插入节点7为红色，且比8小，所以插入到左孩子。出现了连续红色左左节点。解决思路参考例子1中，总结的规律1。通过两次变色，即可解决。

解决思路：父节点8有兄弟节点。且颜色相同，根据规律1，直接通过两次变色即可解决。父节点及其兄弟变为黑色，祖父节点变为红色。此时根节点为红色，再将根节点9变为黑色。

5）输入6。插入节点6为红色，且比7小，所以插入到左孩子。出现了连续红色左左节点。解决思路参考例子1中，总结的规律2和3，只是将其中的左旋变为右旋，并与右孩子交换颜色。

解决思路：父节点7没有兄弟节点，则假设有黑色兄弟。通过先旋转，再变色解决。以父节点7为中心节点，右旋。然后父节点7与其右孩子节点8交换颜色。

6）输入5。插入节点5为红色，且比6小，所以插入到左孩子。出现了连续红色左左节点。解决思路参考例子1中，总结的规律1。通过两次变色，即可解决。

解决思路：父节点6有兄弟节点，则直接通过两次变色即可解决。父节点6与其兄弟8变为黑色，祖父节点7变为红色。

7）输入4。插入节点4为红色，且比5小，所以插入到左孩子。出现了连续红色左左节点。解决思路参考例子1中，总结的规律2和3，只是将其中的左旋变为右旋，并与右孩子交换颜色。

解决思路：父节点5没有兄弟节点，则假设有黑色兄弟。通过先旋转，再变色解决。以父节点5为中心节点，右旋；然后父节点5与其右孩子6交换颜色。

8）输入3。插入节点3为红色，且比4小，所以插入到左孩子。出现了连续红色左左节点。

解决思路：父节点4有相同颜色的兄弟节点。则直接通过两次变色解决。此时，变色后，依然存在连续红色的节点7和5。则继续按照总结的规律解决。

解决思路：父节点7有黑色兄弟节点。则通过先旋转，再变色解决。即，以父节点7为中心节点，进行右旋，然后交换父节点7与其右孩子的颜色。

9）输入2。插入节点2为红色，且比3小，所以插入到左孩子。出现了连续红色左左节点。

解决思路：父节点3没有兄弟节点。假设存在黑色兄弟节点。则父节点存在与其颜色不同的兄弟节点，通过先旋转，再变色的方法解决。以父节点3为中心节点，进行右旋，然后父节点3与其右孩子交换颜色。

10）输入1。插入节点1为红色，且比2小，所以插入到左孩子。出现了连续红色左左节点。

解决思路：父节点2有同色的兄弟节点，则直接通过变色解决。父节点2和他的兄弟变为黑色，祖父节点变为红色。此时，变色后，还存在连续红色节点5和3。继续按照总结的规律处理。

解决思路：父节点5有同色的兄弟节点，则直接通过变色解决。父节点5和他的兄弟变为黑色，祖父节点变为红丝。此时，根节点不为黑色，再将根节点变为黑色。结束。

通过上述例子，在解决连续左左红色节点的过程中，我们可以将例子1中总结的三条规律稍微进化一下：

1）如果父节点有同色的兄弟节点，则通过两次变色解决连续红色节点问题：父节点和其兄弟先变色；祖父节点再变色。

2）如果父节点有不同色的兄弟节点，则通过先旋转，再变色解决连续红色节点问题：先以父节点为中心节点左/右旋；然后父节点与其左/右孩子交换颜色。

3）如果父节点没有兄弟节点，则假设其有一个黑色兄弟。按照上述2）进行处理。（其实如果将所有的null节点标注出来的话，就不存没有兄弟节点的节点。null节点的作用就是将红黑树变为满二叉树）

最后，需要注意红黑树的特性之一：根节点必须为黑色。

通过上述两个例子，实际总结出两条处理连续红色节点的规律：1、两次变色。2、先旋转，再变色。下面的例子3和例子4中，其实也是应用这两条规律。建议自己推理例子3和例子4中的红黑树建立过程。

例子3、解决连续右左红色节点

例子4、解决连续左右红色节点

如果觉得《红黑树系列1——红黑树的建立》对你有帮助，请点赞、收藏，并留下你的观点哦！