这篇讲的非常好
http://blog.csdn.net/liuzhanchen1987/article/details/7325376
红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
也就是说，不存在两个红的，连在一起。
每次一个节点插入的时候，默认是红色。然后根据一定的情况进行调整。
1. 如果父是黑的，不需调整。
2. 如果父是红的，叔叔是红的，那么祖父变成红的，父和叔变成黑的。然后针对祖父进行调整。
3. 如果父是红的，叔叔是黑的。如果当前节点，父，和祖父，不在同一个方向，比如当前是父的右，父是祖父的左，
那么，当前变父，父变当前的左。这样方向就一致了。
4. 上面3的情况，也会被调整成这个：当前，父，和祖父，在同一个方向，比如都是左子树，
那么右旋，父成为 当前 和 祖父 的父节点，原来当前和父是红的，祖父是黑的，变成 当前 和 祖父是红的，父是黑的。
原文：http://www.cnblogs.com/charlesblc/p/6501938.html