红黑树特点

每个节点或者是红色的，或者是黑色的；
根节点是黑色的；
每个叶子结点（最后的空节点）是黑色的；
如果一个节点是红色的，那么他的孩子都是黑色的；[红色不能连着]
从任意一个节点到叶子节点经过的黑色节点是一样的。

增加操作

图中 C 为当前需要插入的节点，P 为当前插入节点的双亲结点，U 为当前插入节点的叔叔节点，G 为当前插入节点的祖父节点！增加节点就是这四种情况了，我们只需要考虑三代节点，还是非常简单的…

这里推荐一个网站，可以试验一下红黑树的增加删除，感觉贼爽啊！！！

(其实是我不想画图找例子了…自己去试验吧..这四种情况的方法屡试不爽)

cs.usfca.edu/~galles/visualization/RedBlack.html

话说，咱中文的博客真的好多人都不太懂这个红黑树，各种错误的例子就往上贴，其实本来是很简单的知识点，把我硬是整迷糊了…真是误人子弟啊…好气啊！

删除操作

删除是红黑树中最难的部分！但是其实跟拧魔方是一样哒！只要掌握了技巧，管你是什么，套公式就完事儿了！

[维基百科写的啥玩意儿，我的智商受到了压制…]

想要删除一个节点，首先就要考虑它有几个孩子：
- 若想要删除的节点，我这里记为 N，若 N 有两个孩子，则我们可以找 N 的左子树最大值或者是 N 的右子树最小值，将其值复制到 N ,然后 不删除 N 这个节点，转而去删除被复制的那个节点(N 的左子树最大值或者是 N 的右子树最小值所在的节点)，为什么要这样转换呢？因为我们知道，N 的左子树最大值或者是 N 的右子树最小值最多也就一个儿子(我这里说的儿子是不包括叶子结点[叶子结点全部是黑色空节点哦，这是红黑树的性质3]的哈~)
- 所以我们现在只需要考虑删除只有一个儿子或者没有儿子的节点
- 看上图，其实也就剩下3种情况，分别是
  - 需删除节点为黑色，有一个颜色为红色的孩子
  - 需删除节点为红色，且没有儿子
  - 需删除节点为黑色，且没有儿子
  前面两种情况是很好处理的，最难的就是第三种情况，需删除节点为黑色，且没有儿子，接下来我们就只需要考虑这种情况！！！
这种情况下，只需要考虑四个节点，分别是 父亲节点 P、兄弟节点 S、S 的左孩子 S1、S 的右孩子 S2，按理说4个节点，颜色排列组合，可以排成16种，但是有些是不符合红黑树性质的组合，现在我们来一一排列一下。

粗略看一下，总共是有9种情况的！在文末会给出我自己总结的这9种分别对应的操作方式，大家可以直接看文末！！！

一道例题

要删除的节点是黑色节点，且儿子为叶子结点

如题，要删除的节点是40，其父亲是55，黑色节点，记为P；其兄弟是65，红色节点，记为S，其侄子是60，75，黑色节点。

如图，这是删除了40之后的图，其儿子—-叶子结点变为x，现在不满足性质5，需要进行变换。

Case I：S 为红色，P 为黑色
- 将 S 和 P 的颜色互换，即 S 变为黑色，P 变为红色
- 对父亲节点 P 进行 左旋，注意哦，因为是左旋，所以圆心是兄弟节点 S

Case II：此时又是一个新的可能出现的场景，删除节点后，P 为红色节点，而兄弟节点 S 为黑色节点，但是兄弟的左孩子为红色，右孩子(叶子结点，当然其也只能是叶子节点，否则就违反性质5了)为黑色。
- 此时，将 S 变为红色，S 的左孩子变为黑色
- 然后，违法了性质 4，将 S 右旋

Case III：此时第三种情况出现了，P 为红色， S 为黑色，S 的左孩子为黑色叶子结点，S 的右孩子为红色节点
- 将 S 的右孩子(红色)、P(红色)、S(黑色)，颜色互换
- 然后将 x 现在的父亲进行左旋

维基百科部分

情形1: N是新的根。在这种情形下，我们就做完了。我们从所有路径去除了一个黑色节点，而新根是黑色的，所以性质都保持着。

注意：在情形2、5和6下，我们假定N是它父亲的左儿子。如果它是右儿子，则在这些情形下的左和右应当对调。

情形2： S是红色。在这种情形下我们在N的父亲上做左旋转，把红色兄弟转换成N的祖父，我们接着对调N的父亲和祖父的颜色。完成这两个操作后，尽管所有路径上黑色节点的数目没有改变，但现在N有了一个黑色的兄弟和一个红色的父亲（它的新兄弟是黑色因为它是红色S的一个儿子），所以我们可以接下去按情形4、情形5或情形6来处理。（注意：这里的图中没有显示出来，N是删除了黑色节点后替换上来的子节点，所以这个过程中由P->X->N变成了P->N，实际上是少了一个黑色节点，也可以理解为Parent(Black)和Silbing(Red)那么他们的孩子黑色节点的数目肯定不等，让他们做新兄弟肯定是不平衡的，还需后面继续处理。这里看英文版本的[1]比较的明了）

情形3： N的父亲、S和S的儿子都是黑色的。在这种情形下，我们简单的重绘S为红色。结果是通过S的所有路径，它们就是以前不通过N的那些路径，都少了一个黑色节点。因为删除N的初始的父亲使通过N的所有路径少了一个黑色节点，这使事情都平衡了起来。但是，通过P的所有路径现在比不通过P的路径少了一个黑色节点，所以仍然违反性质5。要修正这个问题，我们要从情形1开始，在P上做重新平衡处理。

情形4： S和S的儿子都是黑色，但是N的父亲是红色。在这种情形下，我们简单的交换N的兄弟和父亲的颜色。这不影响不通过N的路径的黑色节点的数目，但是它在通过N的路径上对黑色节点数目增加了一，添补了在这些路径上删除的黑色节点。

情形5： S是黑色，S的左儿子是红色，S的右儿子是黑色，而N是它父亲的左儿子。在这种情形下我们在S上做右旋转，这样S的左儿子成为S的父亲和N的新兄弟。我们接着交换S和它的新父亲的颜色。所有路径仍有同样数目的黑色节点，但是现在N有了一个黑色兄弟，他的右儿子是红色的，所以我们进入了情形6。N和它的父亲都不受这个变换的影响。

情形6： S是黑色，S的右儿子是红色，而N是它父亲的左儿子。在这种情形下我们在N的父亲上做左旋转，这样S成为N的父亲（P）和S的右儿子的父亲。我们接着交换N的父亲和S的颜色，并使S的右儿子为黑色。子树在它的根上的仍是同样的颜色，所以性质3没有被违反。但是，N现在增加了一个黑色祖先：要么N的父亲变成黑色，要么它是黑色而S被增加为一个黑色祖父。所以，通过N的路径都增加了一个黑色节点。此时，如果一个路径不通过N，则有两种可能性：它通过N的新兄弟。那么它以前和现在都必定通过S和N的父亲，而它们只是交换了颜色。所以路径保持了同样数目的黑色节点。它通过N的新叔父，S的右儿子。那么它以前通过S、S的父亲和S的右儿子，但是现在只通过S，它被假定为它以前的父亲的颜色，和S的右儿子，它被从红色改变为黑色。合成效果是这个路径通过了同样数目的黑色节点。在任何情况下，在这些路径上的黑色节点数目都没有改变。所以我们恢复了性质4。在示意图中的白色节点可以是红色或黑色，但是在变换前后都必须指定相同的颜色。