五月，今天是个好日子，嘿嘿。

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://peterpannju.blogbus.com/logs/21992610.html

    红黑树是个复杂的数据结构。其插入，删除操作复杂度都为O(lgn)。
    红黑树在 linux 内核中应用很多，比如虚拟内存管理，进程调度等。且其常常和 hash 一起出现，是非常重要的数据结构。

Contents:
  Defination of Red-Black Tree
  Insertion
  Deletion
  Comparison with BST & AVL
  Red-Black Tree Demonstration

Defination of Red-Black Tree
As defined in CLRS, a red-black tree is a binary search tree (BST) that satisfies the following properties:

1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL) is black.
4. If a node is red, then both its children are black. (Or in other words, two red nodes may not be adjacent.)
5. For each node, all paths from the node to descendant leaves contain the same number of black nodes.

    红黑树的数据并不存储在叶节点上。叶节点全部是 NIL。这可以帮助红黑树插入删除操作。

红黑树的高度不超过2lg(n+1)。证明请参考 CLRS。

Insertion
    红黑树的插入方法有两种。分别为 Okasaki's Insertion Method 和 CLRS Insertion Method。CLRS给出的方法比 Okasaki 的更复杂，但是效率较高。这里，我们采用 CLRS 中所采用的方法。

    然后，我们令被删除的节点(注意不一定为n)为x，其兄节点为w，分为如下四种情况：
      Case1: w为红色。
      Case2: w为黑色，w的两个孩子都是黑色。
      Case3: w为黑色，w的左孩子为红色，w的右孩子为黑色。
      Case4: w为黑色，w的右孩子为红色。
    转换图如下：

  Case1 => Case2/Case3/Case4
  Case2 => Case4

    最后，我们将x染黑。 

Comparison with BST & AVL
关于红黑树和 AVL & BST 的比较，有人叙述如下：

  AVL trees are actually easier to implement than RB trees because there are fewer cases. And AVL trees require O(1) rotations on an insertion, whereas red-black trees require O(lg n).
  In practice, the speed of AVL trees versus red-black trees will depend on the data that you're inserting. If your data is well distributed, so that an unbalanced binary tree would generally be acceptable (i.e. roughly in random order), but you want to handle bad cases anyway, then red-black trees will be faster because they do less unnecessary rebalancing of already acceptable data. On the other hand, if a pathological insertion order (e.g. increasing order of key) is common, then AVL trees will be faster, because the stricter balancing rule will reduce the tree's height.
  Splay trees might be even faster than either RB or AVL trees,depending on your data access distribution. And if you can use a hash instead of a tree, then that'll be fastest of all.

红黑树，AVL树，BST都有自己的适用范围，不能一言以蔽之谁更好。 

Splay Tree 我没有尝试过，以前学过的 《Java 数据结构》那本书上有相应的一节介绍。

Red-Black Tree Demonstration

这儿有红黑树用 JApplet 做的例子，给出了可视化的操作，很有意思。
http://gauss.ececs.uc.edu/RedBlackTester/redblack.html

参考文章：
一篇介绍红黑树的英文文献，其中对 Okasaki's Insertion Method 有介绍，并且有红黑树高度不超过2lg(n+1)的证明。它给出的 Deletion Method 和 CLRS中的(这篇文章中的)稍有不同，请跳转查看。

上面英文文献的中文版本，附有 AVL 树的比较。但是笔者的翻译水平不怎么样。

内核中的红黑树实现，附有我对插入操作写的部分注释。本文中的代码也是选自此处。