两个大前提：
- 红黑树还是查找树，为了查找方便，左小右大；
- 保证树的矮胖结构，所以红色节点 向上融合之后，树是均衡的。
0、来源
红黑树的本质还是二叉树，但是因为二叉树很容易产生倾斜问题，所以有了一种平衡二叉树——2-3树，2-3树的每个节点可能有2个子节点（以下称为2节点），也可能有3个子节点（以下称为3节点），当新增节点的时候，有以下几种状况：
- 若查找到的节点为2节点，则直接添加子节点，或升为3节点即可；
- 若查找到的节点为3节点，则插入后会变成4节点，则4节点向上拆分为3节点即可；
- 若查找到的3节点的父节点，也是3节点，则可能一路上升到根节点，这是唯一可以增加树高度的情况。
所以由此可见，只有第三种情况会增加树高度，而查找的复杂度是由树高度决定的，所以2-3树是一种平衡二叉树。
而红黑树本质上与2-3树完全一致，只是表示方式不同。
1、基本概念
红黑树的根本是二叉树，它有五个特性：
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
基本操作
左旋：将旋转节点设置成为右子节点的左子节点，并将原右子节点的左子节点设为旋转节点的右节点。
右旋：将旋转节点设置 成为左子节点 的右子节点，并将原左子节点的右节点设为旋转节点的左节点。
http://blog.csdn.net/xiangzhihong8/article/details/51589032
