要学习红黑二叉树，就得先了解二叉树是什么，二叉树是有限个元素得集合,这些元素集合构成树，二叉树允许集合元素个数为0，此时他就是一个空树，对于元素个数大于0的二叉树，它会有一个根节点，剩下下的元素被组成 2个二叉树，分别称为左子树和右子树。二叉树它满足以下两个条件：

1.每个结点他最多有两个子结点

 2、左子节点一定是小于或等于其父节点，右子结点一定是大于或等于其父结点的

对于一系列元素来说，构成一个二叉树，它的形式是多样的 ，只要满足上面条件即可，那么它可能构成一个完整的二叉树，即各个结点和其子节点都存在，也或者它会完全是一个线性的，即根节点是最小值，其左子树为空且树中不存在左子节点 。前者是最优的方案，获取元素平均搜索次数也是最少的，后者和链表是一样的，平均搜索次数是最多的，如果是最后一个值，则需要将整个树的节点都过一遍，无疑这种方式是最耗时的。

为了保证元素在形成树时不会出现后者的这种情况，在原先二叉树的基础上增加了一些条件限制，来对元素的插入或删除时保持树的饱和。红黑二叉树是其中一种，红黑二叉树中对每个结点元素新增了颜色的属性，非黑即红。红黑二叉树不仅要满足二叉树的定义，以下几个条件也需要其满足：

（1）每个节点或者是黑色，或者是红色。

（2）根节点是黑色。

（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]

（4）如果一个节点是红色的，则它的子节点必须是黑色的，也就是说不可能出现两个连续的红色节点，不过两个连续的黑色节点是可能出现的

（5）从任意一个节点到该节点的叶子节点的所有路径上包含相同数目的黑节点。

在构建一个红黑树时，不管是新插入元素还是删除元素都有可能破坏4、5限制条件，所以在我们新增或删除元素节点时，我们需要操作树中的结点，让其结点颜色属性满足4、5限制条件。

新插入的元素结点一定是在红黑树的最低端的，且插入的元素初始颜色属性为红色(为红色在有的情况下不需要调整原树的颜色属性)；

了解一下左旋和有旋的概念，后面会用到

左旋

右旋

截的别人的图片，感觉很直观；

在我们插入一个新的元素结点时，我们会遍历树，找到新增结点的插入位置(和二叉树的插入是相同的)，插入元素后默认颜色为红色，我们对树做红黑树的限制校验，如果不满足，我们就需要调整树的结点颜色或通过上面说的左旋和右旋来调整结点位置来保证红黑树限制成立，主要有下面的情况

1、新增元素结点是根结点，设置该结点元素为黑色，满足限制条件(2);

2、父结点为黑色，插入结点后不做任何调整（插入结点为红色，满足条件4 ，原先经过父结点的最短简单路径的黑色结点树没有减少或增加，满足条件5，所以不需修改）

3、父结点是红色，此时父节点的兄弟结点(也叫叔叔结点)也是红色，此时爷爷结点一定是黑色的(条件4)，这种情况由于新增的结点为红色，不满足条件4，此时需要做调整，将父结点和叔叔结点同时变为黑色，此时经过父结点和叔叔结点的简单路径多了一个黑色结点，不满足条件5，经过父结点和叔叔结点的简单路径肯定经过爷爷结点，且经过爷爷结点的也只有父结点和叔叔结点，所以将爷爷结点变成红色，这样所有简单路径上的黑色结点个数又一致了；此时其实情况又回到了新增结点的最初情况，只不过现在需要判断红黑树限制的结点变成了爷爷结点，将爷爷结点(此时是红色)看做新增结点递归处理

4、父结点是红色，此时叔叔结点是黑色，此时爷爷结点一定也是黑色的(条件4) ，此时情况稍微多点，需要用到左旋和右旋的操作；

情况1、新增红色结点是父结点的左孩子，且父结点也是爷爷的左孩子，此时，不满足条件4，新增结点和父结点都为红色，将父结点修改为黑色，条件4满足，经过父结点的简单路径增加了一个黑色结点，不满足条件5；对爷爷结点做右旋处理，父结点移至爷爷结点变成爷爷结点，爷爷结点移至叔叔结点变成叔叔结点，新增结点移至父结点变成父结点(在树结构中的位置发生变化，我们对其的命名也发生变化，防止后续描述发生歧义)。此时经过爷爷结点的左子树简单路径黑色结点个数减少一个，右子树却新增了一个，将叔叔结点（原爷爷结点元素）变红色，此时叔叔结点的父结点是黑色的，两个子结点也是黑色的，将其变成红色，不违反条件4，又能平衡简单路径的黑色结点树，满足条件5 。

情况2、新增红色结点是父结点的右孩子，且父结点是爷爷结点的左孩子，此时，不满足条件4，新增结点和父结点都为红色。将父结点做左旋处理，就变成了情况1，继续按照情况1的处理方式去调整。

情况3、新增红色结点是父结点的右孩子，且父结点也是爷爷结点的右孩子，此时，不满足条件4，新增结点和父结点都为红色，将父结点修改为黑色，条件4满足，经过父结点的简单路径增加一个黑色结点，不满足条件5；对爷爷结点做左旋处理，父结点移至爷爷结点变成爷爷结点，爷爷结点移至叔叔结点变成叔叔结点，新增结点移至父结点变成父结点(在树结构中的位置发生变化，我们对其的命名也发生变化，防止后续描述发生歧义)。此时经过爷爷结点的右子树简单路径黑色结点个数减少一个，右子树却新增了一个，将叔叔结点（原爷爷结点元素）变红色，此时叔叔结点的父结点是黑色的，两个子结点也是黑色的，将其变成红色，不违反条件4，又能平衡简单路径的黑色结点树，满足条件5 。

