为什么会有红黑树？

二叉搜索树是一个很不错的数据结构，正常情况下可以很快速的查找，删除和添加元素，但是在某些情况下它会变得很糟糕，比如，插入的元素是有序的，那么二叉搜索树就变成了只有左子树或者只有右子树的怪物，实际上就变成了链表结构，像这种平衡度很差的搜索二叉树的执行效率就变得很差。

为了能高效的搜索一颗二叉搜索树，就要保证树本身是平衡的(或者大致平衡)，这里的平衡说的是树的左边的后代数目和右边的后代数目大致相同。而我们要说的红黑树就是这样的平衡二叉树。

对于每一个要插入的节点，红黑树的插入程序都会检查会不会破坏树的特征结构，如果结构被破坏了，程序就会修正，根据需要改变树的结构，来保证树的平衡。

红黑树的特质

1.红黑树的每个节点不是红色就是黑色(其实就是一个标志位而已)
2.根节点一定是黑色的
3.如果节点是红色的，那么它的子节点必须是黑色的, 反之则不一定
4.从根节点到叶子节点的每条路径上，必须包含相同数目的黑色节点

为什么插入的节点总是红色的？

在红黑树中新插入的节点总是红色的，这不是随随便便拍大腿决定的；因为插入黑色节点一定会违背红黑树特质[4]（因为一条路径上多了一个黑色节点），而插入红色节点则只有一半的机会违背红黑树特质[3] （如果新节点的父节点是红色，就违背了特质[3]），并且先人们说了，违背特质[3]比违背特质[4]更容易修正。

节点之间的关系

在开始下面的内容之前，我们要先明白节点和节点之间的关系，因为后面的内容中会用到这些关系术语，这里，我们用一张图来表示:

节点关系图

这里，以节点[12]为例子，它的一些长辈和晚辈如下：
1.左孩子和右孩子: [11]和[13]
2.兄弟: [18]
3.近侄子: [16]; 远侄子: [19]; 这里的远近相信大家能判断出来。比如[18]的近侄子就是[13]，远侄子就是[11]
4.父亲: [14]
5.叔叔: [2]
6.祖父: [10]

红黑树的平衡性修正

红黑树平衡性修正的方法只有三种：变色、左旋和右旋

1.变色
变色很简单，其实主要是新插入的红色节点的父节点是红色节点（违背了红色节点的子节点必须是黑色节点的特质），只需要修改父节点的颜色即可

2.左旋 && 右旋
例如，有这样一棵树，我们以节点[2]为支点进行左旋：

左旋
过程是这样的：1.将节点[7]的左孩子[5]转接到节点[2]的右孩子上；2.将节点[2]的父节点[11]变成节点[7]的父节点；3. 将节点[2]转接到节点[7]的左孩子上
右旋则正好相反，比如：以节点[7]为支点进行右旋：

右旋
过程是这样的：1.将节点[2]的右节点[5]转接到节点[7]的左孩子上；2.将节点[7]的父节点[11]变成节点[2]的父节点；3.将节点[7]转接到节点[2]的右孩子上。
这里对红黑树进行左旋和右旋的原因，主要是为了调整红黑树的平衡度

红-黑树的插入图解

红黑树的插入可以分解为这么几个步骤：

1：插入的是第一个节点，直接设为根节点，变成黑色即可，不需要修正
2：插入节点的父节点是黑色的（因为插入的红色节点不违背每条路径上黑色节点数相同这一特质），不需要修正
3：插入节点的父节点是红色；（因为插入的红色节点违背了红色节点下必须是黑色节点这一特质），所以这种情况都需要修正
3.1：叔叔节点是红色；修正过程如下:
1. 将父节点和叔叔节点变黑
2.将祖父节点变红 *
3.将祖父节点设为当前节点，然后对新的当前节点重新修正
3.2：叔叔节点是黑色；又分下面几种情况
3.2.1：当前节点是父亲的左孩子，父亲是祖父的左孩子；修正过程如下:
1.以祖父为支点右旋 *
2.交换父亲和祖父的颜色
3.2.2: 当前节点是父亲的右孩子，父亲是祖父的左孩子；修正过程如下:
1.以父亲为支点左旋 *
2.将父亲设为当前节点重新修正*
3.2.3: 当前节点是父亲的右孩子，父亲是祖父的右孩子；修正过程如下:
1.以祖父为支点左旋 *
2.交换父亲和祖父的颜色*
3.2.4: 当前节点是父亲的左孩子，父亲是祖父的右孩子
1.以父亲为支点右旋 *
2.将父亲设为当前节点重新修正*

下面我们用图形来展示下插入的修正过程：

插入修正过程

这里展示了绝大部分的情况，只要按照每种情况下的修正原则来修正就可以了。

红黑树的删除图解

删除节点这里要分两部分来处理

1. 节点交换

如果直接将节点在原位置删除的话，需要考虑删除节点的左右子树的嫁接问题，有点麻烦；另外一种方法是将要删除的节点和它的最小后继或者最大前继交换，然后再删除，本章节中，我们采用交换最小后继的方式，比如，下面这样：

交换最小后继

注意，这里交换的只是节点的值，不要交换节点的颜色；另外，交换的话还有几种情况，我们要把要删除的节点一直交换到叶子节点为止，所以要循环去交换直到完成。

情况1. 当前节点没有孩子，是叶子节点
1. 节点是红色的，直接删除即可
2. 节点是黑色的，删除后违背红黑树特质，需要做后面的变色旋转修正处理，然后再删除
情况2. 当前节点有两个孩子节点；
则从后继节点中找到最小后继D, 交换当前节点和节点D的值，然后把原节点D作为当前节点重新走交换节点流程
情况3. 当前节点只有左孩子L；
交换当前节点和L节点的值，然后把原L节点作为当前节点重新走交换节点流程
情况4. 当前节点只有右孩子R；
交换当前节点和R节点的值，让后把原R节点作为当前节点重新走交换节点流程

经过上面的处理，我们就把要删除的节点移位到了叶子节点；剩下要做的就是处理情况1中的第2种情况中的变色旋转了

2. 变色旋转

为了后续方便，我们用下面的简称来代表节点之间的关系 (节点之间的关系我们在上面已经描述过了，不记得的可以往上翻一翻):
P: 当前节点的父节点
W: 当前节点的兄弟节点
Nf: 当前节点的远侄子
Nn: 当前节点的近侄子

情况1:当前节点是根节点或者是红色节点
直接将其变成黑色，变色旋转结束；
情况2:W是红色
则将W设为黑色，P设为红色，对P进行旋转(当前节点是P的左节点时，左旋，当前节点是P的右节点时右旋);然后再重新进行旋转变色
情况3:W是黑色，且它的两个孩子也是黑色
则将w设为红色，将P设为当前节点，重新进行旋转变色
情况4:W是黑色，Nf是红色
则将W设为P的颜色，P和Nf设为黑色，并对P进行旋转(当前节点是P的左孩子就左旋，是右孩子就右旋)，变色旋转结束；
情况4:W是黑色，Nf是黑色
则交换W和Nn的颜色，并对W进行旋转(当前节点是P的左孩子则右旋，是右孩子则左旋)，然后重新进行旋转变色；

下面是一个删除示例：