[toc]
红黑树是一种含有红黑节点并能自平衡的二叉查找树
性质如下：
- 每个节点要么是黑色，要么是红色
- 根节点是黑色
- 每个叶子节点是黑色（这里的叶子节点是指为空的（NIL或NULL）的叶子节点）
- 每个红色节点的两个子节点一定都是黑色
- 任意一节点到每个叶子节点的路径都包含数量相同的黑节点
- 如果一个节点存在黑色子节点，那么该节点肯定有两个子节点
简单的红黑树如下：
我们把正在处理的节点叫做当前节点，它的父亲叫做父节点，它的父亲的另外一个子节点叫做兄弟节点，父亲的父亲叫作祖父节点。
红黑树能够平衡最主要靠三种操作：左旋、右旋和变色：
- 左旋：以某个节点作为支点（旋转节点），其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转子节点的右子节点，左节点保持不变
- 右旋：以某个结点作为支点（旋转结点），其左子节点变为旋转节点的父节点，左子节点的右节点变为旋转节点的左子节点，右节点保持不变
- 变色：节点的颜色由红变黑或由黑变红
左旋只影响旋转节点和右子树的结构，把右子树的节点往左子树挪了
右旋只影响旋转节点和左子树的结构，把左子树的节点往右子树挪了
旋转操作是局部的，由此可以看出红黑树保持平衡的一些端倪：当一边子树的节点变少了，那么另外向一边子树“借”一些节点，当一边子树节点多了，那么向另外一边子树“租”一些节点。
不能乱挪，还得靠变色
红黑树总是通过旋转和变色达到自平衡
红黑树是一颗平衡二叉树，并且不会破环树的平衡，所以与查找二叉平衡树无异：
- 从根节点开始，把根节点设置为当前节点
- 若当前节点为空，返回null
- 若当前节点不为空，用当前节点的key跟查找key做比较
- 若当前节点key等于查找key，那么就是查找目标，返回当前节点
- 若当前节点key大于查找key，把当前节点的左子节点设置为当前节点，重复步骤2
- 若当前节点key小于查找key，把当前节点右子节点设置为当前节点，重复步骤2
红黑树的查找最坏时间复杂度为O(2logN)*
包括两部分工作，一查找插入的位置，二插入后自平衡，查找插入的父节点很简单，跟查找区别不大：
- 从根节点开始查找；
- 若根节点为空那么插入节点作为根节点，结束
- 若根节点不为空，那么把根节点作为当前节点
- 若当前节点为null，返回当前节点的父节点，返回当前节点的父节点，结束
- 若当前节点key等于查找key，那么该节点就是插入节点，更新插入节点的值，结束
- 若当前节点key大于查找key，把当前节点左子节点设置为当前节点，重复步骤4
- 若当前节点key小于查找key，把当前节点右子节点设置为当前节点，重复步骤4
这里的key可以理解为键值对的key
插入的节点着色为红色，因为不会违背性质5，从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点，因为如果插入的节点是黑色节点，那么必须做自平衡操作。
直接把插入节点作为根节点就行，但注意，红黑树性质2，根节点是褐色，还需要把插入节点设为黑色
处理：把插入节点作为根节点，并把节点设置为黑色
插入节点的key已存在，既然红黑树总保持平衡那么把插入节点设置为将要替代节点的颜色，再把节点的值更新完成就插入
处理：
- 设为当前节点的颜色
- 更新为当前节点的值为插入节点的值
由于插入的节点是红色的，当插入的节点为黑色，并不会影响红黑树的平衡，直接插入即可
如果插入的父节点为红节点，那么该父节点不可能为根节点，所以插入节点总是存在祖父节点。
祖父节点一定为红节点，因为不可能存在两个相连的红节点
此时该插入子树的红黑层数情况是：黑红红，显然最简单的处理方式是把其改为红黑红
处理：
- 将P和S设置为黑色
- 将PP设置为红色
- 将PP设置为当前插入节点
如果PP的父节点是黑色，那么无需再做处理，如果PP的父节点是红色，根据性质4，此时红黑树已经不平衡了，还需要把PP当作新的插入节点，继续做插入操作自平衡处理，知道平衡为止。
如果刚好为根节点，根据性质2，必须把PP重新设置为黑色，那么此时红黑树结构为黑黑红。换句话说，根节点到叶子节点的路径中，黑色节点增加了（本来是黑红，即只有根节点是黑色的，插入之后变成了黑黑红），这也是唯一一种会增加红黑树黑色节点层数的插入场景。
红黑树的生长是自底向上的，而普通的二叉查找树是自顶向下的
处理：
- 将P设置为黑色
- 将红色
- 对PP进行右旋
处理：
- 对P进行左旋
- 把P设置为插入节点，得到情景4.2.1
- 进行4.2.1的处理
处理：
- 对P进行右旋
- 将P设置为插入节点，得到4.3.1
- 进行4.3.1的处理
红黑树删除也包括两种操作，一是查找目标节点；二删除后自平衡。
查找目标节点显然可以复用查找操作，当不存在目标节点时，忽略本次操作；当存在目标节点时，删除后就得做自平衡处理了。删除了节点后我们还需要找节点来替代删除节点的位置，不然子树跟父辈节点断开了，除非删除节点刚好没有子节点，那么就不需要替代
二叉树删除节点替代节点有三种情形：
- 若删除节点无子节点，直接删除
- 若删除节点只有一个子节点，用子节点替换删除节点
- 若删除节点有两个子节点，用后记节点（大于删除节点的最小节点）替换删除节点
情景三的后继节点是大于删除节点的最小节点，也是删除节点的右子树中最左节点。
删除节点被替代后，在不考虑节点键值的情况下，对于树来讲，可以认为删除的是替代节点
基于此，上面所说的三种二叉树删除操作最后都会互相转换最终都是转换成情景1
- 情景2：删除节点用唯一的子节点替换，子节点替换为删除节点后，可以认为删除的是子节点，若子节点又有两个子节点，那么相当于转换为情景三，一直自顶向下转换，总是能转换为情景1
- 情景3：删除节点用后继节点（后继节点肯定不存在左节点，否否则无需转换），如果后继节点有右节点那么相当于转换为情景2，如果后继节点有右子节点，那么转换为情景2，否则转换为情景1
二叉树节点情景关系如图：
综上所述：删除操作删除的节点可以看作删除替代节点，而替代节点最后总是在树末
红黑树删除的所有操作：
约定以下：
图中字母并不代表节点key大小，P代替节点，P表示代替节点的父节点，S表示代替节点的兄弟节点，SL表示兄弟节点的左子节点，SR表示兄弟节点的右子节点，灰色节点表示它可以是红色也可以是黑色
R是即将被替换到删除节点位置的替代节点，在删除前，他还在原来所在的位置参与二叉树的平衡，平衡后再替换到删除节点的位置，才算删除完成
我们把替换节点换到了删除节点的位置时，由于替换节点时为红色，删除了也不会影响红黑树的平衡，只要把替换节点的颜色设为删除的节点的颜色即可重新平衡
处理：颜色变为删除节点的颜色
当替换节点是黑色节点，删除后可能会违反性质5，所以我们必须进行自平衡处理。还必须考虑替换节点是其父节点的左子节点还是右子节点，来做不同的旋转，以使树重新平衡
处理：
- 将S设置为黑色
- 将P设置为红色
- 对P进行左旋，得到情景2.1.2.3
- 进行情景2.1.2.3的处理
此时R仍然是替代节点，它的新兄弟节点SL和兄弟节点的子节点都是黑色
父节点和子节点的颜色未确定，所以又分为几种情况：
处理：
- 将S颜色设为P的颜色
- 将P设为黑色
- 将SR设置黑色
- 对P进行左旋
如果考虑第一次替换的情况SL，根据红黑树的性质4，SL一定是红色，如果考虑到自底向上的情况，每颗子树都保持了平衡状态，整棵树是平衡的。
处理：
- 将S设置为红色
- 将SL设置为黑色
- 对S进行右旋，得到情景2.1.2.1
把兄弟节点设为红色，再把父节点当作替代节点，自底向上处理，去找父节点的兄弟节点去借红节点。
处理：
- 将S设为红色
- 把P作为新的替换节点
- 重新进行节点删除处理
与2.1相反
处理：
- 将S设置为红色
- 将P设置为红色
- 对P进行右旋，得到情景2.2.2.3
- 进行情景2.2.2.3的处理
处理：
- 将S设为P的颜色
- 将P设置为黑色
- 将SL设置为黑色
- 对P进行右旋
处理
- 将S设为红色
- 将P设为黑色
- 将S进行左旋，得到情景2.2.2.1
- 进行情景2.2.2.1的处理
处理：
- 将S设置为红色
- 把P作为新的替换节点
- 重新进行删除节点情景处理