情况4、新增红色结点是父结点的左孩子，且父结点是爷爷结点的右孩子，此时，不满足条件4，新增结点和父结点都为红色。将父结点做右旋处理，就变成了情况3，继续按照情况3的处理方式去调整；

以上是红黑树新增结点的处理。

下面来理一理删除：

什么叫后继结点 ：后继节点一共有两种情况，一种情况是当前节点有右子树，那么当前节点的后继节点一定在它的右子树上，在右子树的最左边 ，即为右子树的最小值；第二种情况是，当前结点没有右子树，那么就依次往上找，找到一种情况是当前节点是它的父亲节点的左孩子的时候，那么这个父亲节点就是我原始节点的后继节点

红黑树的删除会有以下情况 

1、删除的结点无子结点

2、删除的结点只有左子树或右子树

3、删除的结点左右子树都存在

针对第3种情况，如果左右子树都存在的话，我们会寻找删除结点的后继结点，然后将后继结点的值赋给删除结点，再将后继结点删除，这种情况下的后继结点即为删除结点的右子树的最左边；实际上就是变成了删除后继结点，又变成了第一二种情况，所以实际上就有这两种情况了。

情况1 、 删除的结点无子结点；

        1.1  、删除结点为红色   ，直接删除即可，因为是红色结点，所以不影响红黑树的4和5条件；

        1.2 、删除结点为黑色且为左孩子，兄弟结点为红色，此时父结点为黑色，根据红黑树的性质，兄弟结点的左结点SL和右结点SR都为黑色且不能为空，删除后，父结点修改为红色，兄弟结点修改为黑色，对父结点做左旋处理，SL结点变成了原父结点的右孩子(黑色)，原父结点左孩子为空孩子，此条路径会少一个黑色结点，不满足条件5，再对原父结点做左旋处理，SL结点替代原父结点位置即可。

        1.3、删除结点为黑色且为左孩子，兄弟结点为黑色

                1、兄弟结点左孩子SL为红色时 ，删除结点后，左子树减少一个黑色，需要左结点新增个黑色结点，兄弟结点右旋，SL结点代替兄弟结点，将SL修改为父结点的颜色，父节点修改为黑色，对父结点左旋，此时，左子树新增了一个黑色结点，右子树的黑色结点树不变。

                2、兄弟结点右孩子SR为红色时 ，删除结点后，左子树减少一个黑色，需要左结点新增个黑色结点，将兄弟结点由黑色改为父结点的颜色，将SR由红色改为黑色，将父节点的颜色改为黑色，再将父节点左旋转；此时，左子树新增了一个黑色结点，右子树的黑色结点树不变。

                3、兄弟结点的两个孩子都为黑色，父结点为红色，删除结点后，左子树减少一个黑色，需要左结点路径新增个黑色结点，     父结点修改为黑色，再将兄弟结点修改为红色即可。

                4、兄弟结点的两个孩子都为黑色，父结点为黑，删除结点后，左子树减少一个黑色，此种情况下无法通过修改结点颜色属性和旋转来达到左子树增加黑色结点的目的，所以只能将兄弟结点改为红色，将左右子数经过黑色结点树都减1，在对父结点左迭代处理，

        1.4、删除结点为黑色且为右孩子，兄弟结点为红色，此时父结点为黑色，根据红黑树的性质，兄弟结点的左结点SL和右结点SR都为黑色且不能为空，删除后，父结点修改为红色，兄弟结点修改为黑色，对父结点做右旋处理，SR结点变成了原父结点的左孩子(黑色)，原父结点右孩子为空孩子，此条路径会少一个黑色结点，不满足条件5，再对原父结点做右旋处理，SR结点替代原父结点位置即可。

    1.5  删除结点为黑色且为右孩子，兄弟结点为黑色

         1、兄弟结点左孩子SR为红色时 ，删除结点后，右子树减少一个黑色，需右结点新增个黑色结点，兄弟结点左旋，SR结点代替兄弟结点，将SR修改为父结点的颜色，父节点修改为黑色，对父结点右旋，此时，右子树新增了一个黑色结点，左子树的黑色结点树不变。

                2、兄弟结点左孩子SL为红色时 ，删除结点后，右子树减少一个黑色，需要右结点新增个黑色结点，将兄弟结点由黑色改为父结点的颜色，将SL由红色改为黑色，将父节点的颜色改为黑色，再将父结点节点右旋转；此时，左子树新增了一个黑色结点，右子树的黑色结点树不变。

            3、兄弟结点的两个孩子都为黑色，父结点为红色，删除结点后，右子树减少一个黑色，需要左结点路径新增个黑色结点，     父结点修改为黑色，再将兄弟结点修改为红色即可。

              4、兄弟结点的两个孩子都为黑色，父结点为黑，删除结点后，右子树减少一个黑色，此种情况下无法通过修改结点颜色属性和旋转来达到右子树增加黑色结点的目的，所以只能将兄弟结点改为红色，将左右子数经过黑色结点树都减1，在对父结点做迭代处理；

1.4和1.5情况差不多，只是做左旋右旋的选择不同

情况2、删除的结点只有一个子结点；

        2.1、删除的结点为红色，用子结点替换掉该要删除的结点，因为是红色结点，所以不影响红黑树的4和5条件；

        2.2 、删除的结点为黑色，用子结点替换掉该要删除的结点，如果子结点为红色时，修改子结点颜色为红色；

        2.3  删除的结点为黑色，用子结点替换掉该要删除的结点，子结点为黑色，处理情况和情况1的1.2、1.3、1.4、1.5情况类似。