在我学习数据结构和算法一段时间之后，就被灌输了二分查找的性能非常好的观念，确实，这也没什么毛病，毕竟 O(logn) 的复杂度确实已经很好了。那么，习惯得，我也将二叉树认为是查找元素的不二选择，好像这在通常情况下问题也不大。

但是，当理论遇到现实的时候，事情就变得有点糟糕了，例如二叉树的理想状态应该是平衡二叉树，也就是说对于每一个分支，左右子树的高度差最多就是一个，这样可以保证查找一个元素的时间复杂度是 O(logn)。事实上，这很难做到，我是说在不修正的情况下，要想让一棵二叉树随时保持平衡，那么我们就需要在增加或删除元素的时候做平衡处理，而这处理的代价经常都会是 O(logn)。

为了在尽可能保持二叉树的优点的同时，又尽可能解决缺点，有很多类似的树型结构被发现，其中有 2-3树／AVL 树／红黑树／B树／B+树等等，每种都有其独特并且优异的地方，而在这篇文章中，我就以红黑树为例，温习一下红黑树的知识。

红黑树与AVL树的比较

  1. AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多；
  2. 红黑是用非严格的平衡来换取增删节点时候旋转次数的降低；
  3. 所以简单说，如果你的应用中，搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB。

红黑树的特点

一棵二叉查找树如果满足以下的红黑性质，那么这就是一棵红黑树：

  1. 每个节点要么是红的，要么是黑的
  2. 根节点是黑的
  3. 每个叶节点(NULL)是黑的
  4. 如果一个节点是红的，那么它的两个儿子都是黑的
  5. 对于每个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑节点

对第 4 个点稍作解释，其实可以说成是没有父子节点都是红的情况，但是，却可以存在父子节点都是黑的情况。

对于一棵红黑树来说，那么它一定满足这些性质，那么只有两种情况会破坏这些性质，那就是插入 和 删除，所以我们需要做一些特别的操作来使 红黑树 能够继续满足条件。

插入节点

往一棵红黑树中插入一个节点时，我们要遵循一些规则：

  1. 插入的节点最开始一定是设置成红的
  2. 插入的节点的位置一开始一定是叶子节点的位置
  3. 只有当父节点的颜色也是红的时候，我们才需要考虑调整

这就是一棵简单的红黑树：
图 1：一棵简单的红黑树

这里将元素4 插入到原来的红黑树中，所以，这里也就破坏红黑性质了，这也是唯一一种需要转换的情况，那就是父子节点都是红的。对于父子节点都是红的，我们需要考虑两种情况：

但是，处理这个问题，有时候很简单得完成，那就是第三种情况：

这个时候我们归纳一下，插入一个新元素的时候，红黑特性被破坏，我们有三种情况需要处理：

下面我们就对这三种情况一一解决。

父节点的兄弟节点也是红的

对于这种情况，我们上面的示例就恰恰是这样的：
图 2：父节点的兄弟节点也是红的

这个时候因为 5 和 8 都是红的，所以我们可以这么操作：

即可，这样我们就让新插入的节点不会破坏 红黑性质 了，因为对于节点 7 来说，我们可以保证它到子节点中的黑节点个数不变，这样的话，整棵树的黑节点路径原则也不会被破坏。

变换之后就是：
图 3：变换父节点和父节点兄弟节点

但是，可以发现，父节点被变换颜色之后又和它的父节点产生了冲突，这个时候就不能通过变换兄弟节点的颜色来解决了。但是，我们可以发现，现在 2 和 7 的情况就是我们的另外一种情况：新的节点在父节点的右子树

新的节点在父节点的右子树

对于父节点的兄弟不是红色的，并且新的节点在父节点的左树的情况：
图 4：新节点是父节点的右子树

这就是刚才解决新插入节点之后的新情况，对节点 7 和节点 2 产生了冲突，这个时候我们需要解决。这里需要引入一个新的概念叫做旋转，旋转包含左旋和右旋，其实他们是对称操作：
图 5：左右旋

所以这里需要利用 左旋 的操作，根据上图的指引，我们进行以节点 2 为根进行 左旋 后的结果是：
图 6：左旋的结果

这个时候又遇到情况了，那就是节点 2 和节点 7 又冲突了并且就是最后一种情况：新的节点在父节点的左子树

新的节点在父节点的左子树

当遇到这种情况的时候，我们就要进行 右旋 操作，右旋操作有个前提就是

右旋 之后的结果应该是：
图 7：右旋的结果

这个时候可以发现这棵二叉查找树 已经满足了所有的 红黑性质，也就是说这又是一棵红黑树，也就是将插入操作调整完毕了。

