红黑树使用得非常多，然而由于它不在我的本科教材上，我又不用自己实现它，所以我一直不知道它是什么样的。现在想了解一下，结果发现网上我看了好几篇的中文资料都是这种介绍方式——

假设要介绍的树叫梧桐树。文章会告诉你梧桐树会长多高，树叶长什么样，分叉有什么特征，它和棕榈树有什么不同，还会贴心地放一张或者多张梧桐树的照片给你看。

然而红黑树不是梧桐树啊！计算机科学也不是植物学啊！它是为特定目的人造的！所以你倒是说说它为什么会被设计成这个样子啊……

然后我去看了一眼英文维基百科上的介绍，才看了第一段就恍然大悟。

A red–black tree is a kind of self-balancing binary search tree in computer science. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.

意思是，红黑树是一种自平衡二叉树。每个节点有一个额外的比特，通常叫它颜色，并且是红的或者黑的。所以红黑树之所以叫红黑树，只是发明者为了方便叙述给加了点颜色，就跟数学里那些个着色问题（以及物理里夸克的颜色和味道）一样。为什么要加这些颜色呢？它们是用来保证树大致平衡的。

神奇了，为什么加了这么个颜色就能保证了？

Balance is preserved by painting each node of the tree with one of two colors in a way that satisfies certain properties, which collectively constrain how unbalanced the tree can become in the worst case. When the tree is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties. The properties are designed in such a way that this rearranging and recoloring can be performed efficiently.

哦，是用特定的方法着色的，并且树被修改的时候会重新着色。神奇的算法使得这些操作非常高效。也算是用空间换时间了。

The leaf nodes of red–black trees do not contain data. These leaves need not be explicit in computer memory—a null child pointer can encode the fact that this child is a leaf—but it simplifies some algorithms for operating on red–black trees if the leaves really are explicit nodes.

红黑树的叶子节点总是黑色的，并且不包含额外的信息。所以实现的时候实际上不需要显式地存在，或者用同一个节点就好。它的存在只是为了简化算法描述而已。

红黑树的性质：

1. 每个节点不是红色就是黑色。多出来一比特的信息，当然只有两种选择了。
2. 根节点是黑色。
3. 叶子节点是黑色。
4. 红色节点的子节点是黑色。这是为什么非要加个不包含任何信息的黑色叶子节点了。不然弄出来红色叶子节点有点麻烦了。
5. 任意节点到它下方的叶子节点，路径上的黑色节点数是相同的。再一次体现了黑色叶子节点的用处。

这些性质保证了，从根节点到所有叶子节点，最远的路径最多是最近的路径两倍远。不会特别远，甚至是退化成链表了。

然后是树上的操作。

查找就不用说了。二叉树的查找算法而已。

插入的时候，首先把新节点涂成红色，按二叉树的方式插进去，取代某个叶子节点，并自己长出两片叶子。然后修复一下。修复方案如下：

1. 如果这是个根节点，那么涂黑就完事了。
2. 如果它的上级节点是黑色，黑色节点下接红色节点，没事，不需要更多操作了。
3. 如果它的上级节点是红色，并且它的上级邻节点是红色，这就坏事了，违反了性质4。那就把它们涂黑。可这样多了一层黑节点，又会违反性质5。那就把上上级节点涂红（由性质4，上上级节点之前肯定是黑色）。可如果上上级节点是根节点，又违反了性质2。不过上上级节点带的这部分子树肯定是没问题的，那就把整个上上级节点带的这棵子树当整体，递归修复一下好了。
4. 如果它的上级节点是红色，并且它的上级邻节点是黑色，这还是破坏了性质4。而这个时候如果把上级节点涂黑，那么上上级节点不管涂不涂红，一边加了一个黑节点而另一边没有加，它这个子树本身就已经坏掉了，所以得想另外的办法。
   1. 第一步，如果上级节点在左边，而新加节点在右边，那就左旋。如果上级节点在右边，而新加节点在左边，那就右旋。其它情况不用动。由于是两个上下级红色节点在旋转，这样并不会再破坏任何性质。
   2. 第二步，两个红色节点和可以被取代的叶子节点已经准备好了，现在把上上级节点（也就是动过的子树的上级节点）用子树的根换掉，原来的挂到上一步空出来的叶子节点那里，并且把新根涂黑，把一开始那个碍事的黑色节点涂红。这样，两个红色节点就成了同一个黑色节点的子节点。性质4得到了保持，涂色过程只是把黑色上移取代之前的红色，一边的路径上少了个红色节点，另一边多了个红色节点而已，也不会破坏性质5。

