对于用树来进行搜索已经是没有疑义的事，二叉搜索树现在已经写进了所有入门算法课程，虽然并非所有的IT岗位都要求程序员掌握初级数据结构和算法，但几十年来对搜索树的改进一直没有中断过，并且这一技术在关键的研发过程和创新产品中，被证明是极有价值的.
起源
红黑树 RB Tree，是对二叉搜索树的一次重要改进，他于1972年被德国的Bayer教授提出，该教授....Symmetric binary B-trees, 不过自 Guibas 及 Sedgewick 1978年的一篇文章问世之后，这一数据结构被公开称为红黑树——这一名称有助于回想红黑树的基本定义及重要特性。
目前红黑树是一种十分重要的基础数据结构，在Introduction to Algorithm 与 Linux Kernel中都可以找到他的身影. 由于早已被广泛研究，红黑树的标准定义，重要性质、操作，没有太大的神秘性，大致用列表表示即可。
红黑树的标准定义包括5条语句，简洁地表达就是: 红黑树为每一个节点赋予一个颜色属性, 利用它来维持半平衡性. 在红黑树中, 任何两个叶子到根的距离不会相差两倍以上.
原始文献可以在斯普林格网站下载：http://www.springerlink.com/content/qh51m2014673513j/
操作
对于一个具有强限制条件的树，随机插入、删除操作是极有破坏性的，所以像一般的平衡二叉树一样，需要有旋转操作来维护定义的满足。而这一数据结构和算法的性能也可由插入删除的效率来衡量. 红黑树有非常不错的效率.
旋转的简要规则是: x替代y位置, 将y变为x的子节点, x原有的一个子节点beta转换为y的子节点.
一个有趣的现象是，红黑树旋转不改变前序遍历结果.
设计好旋转操作之后，插入删除操作的步骤就可以利用旋转操作来保证定义不被违反.
插入操作本身与一般的搜索二叉树无异, 为了保持平衡，插入后需要进行着色和旋转，因而插入的整体复杂度O(lg n).
删除操作比插入操作稍微复杂，按照正常的树结点删除进行操作，而后进行颜色调整并旋转，实现时的复杂性在于RB树有几种边界条件需要单独处理。事实上结构的设计中已经引入改进来简化这些情况，即任何有效的数据节点都是内结点，所有的边界节点都是假节点，仅在各种操作中充当占未符。删除操作的复杂度也是O(lg n)。
使用
红黑树，以及其他许多平衡二叉树，被用来维护Set、Map类的数据集合时很适合的。虽然很多时候Hash List也被用来实现Map、Set(比如Java中的各种数据结构)，但是平衡二叉树的实现在某些方面的优点不可替代。首先平衡二叉树是搜索二叉树的事实，决定了对元素简直进行排序时的效率很高. 其次，若要求进行集合运算如比较、合并，则需要使用二叉树的实现形式。
一种类似于红黑树但是更适合直接读写磁盘数据的树是B-tree, 同样也是由Bayer提出.
参考
http://www.eli.sdsu.edu/courses/fall96/cs660/notes/redBlack/redBlack.html
http://sunland.gsfc.nasa.gov/info/scheme/Red-Black_Trees.html