红黑树：本质上他是一个二叉搜索树，所以他满足二叉搜索输的基本性质——即任何节点的值大于它的左子节点，小于它的右子节点。不同于普通的二叉树，红黑树是自平衡的（局部平衡，不同于AVL树的严格平衡）
一、红黑树性质（核心思想）：
1.节点只有红色或黑色
2.根节点是黑色
3.每个叶子结点都带有两个空的黑色结点（被称为黑哨兵，即NIL节点），如果一个结点n的只有一个左孩子，那么n的右孩子是一个黑哨兵；如果结点n只有一个右孩子，那么n的左孩子是一个黑哨兵。
4.红节点的两儿子都是黑色的，即红节点不相邻
5.树上任一节点，从该节点到其叶节点的所有路径上都包含相同的黑节点（包括NIL节点）
二、红黑树中每个节点拥有的属性：
1.颜色， 2.值， 3.父节点指针， 4.左子节点指针， 5.右子节点指针
三、树的旋转
左旋，如图所示（左->右），以x->y之间的链为“支轴”进行，使y成为该新子树的根，x成为y的左孩子，而y的左孩子则成为x的右孩子。
右旋，同理
note1：旋转都是以根节点为视角的，比如左旋方法 LEFT-ROTATE(T, pivot)，这个参数pivot，就是上图左侧的X节点，而不是Y节点（约定熟成的规矩）
note2：有些书上有双旋这个概念，其实双旋转就是做了两次单选，本质是相同的
四、树中插入元素
从根节点开始，按照左小右大的规则一步步查找合适的插入点。
找到后，将需要插入的元素作为红节点代替原位置的黑哨兵（NIL节点）。
然后修复因为插入引起的不平衡。
note：之所以将新插入点定义为红节点，这时因为这样能最少程度减少对原树的破坏(红节点有可能会破坏性质4，但如果插入黑节点，那肯定会破坏性质5)
代码等待补充
五、插入修复
插入后有3种情况：
情况1：插入前是空树，这种情况下，只违反了性质2,
措施：直接涂黑
情况2：插入元素的父节点是黑色的，这时树仍然平衡（最简单的情况）
情况3：插入元素的父亲是红色的，这时只违反了性质5，这种情况又分为3种：
case1：插入元素的叔叔是红色的，
措施：将父亲和叔叔涂黑，爷爷涂红，然后将爷爷作为新的插入点case2：插入元素的叔叔是黑的，并且插入元素是它父亲的右儿子
措施：以它父亲为pivot，进行左旋，然后将父亲作为新的插入点，进入case3case3：插入元素的叔叔是黑的，并且它是左儿子
措施：将他父亲涂黑，爷爷涂红，然后以爷爷为pivot，进行右旋
（note：情况3考虑的是插入元素的父亲是它爷爷的左儿子，如果是右儿子的话，操作想法，思想不变）
修复思想：把每次多出来的红色往上推，直到根节点，如果还是红色，就直接把跟节点变黑（相当于把红色推到树外面去了）
这里说一下我个人的两个理解(我称之为上推)：
理解1：当一个元素和它的兄弟（它父亲的另一个子节点）同色时，如果这时它父亲和他们不同色，那么可以把他们的颜色和它父亲的颜色相交换，这时子树仍然符合红黑树性质。（不考虑父节点和祖父节点都是红色的情况）
理解2：当一个元素和它的兄弟（它父亲的另一个子节点）同色时，如果这时它父亲和他们同色，这时可以把他们的颜色给他父亲，他们自己变成另一种颜色。也就是说，这个过程后，它父亲拥有了双重颜色。
e.g.1
这时如果把点22和27的红色上推，那么点25就变成了红色，22、27变成黑色；不考虑25的父亲17，25这颗子树仍然平衡。（用于分析元素插入）。
e.g.2:
如果把点4和14的黑色上推，那么点9就变成双重黑色，点4、14变成红色（但无论左支还是右支，黑色节点仍然是两个）。（这个思想用于分析元素删除时会很有用）
删除以及遍历部分，不好意思，小弟还在编辑中，大家稍等哈
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) | 黑马程序员IT技术论坛 X3.2 |
