1.简介
红黑树是一种自平衡二叉查找树。它的统计性能要好于平衡二叉树（AVL树），因此，红黑树在很多地方都有应用。在C++ STL中，很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除等操作。
本文介绍了红黑树的基本性质和基本操作。
2.红黑树的性质
红黑树，顾名思义，通过红黑两种颜色域保证树的高度近似平衡。它的每个节点是一个五元组：color（颜色），key（数据），left（左孩子），right（右孩子）和p（父节点）。
红黑树的定义也是它的性质，有以下五条：
性质1. 节点是红色或黑色
性质2. 根是黑色
性质3. 所有叶子都是黑色（叶子是NIL节点）
性质4. 如果一个节点是红的，则它的两个儿子都是黑的
性质5. 从任一节点到其叶子的所有简单路径都包含相同数目的黑色节点。
http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91