插入小结

可以看到，这个简单的操作就涉及到了 3 种类型，其实过程中可能不止做一种类型的转换，还会涉及到 2 种或者 3 种类型的转换。

  1. 父节点的兄弟节点也是红的
    1. 将父节点和兄弟节点都改成黑的
    2. 将父节点的父节点改成红的
  2. 新的节点在父节点的右子树
    1. 左旋
  3. 新的节点在父节点的右子树
    1. 将父节点设置为 Black
    2. 将父节点的父节点设置为 Red
    3. 右旋父节点的父节点

删除节点

红黑树中的删除和普通二叉查找树的删除差不多，也就多了一项红黑节点调整。所以假设我们先不考虑红黑调整，那么删除一个节点就是：
图 8：删除节点

这就是一个普通的删除二叉查找树的步骤，其中 tree_successor 就是搜索下一个用来替换当前节点的值，这里需要说明的是这个被用来替换的值肯定是叶子节点，或者说只有右子树的节点，没有其他情况。然后我们所谓的删除就是将两个值调换，将替换的值删掉。

现在是时候考虑一下红黑平衡了，考虑一下，什么时候需要红黑平衡？根据这里的代码，我们可以发现真正被删除的是 y，所以，有两种情况需要考虑：

这个时候又需要考虑两种情况了，对于 x 来说，也有两种可能，那就是：

对于 x 需要承担 2 个黑色的情况，我们有几种情况要考虑：

  1. x 的兄弟 w 是红色的

    那么对于这种情况，我们可以考虑进行一个左旋，然后再改变一下兄弟节点的颜色：
图 9：x 的兄弟 w 是红色的

这里考虑将 节点D 进行一个左旋，那么旋转之后的结果就是：
图 10：左旋结果

我们将 B/D 的颜色进行一个转换，然后我们需要注意的是 x 对应的节点也还必须承担多一个黑色，然而这个 x 已经是黑色了，所以还得转接，但是，很明显，兄弟节点不是红色了，不能旋转了，那我们就需要考虑另外一种情况了。

  1. x 的兄弟 w 是黑色的，而且 w 的两个孩子都是黑色的

因为 x 不能承担多一个黑色，所以我们考虑 w 的情况，首先考虑 w 有两个孩子，并且两个孩子都是黑色的，那么就是这样子的：
图 11：x 的兄弟 w 是黑色的，并且 w 的两个孩子都是黑色的

对于这种情况，我们可以将 节点D 的颜色变为红色，这样的话可以发现左右都差一个黑色，那么我们就将这差的一个黑色让 父节点c 承担，虽然图示中 父节点c 的颜色是红色的，但是事实上红黑都有可能：

所以变换之后应该是这样的：
图 12：变换结果

  1. x 的兄弟 w 是黑色的，而且 w 的左子节点是红色，右子节点是黑色

    这种情况我们可以用图示来表示：
图 13：x 的兄弟 w 是黑色的，而且 w 的左子节点是红色，右子节点是黑色

对于这种情况，我们不能一次性迁移 节点x 的状态，那只能退而求其次，找出一个中间状态，构建这个中间状态：
图 14：中间状态

这里讲 节点C 的位置提升为父节点，然后将原来的 父节点D 将为 节点C 的子节点，并且改变为红色，然后我们再讨论这种情况。

  1. x 的兄弟 w 是黑色的，并且 w 的右子节点是红色

这里我们可以发现我们只关注节点w 的右子节点，并且为红色即可，不需要关注左子节点，这个时候我们可以这样表示这个图：
图 15：节点 w 的右子节点

这时，我们可以将 节点D 左旋，然后就得到了这种情况：
图 16：最终结果

这里有几点地方需要指出来：

  1. 原来 节点w 的右节点E 变成了 Black
  2. 原来 节点D 的颜色变成了 节点B 的颜色
  3. 父节点B 的颜色一定变成 Black

这时，我们再看这张图，会发现 x 不见了，也就是说没有任何节点需要多提供一个黑色，也就是说我们这棵红黑树平衡了。

以上就是我们需要考虑的删除一个节点之后红黑不平衡的问题了，其实核心要点就是记住 变量x 就是表示这个节点需要多提供一个黑色，所以当 x 是 Root 或者是红色的时候，那么我们就成功了，因为：

小结

红黑树的目的就是尽可能保持二叉搜索树的平衡，保证二叉搜索树的搜索速度，同时又要提高插入元素的速度，所以红黑树要设立红黑特性，保证在这两方面之间得到权衡。和 AVL 树相比：

Reference

  1. 算法导论
  2. 教你透彻了解红黑树
  3. 二叉树可视化工具