原文链接：http://liuliqiang.info/post/red-black-tree/
在我学习数据结构和算法一段时间之后，就被灌输了二分查找的性能非常好的观念，确实，这也没什么毛病，毕竟 O(logn) 的复杂度确实已经很好了。那么，习惯得，我也将二叉树认为是查找元素的不二选择，好像这在通常情况下问题也不大。
但是，当理论遇到现实的时候，事情就变得有点糟糕了，例如二叉树的理想状态应该是平衡二叉树，也就是说对于每一个分支，左右子树的高度差最多就是一个，这样可以保证查找一个元素的时间复杂度是 O(logn)。事实上，这很难做到，我是说在不修正的情况下，要想让一棵二叉树随时保持平衡，那么我们就需要在增加或删除元素的时候做平衡处理，而这处理的代价经常都会是 O(logn)。
为了在尽可能保持二叉树的优点的同时，又尽可能解决缺点，有很多类似的树型结构被发现，其中有 2-3树／AVL 树／红黑树／B树／B+树等等，每种都有其独特并且优异的地方，而在这篇文章中，我就以红黑树为例，温习一下红黑树的知识。
红黑树与AVL树的比较：
AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多；
红黑是用非严格的平衡来换取增删节点时候旋转次数的降低；
所以简单说，如果你的应用中，搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB。
红黑树的特点
一棵二叉查找树如果满足以下的红黑性质，那么这就是一棵红黑树：
每个节点要么是红的，要么是黑的
根节点是黑的
每个叶节点(NULL)是黑的
如果一个节点是红的，那么它的两个儿子都是黑的
对于每个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑节点
对第 4 个点稍作解释，其实可以说成是没有父子节点都是红的情况，但是，却可以存在父子节点都是黑的情况。
对于一棵红黑树来说，那么它一定满足这些性质，那么只有两种情况会破坏这些性质，那就是插入 和 删除，所以我们需要做一些特别的操作来使 红黑树 能够继续满足条件。
插入节点
往一棵红黑树中插入一个节点时，我们要遵循一些规则：
插入的节点最开始一定是设置成红的
插入的节点的位置一开始一定是叶子节点的位置
只有当父节点的颜色也是红的时候，我们才需要考虑调整
这就是一棵简单的红黑树：
这里将元素4 插入到原来的红黑树中，所以，这里也就破坏红黑性质了，这也是唯一一种需要转换的情况，那就是父子节点都是红的。对于父子节点都是红的，我们需要考虑两种情况：
新的节点在父节点的左树
新的节点在父节点的右树
但是，处理这个问题，有时候很简单得完成，那就是第三种情况：
父节点的兄弟节点也是红的
这个时候我们归纳一下，插入一个新元素的时候，红黑特性被破坏，我们有三种情况需要处理：
父节点的兄弟节点也是红的
新的节点在父节点的左子树
新的节点在父节点的右子树
下面我们就对这三种情况一一解决。
父节点的兄弟节点也是红的
对于这种情况，我们上面的示例就恰恰是这样的：
这个时候因为 5 和 8 都是红的，所以我们可以这么操作：
将 5 和 8 变为黑，然后将 7 变成红
即可，这样我们就让新插入的节点不会破坏 红黑性质 了，因为对于节点 7 来说，我们可以保证它到子节点中的黑节点个数不变，这样的话，整棵树的黑节点路径原则也不会被破坏。
变换之后就是：
但是，可以发现，父节点被变换颜色之后又和它的父节点产生了冲突，这个时候就不能通过变换兄弟节点的颜色来解决了。但是，我们可以发现，现在 2 和 7 的情况就是我们的另外一种情况：新的节点在父节点的右子树
新的节点在父节点的右子树
对于父节点的兄弟不是红色的，并且新的节点在父节点的左树的情况：
这就是刚才解决新插入节点之后的新情况，对节点 7 和节点 2 产生了冲突，这个时候我们需要解决。这里需要引入一个新的概念叫做旋转，旋转包含左旋和右旋，其实他们是对称操作：
所以这里需要利用 左旋 的操作，根据上图的指引，我们进行以节点 2 为根进行 左旋 后的结果是：
这个时候又遇到情况了，那就是节点 2 和节点 7 又冲突了并且就是最后一种情况：新的节点在父节点的左子树
新的节点在父节点的左子树
当遇到这种情况的时候，我们就要进行 右旋 操作，右旋操作有个前提就是
将父节点设置为 Black
将父节点的父节点设置为 Red
右旋 父节点的父节点
右旋 之后的结果应该是：
这个时候可以发现这棵二叉查找树 已经满足了所有的 红黑性质，也就是说这又是一棵红黑树，也就是将插入操作调整完毕了。
插入小结
可以看到，这个简单的操作就涉及到了 3 种类型，其实过程中可能不止做一种类型的转换，还会涉及到 2 种或者 3 种类型的转换。
父节点的兄弟节点也是红的
将父节点和兄弟节点都改成黑的
将父节点的父节点改成红的
新的节点在父节点的右子树
左旋
新的节点在父节点的右子树
将父节点设置为 Black
将父节点的父节点设置为 Red
右旋父节点的父节点
删除节点
红黑树中的删除和普通二叉查找树的删除差不多，也就多了一项红黑节点调整。所以假设我们先不考虑红黑调整，那么删除一个节点就是：
这就是一个普通的删除二叉查找树的步骤，其中 tree_successor 就是搜索下一个用来替换当前节点的值，这里需要说明的是这个被用来替换的值肯定是叶子节点，或者说只有右子树的节点，没有其他情况。然后我们所谓的删除就是将两个值调换，将替换的值删掉。
现在是时候考虑一下红黑平衡了，考虑一下，什么时候需要红黑平衡？根据这里的代码，我们可以发现真正被删除的是 y，所以，有两种情况需要考虑：
y 是红色的，那么删除红色节点之后，并不会影响后续节点路径中黑色节点的个数，也不会导致两个红色节点成为父子节点，那么也就是说是安全的，无需红黑平衡了。
y 是黑色的，那么这个时候被删除了，和 y 有关的路径就少了一个黑色节点，那么我们可以考虑将这个黑色节点下移，转给 y 的儿子 x，也就是说 x 必须承担一个黑色。
这个时候又需要考虑两种情况了，对于 x 来说，也有两种可能，那就是：
x 是红色的，那么我们直接将 x 转变为黑色，那么整个路径上黑色节点的个数也平衡了，而且也不会有两个红色成为父子节点，就成功了。
x 是黑色的，那么显然不能再提供一个黑色，那么只能继续迁移，需要记住，此时 x 承担了 2 个黑色的责任，需要找人承担一个
对于 x 需要承担 2 个黑色的情况，我们有几种情况要考虑：
x 的兄弟 w 是红色的
那么对于这种情况，我们可以考虑进行一个左旋，然后再改变一下兄弟节点的颜色：
这里考虑将 节点D 进行一个左旋，那么旋转之后的结果就是：
我们将 B/D 的颜色进行一个转换，然后我们需要注意的是 x 对应的节点也还必须承担多一个黑色，然而这个 x 已经是黑色了，所以还得转接，但是，很明显，兄弟节点不是红色了，不能旋转了，那我们就需要考虑另外一种情况了。
x 的兄弟 w 是黑色的，而且 w 的两个孩子都是黑色的
因为 x 不能承担多一个黑色，所以我们考虑 w 的情况，首先考虑 w 有两个孩子，并且两个孩子都是黑色的，那么就是这样子的：
rb-case2-01.png
对于这种情况，我们可以将 节点D 的颜色变为红色，这样的话可以发现左右都差一个黑色，那么我们就将这差的一个黑色让 父节点c 承担，虽然图示中 父节点c 的颜色是红色的，但是事实上红黑都有可能：
如果是红色，那么直接变成黑色就大功告成了
如果是黑色，那么就需要多贡献一个黑色，如果不能贡献，那只能继续根据各种情况递归下去
所以变换之后应该是这样的：
rb-case2-02.png
x 的兄弟 w 是黑色的，而且 w 的左子节点是红色，右子节点是黑色
这种情况我们可以用图示来表示：
rb-case3-01.png
对于这种情况，我们不能一次性迁移 节点x 的状态，那只能退而求其次，找出一个中间状态，构建这个中间状态：
rb-case3-02.png
这里讲 节点C 的位置提升为父节点，然后将原来的 父节点D 将为 节点C 的子节点，并且改变为红色，然后我们再讨论这种情况。
x 的兄弟 w 是黑色的，并且 w 的右子节点是红色
这里我们可以发现我们只关注 节点w 的右子节点，并且为红色即可，不需要关注左子节点，这个时候我们可以这样表示这个图：
rb-case4-01.png
这时，我们可以将 节点D 左旋，然后就得到了这种情况：
rb-case4-02.png
这里有几点地方需要指出来：
原来 节点w 的右节点E 变成了 Black
原来 节点D 的颜色变成了 节点B 的颜色
父节点B 的颜色一定变成 Black
这时，我们再看这张图，会发现 x 不见了，也就是说没有任何节点需要多提供一个黑色，也就是说我们这棵红黑树平衡了。
以上就是我们需要考虑的删除一个节点之后红黑不平衡的问题了，其实核心要点就是记住 变量x 就是表示这个节点需要多提供一个黑色，所以当 x 是 Root 或者是红色的时候，那么我们就成功了，因为：
如果 root 需要提供多一个黑色，那么其实完全就不用多提供了，因为 root 无父节点需要平衡。
如果是红色节点需要提供多一个黑色，那么尽管把它变成黑色好了，因为把它变成黑色不会影响我们的红黑特性，最可能影响到的一条特性就是任何路径上的黑色节点数一样，但是因为包含这个节点的路径都少了一个，所以尽管变成黑色就可以了。
小结
红黑树的目的就是尽可能保持二叉搜索树的平衡，保证二叉搜索树的搜索速度，同时又要提高插入元素的速度，所以红黑树要设立红黑特性，保证在这两方面之间得到权衡。和 AVL 树相比：
如果你的插入和搜索频率差不多，那么就用 红黑树
如果插入远远少于查询，那么用 AVL树 划算
Reference
算法导论
教你透彻了解红黑树
二叉树可视化工具