删除就更复杂了。

1. 如果被删除的节点有两个非叶子节点，按二叉树的方法删除节点，但是保持原来这个位置上节点的颜色。因为子树的根被保留颜色地替换了，所以这一步不会破坏性质。而少了的（被作为新子树根替换的）节点，递归这个删除算法就可以了，一直在深入，总能递归到没有两个非叶子节点的节点。
2. 你不会想删叶子节点，也不能删它们。
3. 所以剩下一种情况：被删除的节点最多有一个非叶子子节点。如果有的话就叫它 C 好了，没有就随便找个叶子节点当 C。那被删除的节点我们叫 M。
   1. 如果 M 是红色，那用 C 取代它即可。因为 C 肯定是黑色（而且是叶子节点）。
   2. 如果 M 是黑色，但 C 是红色，用 C 取代 M，并且把 C 涂黑。少了一个红色节点而已，没事的。
   3. 如果 M 和 C 都是黑色，这个时候 C 也一定是叶子节点。先用 C 取代 M，并叫新的 C 为 N，其上级节点为 P，P 的另一个子节点为 S。现在 N 这边少了个黑色节点，相对的，S 这边多了一个。
      1. 如果 N 是根节点（P 不存在），那么没事了。
      2. 如果 P 是黑色，并且 S 是红色，旋转一下，让 S 成为新的子树的根，并将 P 涂红。从颜色上看，只是红色从一个子节点跑到另一个，然后有棵子树从一边换到另一边了，性质不会被再度破坏。但之前被破坏的部分还没修复呢，现在是一个黑色下边有一个黑色的节点那里的路径上多了一个黑色节点，要走下边的步骤。
      3. 如果 P 和 S 都是黑色，N 那边不是被删掉了一个黑色节点吗，现在把 S 涂红，这样 P 的两边（N 和 S）都少了个黑色节点。子树没有问题，然而 P 这边的路径上少了个黑色节点。要么 P 是根节点，不用管了。要么 P 的邻节点那边的路径多了个黑色节点，情况就是一个子树，下方有一个黑色节点，并且这一边的路径上多了个黑色节点。如果子树的根是黑色，那么递归了，回去再走一遍上一步（3.3.2）就好。如果是红色，走下边的步骤。
      4. 如果 P 是红色，并且 S 和 S 的子节点都是黑色，把 P 和 S 的颜色交换一下，S 那边的路径少了个黑色节点，处理好了。
      5. 如果 P 是红色，N 位于左侧，并且 S 的左子节点是红色，右子节点是黑色。N 当然是黑色的啦。那么把 S 右旋，并且把旧 S 的左节点（新的子树根）涂黑，然后旧 S 自己（新右子节点）涂红。继续下边的步骤。
      6. 如果 P 是红色，N 位于左侧，并且 S 的左子节点是黑色，右子节点是红色，把 P 左旋一下，并把之前那个红色子节点涂黑。这样 N 那侧的路径多了个黑色节点。完成了。
      7. 如果 P 是红色，N 位于右侧。把上两步镜像一下就可以了。

总之就是各种涂色和旋转，来保持二叉树和红黑树的性质不被破坏（红黑树是二叉树，所以旋转需要点技巧，不是想旋转就一定能旋转的）。看着复杂，照着前人已经想好的步骤去做其实也并不难。然而中文网络上几乎没有人解释这些步骤的目的，以至于让人理解不能 :-(