红黑树是一种自平衡二叉搜索树。二叉搜索树就是插入的时候，比当前节点小的放到左子树，大的放到右子树。这样查找的时候可以沿着树的一条路径找到想要的值，所以时间复杂度是树的深度，最坏$O(N)$，平均$O(lg^N)$。
正因为二叉搜索树由于数据的不确定性可能造成树建的不平衡，导致树过深，时间复杂度过高。所以出现了自平衡二叉搜索树像红黑树。
红黑树所有的性质和特点都是想让树尽可能的平衡。
1. 性质
- 每个节点或是红色，或是黑色
- 根结点是黑色
- 每个叶节点(NIL)是黑色
- 如果一个节点是红色，则它两个子节点必须是黑色
- 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点
另外其他二叉树叶子结点一般为nil，红黑树为了节省内存空间，将所有叶子节点指向一个哨兵节点，哨兵节点color为BLACK，其他属性p、left、right、key为任意值，根结点的父节点也指向哨兵节点。
2. 为什么红黑树可以平衡
2.1 引理
一棵有n个内部节点的红黑树的高度至多为$2lg^{(n+1)}$
如果可以证明上述引理，那么红黑树的查找最坏的时间复杂度也是$O(2lg^{(n+1)})$，因为在一棵高度为h的树上操作时间复杂度是$O(h)$，就是咱们要的平衡。
2.2 证明
首先证明红黑树以任意一个节点x为根的子树中至少包含$2^{bh(x)}-1$个内部节点(从节点x出发，不包含x到达一个叶子节点的任意一条简单路径上黑节点的个数成为x节点的黑高，记为$bh(x)$)。
下面用数学归纳法证明
-
当高度为0时 即子树为空，满足内部节点不超过$2^{0}-1=0$的要求。
-
当高度为k时 假设以x为根的子树内部节点不超过$2^{bh(x)}-1$。
-
当高度为k-1时 即当前节点是x(这个x节点是高度为k时假设的那个)的儿子，黑高为$bh(x)$或$bh(x)-1$，取决于儿子是黑还是红。所以以儿子节点为根的子树至少有$2^{bh(x)-1}-1$内部节点。于是，由儿子节点推父节点x内部节点的个数不超过$(2^{bh(x)-1}-1)+(2^{bh(x)-1}-1)=(2^{bh(x)}-1)$，由此假设成立。
现在来证明引理。设h为树的高度，根据性质4得出从根节点到叶节点的任何一条简单路径上都至少有一半节点是黑色，所以根的黑高至少时h/2。于是有
n为树的节点个数，这个公式上边证明过了。将1放到左边，然后取对数得到
由此得到结论，高度小于等于$2lg^{(n+1)}$，所以只要满足红黑树性质的n节点二叉树高度最大为$2lg^{(n+1)}$。
3. 红黑树如何实现自平衡
3.1 旋转
由于插入和删除操作会对红黑树修改，有可能会不符合红黑树的性质，所以必须通过调整节点的颜色和指针结构来重新满足性质，而调整指针结构的操作是旋转，有左旋、右旋。 下图α,β,γ代表一棵子树(可能为空)
3.1.1 左旋
上图为例，左旋就是从右边树结构变成左边树结构的操作。 当在某点例如x点做左旋时:
- 以x-y这条路径当轴，逆时针旋转(左旋)，x变成y的左儿子，y到原来x的位置。
- 因为x变成了y的左儿子，所以要考虑y之前是否有左儿子，如果有的话就要将左儿子β在左子树中重新找位置了，之前β是在x的右边所以比x大，刚好x的右儿子旋转后是空的，所以β就放到x的右儿子的位置。就得到了左边树的结构。
3.1.2 右旋
和左旋步骤是一样的，方向相反。
3.2 插入
- 插入节点颜色设置为红色。
- 首先从根结点开始遍历，插入节点比当前节点小就去左子树，否则就去右子树，直到遍历到叶子结点，然后比较插入节点和父节点大小选择作为父节点的左儿子还是右儿子。
- 现在已经将节点插入了，由于插入节点颜色是红色，所以可能破坏红节点儿子只能是黑节点的性质。所以从插入节点向上遍历修复破坏性质的地方，直到完全符合性质。
3.2.1 修复
回想一下插入新节点的过程，然后对比一下可能违反什么性质。
| 性质编号 | 描述 | 是否可能违反 |
|---|---|---|
| 1 | 每个节点或是红色，或是黑色 | 不会违反，除非插入第三种颜色 |
| 2 | 根结点是黑色 | 可能违反，只有树为空的时候，插入节点(红色)作为根结点 |
| 3 | 每个叶节点(NIL)是黑色 | 不会违反，插入节点不会改变叶节点的颜色，叶节点永远都是T.nil |
| 4 | 如果一个节点是红色，则它两个子节点必须是黑色 | 可能违反，只有插入节点的父节点是红色时，会违反这条性质 |
| 5 | 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点 | 不会违反，插入节点为红色，不会改变每条路径上黑色的数量 |
对比过后发现，可能违反的性质有2、4。并且同一时间只可能违反其一，如果违反性质2，说明树为空插入节点为根结点，根结点的父节点是T.nil(黑色)不违反性质4。如果违反性质4，那么插入节点的父节点一定是红色，说明树一定不是空的(为空的话，插入节点的父节点应该是T.nil黑色)，并且只有树为空的情况插入才会影响根结点颜色，所以也不可能违反性质2。
现在可能破坏的地方分析清楚了，就可以开始梳理如何修复了，并且修复操作不能造成二次破坏导致不符合其他性质。
-
违反性质1 只需要把根结点直接设置为黑色即可。因为违反性质1的时候，树中只有插入节点一个节点，所以修复结束。
-
违反性质4 违反性质4是因为插入节点和父节点都是红色，情况比较复杂，具体分6类。从插入节点往上遍历，针对不同的case采取不同的fix方式，直到父节点是黑色或者到根结点即停止遍历。 指针指向的位置初始时在插入位置
3.2.1.1 case 1
1.入节点是父节点是祖父节点的左儿子 2.入节点叔节点是红色 (z是插入节点，p是父节点，u是叔节点，g是祖父节点)
这种情况将父节点和叔节点变为黑色，祖父节点变为红色，指针指向祖父节点(上移两层)然后继续判断。
这一步祖父节点可能是根结点，所以在修复完违反性质4的情况之后，再把根结点设置为黑色，避免再违反性质1
3.2.1.2 case 2
1.插入节点是父节点是祖父节点的左儿子 2.插入节点叔节点是黑色 3.插入节点是父节点右儿子 (z是插入节点，b是兄弟节点，p是父节点，u是叔节点，g是祖父节点)
关于父节点做左旋，就可以变为case 3。
3.2.1.3 case 3
1.插入节点是父节点是祖父节点的左儿子 2.插入节点叔节点是黑色 3.插入节点是父节点左儿子 (z是插入节点，b是兄弟节点，p是父节点，u是叔节点，g是祖父节点)
将父节点变为黑色，祖父节点变为红色，然后关于祖父节点做右旋得到下图(关系还是按照旋转前定的)
case3修复之后，看上图，就没有可能违反性质的地方了，修复结束。
case 4,5,6是插入节点的父节点是父节点右儿子的情况，和前三种对称，这里就略过了。
3.2.2 插入节点为什么设置为红色?
如果设置为黑色的话，会破坏每点到叶节点简单路径上黑色节点数量相同的性质了，修复起来情况就复杂了，相比之下就比如直接设置为红色。
3.2.3 小结
到现在插入步骤已经清晰了:
- 按照普通二叉树插入方式插入节点
- 从插入节点开始往上看看有没有违反性质的地方，只有父节点是红色的情况会违反性质4(违反性质2的情况不要考虑，只需要在修复结束时，强制把根节点设为黑色即可)
- 遇到父节点是红色的情况就需要修复了(以下情况都假设插入节点的父节点是祖父节点的左儿子，右儿子的情况修复方式相反)
- 叔节点是红色的(case 1), 就把父节点和叔节点都变为黑色，祖父节点变为红色，然后指针指向祖父节点继续向上遍历，直到根节点或者指针的父节点是黑色就结束。
- 叔节点是黑色，插入节点是父节点右儿子(case 2)，关于父节点做个左旋变成case 3
- 叔节点是黑色，插入节点是父节点左儿子(case 3)，父节点变为黑色，祖父变红色，然后关于祖父节点做右旋，修复结束。
大概就是，遇到case 1把错误交给上层，然后一层层遍历上去。遇到case 2变为case 3，case 3可以直接修复。
所以插入及修复只是在二叉树的一条路径上操作，时间复杂度是$O(lg^N)$。
3.3 删除
删除和普通的搜索二叉树的删除差不多，唯一的不同就是要记录减少的颜色，因为可能破坏红黑树的性质。
初始情况下y指向z z为要删除节点，p为父节点，l为z左儿子，r为z右儿子
- z没有子节点
直接删除z，z的父节点的儿子指向T.nil。
- z只有右儿子
将z的右子树提到z的位置。
- z只有左儿子
将z的左子树提到z的位置。
- z有两个儿子
找到后继节点y(比z大的最小的那个)，用y替换z的位置，颜色设置为z的颜色，这样y原来的位置就空了，将y的右子树x(如果有)提到y原来的位置。
3.3.1 修复解析
y: 代表要z或者z的后继节点(case 4) x: 代表不违反性质的最低节点(x往下就没操作过，要修复的话，从x向上遍历修复) case 1: x为nil case 2,3: x为z的唯一的那个儿子(因为儿子子树内部没变过，只需要修复往上) case 4: x为z后继的右儿子
删除操作完成之后，相当于少了y指向节点的颜色，所以只要y是黑色节点，就会产生违反性质的情况。
- 如果y是根结点，删除y后，如果提到y位置节点颜色是红色就违反了性质2。(性质2最好修复，所有修复操作完成后直接把根变为黑色就行)
- 如果x是红色，并且x的父节点也是红色，就违反性质4。
- 因为y是黑色节点，所以删掉后经过y的路径上黑色节点都少1就违反性质5了，解决这个问题的办法是假设x除了自身颜色外还有一层黑色，就是双重颜色，所以现在x违反性质1。
| 性质编号 | 描述 | 是否可能违反 |
|---|---|---|
| 1 | 每个节点或是红色，或是黑色 | 可能违反，x有双重颜色时违反 |
| 2 | 根结点是黑色 | 可能违反，y是根结点，并且后续一个红色节点代替了上来，那么根节点就是红色 |
| 3 | 每个叶节点(NIL)是黑色 | 不会违反 |
| 4 | 如果一个节点是红色，则它两个子节点必须是黑色 | 可能违反，情况4(两个儿子)，后继节点的父亲是红色，右儿子是红色，那么右儿子提上来之后就父子都是红色 |
| 5 | 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点 | 不会违反 |
现在可能违反的性质有1，2，4
3.3.2 修复策略
因为删除操作后，红黑树少了一个黑色，所以把这个黑色放在x，x变为双重颜色(下图用紫色表示)。
- 如果x原来是红色，刚好将x变为黑色，修复完成。
- 如果x原来是黑色，那么x为双重黑色，下面就是剖析如果修复x的双重黑色。
修复是从x向上遍历，因为x为根的子树没有做过操作(删除操作的时候记录下来)，所以不会违反性质。修复策略分为四种情况:(以下情况都是x为父节点左儿子的情况，右儿子的情况相反而已)
3.3.2.1 case 1
x的兄弟节点w是红色
此时: 1) 因为w是红色，所以p是黑色。 2) 因为x是双重黑色，所以w一定有儿子且w的子节点是黑色。如果没有，那么从p到叶子各路径上的黑节点数量就不一样了。 措施:
- 将w变为黑色，p变为红色，且对p做左旋，就变成case 2
- 操作前l，r，x到p的父节点之前的路径有1个黑色节点(p)，操作后还是1个(w)，所以没改变黑色个数的性质。且x有黑色性质，所以p为红色也没违反性质。
3.3.2.2 case 2
x的兄弟节点w是黑色，且w的两个子节点是黑色
w是黑色且x本来就一层黑色，所以从x，w上去掉一层黑色。将这层黑色加到x的父节点身上，指针指向x的父节点。 黑色加到x的父节点之后，有两种情况:
- x的父节点原来是红色，这种情况就不是双重黑色了，直接将x的父节点变为黑色，修复结束。
- x的父节点原来是黑色，那么继续遍历，一直将双重黑色传递至根，这样去掉一重黑色，相当于所有路径都去了一个黑节点，依然满足性质。
3.3.2.3 case 3
x的兄弟节点w是黑色，且w的左儿子是红色，右儿子是黑色
交换w和左儿子的颜色，然后关于w做一次右旋，变成case 4。黑色节点的个数都没有变，所以没改变性质。
3.3.2.4 case 4
x的兄弟节点w是黑色，且w的右儿子是红色
交换w和p的颜色，w的右儿子变成黑色，关于p做一次左旋，循环结束。看下图:
- x的黑色节点相当于转移到p身上了，而w为p之前的颜色，所以是黑是红都不违反性质
- l到原p的父亲中间有1个黑(原w)+1个可能黑(原p)，操作后1个黑(p)+1个可能黑(w)所以刚好也不违反性质，操作后x的双重颜色成功被去掉，结束修复。
3.3.4 小结
按照正常二叉树删除 修复:
- 遇到case 1转case 2，然后一层层向上转移双色节点。
- 遇到case 3转case 4，能将多余一层黑色去掉，修复结束。