红黑树系列1——红黑树的建立_红黑树的建立过程

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

红黑树系列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的右孩子节点。此时，需要解决右右连续红色节点的问题。<