主要来源 https://segmentfault.com/a/1190000000472153
红黑树，众所周知，是一个STL标准库的map当中sort的算法。其实在学CS100的时候完全不知道这些是什么，感谢侯捷老师，带我领略STL的奇妙世界。
红黑树介绍
第一个性质
对于树中的每一个节点，如哦它有左子树，且他的中所有节点的值不大于该节点值；如果它有右子树，则右子树中所有节点的值不小于该节点的值。
红黑树，能保证在最坏情况下，基本的动态几何操作的时间均为O（lgn）。
在红黑树的每一个节点中都含有五个域color，key，left，right，p
如果指针域没有，则轮空
性质总结
1.每个节点要么是红的，要么是黑的。
2.根节点是黑的。
3.每个叶节点（叶节点即指树尾端NIL指针或NULL节点）是黑的。
4.如果一个节点是红的，那么它的两个儿子都是黑的。
5.对于任一节点而言，其到叶节点树尾端NIL指针的每一条路径都包含相同数目的黑节点。
一些常规操作
左旋
当在某个节点pivot上的时候，假设右孩子不是NIL[t],pivot 可以为树内的任意左孩子而不是NIL[t]的节点。
左旋以pivot到y之间的链为“支轴”进行，它使y成为该孩子树的新根，而y的左孩子b则成为pivot的右孩子。
LEFT-ROTATE(T, x)
y ← right[x] ▹ Set y.
right[x] ← left[y] ▹ Turn y's left subtree into x's right subtree.
p[left[y]] ← x
p[y] ← p[x] ▹ Link x's parent to y.
if p[x] = nil[T]
then root[T] ← y
else if x = left[p[x]]
then left[p[x]] ← y
else right[p[x]] ← y
left[y] ← x ▹ Put x on y's left.
p[x] ← y右旋
RB-INSERT(T, z)
y ← nil[T]
x ← root[T]
while x ≠ nil[T]
do y ← x
if key[z] < key[x]
then x ← left[x]
else x ← right[x]
p[z] ← y
if y = nil[T]
then root[T] ← z
else if key[z] < key[y]
then left[y] ← z
else right[y] ← z
left[z] ← nil[T]
right[z] ← nil[T]
color[z] ← RED
RB-INSERT-FIXUP(T, z)咱们来具体分析下，此段代码：
RB-INSERT(T, z)，将z插入红黑树T 之内。为保证红黑性质在插入操作后依然保持，上述代码调用了一个辅助程序RB-INSERT-FIXUP来对节点进行重新着色，并旋转。
left[z] ← nil[T]
right[z] ← nil[T] //保持正确的树结构第16行，将z着为红色，由于将z着为红色可能会违背某一条红黑树的性质，
所以，在第17行，调用RB-INSERT-FIXUP（T,z）来保持红黑树的性质。
RB-INSERT-FIXUP(T, z)，如下所示：
while color[p[z]] = RED
do if p[z] = left[p[p[z]]]
then y ← right[p[p[z]]]
if color[y] = RED
then color[p[z]] ← BLACK ▹ Case 1
color[y] ← BLACK ▹ Case 1
color[p[p[z]]] ← RED ▹ Case 1
z ← p[p[z]] ▹ Case 1
else if z = right[p[z]]
then z ← p[z] ▹ Case 2
LEFT-ROTATE(T, z) ▹ Case 2
color[p[z]] ← BLACK ▹ Case 3
color[p[p[z]]] ← RED ▹ Case 3
RIGHT-ROTATE(T, p[p[z]]) ▹ Case 3
else (same as then clause
with "right" and "left" exchanged)
color[root[T]] ← BLACKok，参考一网友的言论，用自己的语言，再来具体解剖下上述俩段代码。
为了保证阐述清晰，我再写下红黑树的5个性质：
- 每个节点要么是红的，要么是黑的。
- 根节点是黑的。
- 每个叶节点，即空节点（NIL）是黑的。
- 如果一个节点是红的，那么它的俩个儿子都是黑的。
- 对每个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑节点。
在对红黑树进行插入操作时，我们一般总是插入红色的节点，因为这样可以在插入过程中尽量避免对树的调整。 那么，我们插入一个节点后，可能会使原树的哪些性质改变列? 由于，我们是按照二叉树的方式进行插入，因此元素的搜索性质不会改变。
如果插入的节点是根节点，性质2会被破坏，如果插入节点的父节点是红色，则会破坏性质4。 因此，总而言之，插入一个红色节点只会破坏性质2或性质4。 我们的恢复策略很简单，
- 把出现违背红黑树性质的节点向上移，如果能移到根节点，那么很容易就能通过直接修改根节点来恢复红黑树的性质。直接通过修改根节点来恢复红黑树应满足的性质。
- 穷举所有的可能性，之后把能归于同一类方法处理的归为同一类，不能直接处理的化归到下面的几种情况，
注：以下情况3、4、5与上述算法导论上的代码RB-INSERT-FIXUP(T, z)，相对应：
插入修复具体操作情况
1) 情况1：插入的是根节点。
原树是空树，此情况只会违反性质2。
对策：直接把此节点涂为黑色。
2) 情况2：插入的节点的父节点是黑色。
此不会违反性质2和性质4，红黑树没有被破坏。
对策：什么也不做。
3) 情况3：当前节点的父节点是红色且祖父节点的另一个子节点（叔叔节点）是红色。
此时父节点的父节点一定存在，否则插入前就已不是红黑树。与此同时，又分为父节点是祖父节点的左子还是右子，对于对称性，我们只要解开一个方向就可以了。 在此，我们只考虑父节点为祖父左子的情况。 同时，还可以分为当前节点是其父节点的左子还是右子，但是处理方式是一样的。我们将此归为同一类。
对策：将当前节点的父节点和叔叔节点涂黑，祖父节点涂红，把当前节点指向祖父节点，从新的当前节点重新开始算法。
针对情况3，变化前（图片来源：saturnman）[当前节点为4节点]：
变化后：
4) 情况4：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子
对策：当前节点的父节点做为新的当前节点，以新当前节点为支点左旋。
如下图所示，变化前[当前节点为7节点]：
变化后：
5) 情况5：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左子
解法：父节点变为黑色，祖父节点变为红色，在祖父节点为支点右旋
如下图所示[当前节点为2节点]
变化后：
回顾：经过上面情况3、情况4、情况5等3种插入修复情况的操作示意图，读者自会发现，后面的情况4、情况5都是针对情况3插入节点4以后，进行的一系列插入修复情况操作，不过，指向当前节点N指针一直在变化。所以，你可以想当然的认为：整个下来，情况3、4、5就是一个完整的插入修复情况的操作流程。
II、ok，接下来，咱们最后来了解，红黑树的删除操作：
为了保证以下的介绍与阐述清晰，我第三次重写下红黑树的5个性质
- 每个节点要么是红的，要么是黑的。
- 根节点是黑的。
- 每个叶节点，即空节点（NIL）是黑的。
- 如果一个节点是红的，那么它的俩个儿子都是黑的。
- 对每个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑节点。
相信，重述了3次，你应该有深刻记忆了。:D
我们删除的节点的方法与常规二叉搜索树中删除节点的方法是一样的，如果被删除的节点不是有双非空子女，则直接删除这个节点，用它的唯一子节点顶替它的位置，如果它的子节点分是空节点，那就用空节点顶替它的位置，如果它的双子全为非空，我们就把它的直接后继节点内容复制到它的位置，之后以同样的方式删除它的后继节点，它的后继节点不可能是双子非空，因此此传递过程最多只进行一次。
继续讲解之前，补充说明下二叉树节点删除的几种情况，待删除的节点按照儿子的个数可以分为三种：
- 没有儿子，即为叶节点。直接把父节点的对应儿子指针设为NULL，删除儿子节点就OK了。
- 只有一个儿子。那么把父节点的相应儿子指针指向儿子的独生子，删除儿子节点也OK了。
- 有两个儿子。这是最麻烦的情况，因为你删除节点之后，还要保证满足搜索二叉树的结构。其实也比较容易，我们可以选择左儿子中的最大元素或者右儿子中的最小元素放到待删除节点的位置，就可以保证结构的不变。当然，你要记得调整子树，毕竟又出现了节点删除。习惯上大家选择左儿子中的最大元素，其实选择右儿子的最小元素也一样，没有任何差别，只是人们习惯从左向右。这里咱们也选择左儿子的最大元素，将它放到待删节点的位置。左儿子的最大元素其实很好找，只要顺着左儿子不断的去搜索右子树就可以了，直到找到一个没有右子树的节点。那就是最大的了。
OK，回到红黑树上来。算法导论一书，给的红黑树节点删除的算法实现是：
RB-DELETE(T, z) 单纯删除节点的总操作
if left[z] = nil[T] or right[z] = nil[T]
then y ← z
else y ← TREE-SUCCESSOR(z)
if left[y] ≠ nil[T]
then x ← left[y]
else x ← right[y]
p[x] ← p[y]
if p[y] = nil[T]
then root[T] ← x
else if y = left[p[y]]
then left[p[y]] ← x
else right[p[y]] ← x
if y 3≠ z
then key[z] ← key[y]
copy y's satellite data into z
if color[y] = BLACK
then RB-DELETE-FIXUP(T, x)
return y在删除节点后，原红黑树的性质可能被改变，如果删除的是红色节点，那么原红黑树的性质依旧保持，此时不用做修正操作，如果删除的节点是黑色节点，原红黑树的性质可能会被改变，我们要对其做修正操作。那么哪些树的性质会发生变化呢，如果删除节点不是树唯一节点，那么删除节点的那一个支的到各叶节点的黑色节点数会发生变化，此时性质5被破坏。如果被删节点的唯物主唯一非空子节点是红色，而被删节点的父节点也是红色，那么性质4被破坏。如果被删节点是根节点，而它的唯一非空子节点是红色，则删除后新根节点将变成红色，违背性质2。
RB-DELETE-FIXUP(T, x) 恢复与保持红黑性质的工作
while x ≠ root[T] and color[x] = BLACK
do if x = left[p[x]]
then w ← right[p[x]]
if color[w] = RED
then color[w] ← BLACK ▹ Case 1
color[p[x]] ← RED ▹ Case 1
LEFT-ROTATE(T, p[x]) ▹ Case 1
w ← right[p[x]] ▹ Case 1
if color[left[w]] = BLACK and color[right[w]] = BLACK
then color[w] ← RED ▹ Case 2
x p[x] ▹ Case 2
else if color[right[w]] = BLACK
then color[left[w]] ← BLACK ▹ Case 3
color[w] ← RED ▹ Case 3
RIGHT-ROTATE(T, w) ▹ Case 3
w ← right[p[x]] ▹ Case 3
color[w] ← color[p[x]] ▹ Case 4
color[p[x]] ← BLACK ▹ Case 4
color[right[w]] ← BLACK ▹ Case 4
LEFT-ROTATE(T, p[x]) ▹ Case 4
x ← root[T] ▹ Case 4
else (same as then clause with "right" and "left" exchanged)
color[x] ← BLACK上面的修复情况看起来有些复杂，下面我们用一个分析技巧：我们从被删节点后来顶替它的那个节点开始调整，并认为它有额外的一重黑色。这里额外一重黑色是什么意思呢，我们不是把红黑树的节点加上除红与黑的另一种颜色，这里只是一种假设，我们认为我们当前指向它，因此空有额外一种黑色，可以认为它的黑色是从它的父节点被删除后继承给它的，它现在可以容纳两种颜色，如果它原来是红色，那么现在是红+黑，如果原来是黑色，那么它现在的颜色是黑+黑。有了这重额外的黑色，原红黑树性质5就能保持不变。现在只要花时是恢复其它性质就可以了，做法还是尽量向根移动和穷举所有可能性。 ——saturnman
红黑树删除修复操作的几种情况@saturnman：
注：以下的情况3、4、5、6，与上述算法导论之代码RB-DELETE-FIXUP(T, x) 恢复与保持 中case1，case2，case3，case4相对应。
情况1：当前节点是红+黑色
解法，直接把当前节点染成黑色，结束。此时红黑树性质全部恢复。
情况2：当前节点是黑+黑且是根节点
解法：什么都不做，结束
情况3：当前节点是黑+黑且兄弟节点为红色(此时父节点和兄弟节点的子节点分为黑)。
解法：把父节点染成红色，把兄弟节点染成黑色，之后重新进入算法（我们只讨论当前节点是其父节点左孩子时的情况）。此变换后原红黑树性质5不变，而把问题转化为兄弟节点为黑色的情况(注：变化前，原本就未违反性质5，只是为了把问题转化为兄弟节点为黑色的情况)。
变化前：
变化后：
情况4：当前节点是黑加黑且兄弟是黑色且兄弟节点的两个子节点全为黑色。
解法：把当前节点和兄弟节点中抽取一重黑色追加到父节点上，把父节点当成新的当前节点，重新进入算法。（此变换后性质5不变）
变化前
变化后
情况5：当前节点颜色是黑+黑，兄弟节点是黑色，兄弟的左子是红色，右子是黑色。。
解法：把兄弟节点染红，兄弟左子节点染黑，之后再在兄弟节点为支点解右旋，之后重新进入算法。此是把当前的情况转化为情况6，而性质5得以保持。
变化前：
变化后：
情况6：当前节点颜色是黑-黑色，它的兄弟节点是黑色，但是兄弟节点的右子是红色，兄弟节点左子的颜色任意。
解法：把兄弟节点染成当前节点父节点的颜色，把当前节点父节点染成黑色，兄弟节点右子染成黑色，之后以当前节点的父节点为支点进行左旋，此时算法结束，红黑树所有性质调整正确。
变化前：
变化后：
