红黑树

性质：                                                                                                       1.节点是黑色或红色                                                                 2.根节点是黑色                                                                3.所有叶子节点(NIL节点)都是黑色                                              4.从根节点到每个叶子节点的所有路径不能有两个连续的红色节点       5.从任一节点到叶子节点的所有路径都包含相同数目的黑色节点

N

G

红黑树：二叉查找树的一种

U

P

假设删除的节点为D，删除节点的父节点为P，删除节点的兄弟节点为S，S的左儿子为SL，S的右儿子为SR

3.如果插入的节点N不是根节点（新节点N一定存在父节点P），当新节点N的父节点P是红色，叔父节点U是红色时                                                                                              （如果父节点P是红色，由于根节点一定是黑色，那么父节点一定不是根节点，从而推断出新节点N一定存在祖父节点，从而肯定有叔父节点（叔父节点有可能为叶子节点NIL））  

D

GG

S

针对父节点P做一次右旋然后按情形4-④来处理

将P和U变为黑色，G变为红色将G当成新插入的节点从情况1开始判断

GR

以S为中心左旋将S和SR变色变为情况2  

假设新节点为N，父节点为P，祖父节点为G，叔父节点为U

10

3.删除的节点既有左子树，又有右子树（这种情况可以转化为情况1或情况2，假设删除节点为D，只需用D的前驱节点或后驱节点的值替换掉要D， 然后删除D的前驱节点或后驱节点，此时D的前驱节点或后驱节点最多只有一个非空儿子，这时情况就变为情况1和情况2了） 

调整方法：此时需要针对父节点P进行一次左旋来调整新节点N和父节点P的位置，此时树不满足平衡树的性质，需要将父节点P当做新插入的节点按情形4-④来处理

SR

删除：

以S为中心右旋将S和SL变色变为情况2  

如果是由情况3演变而来，那么节点U一定不是NIL节点；

2.删除的节点为黑色，分为多种情况：

将P和S变色

4.如果插入的节点N不是根节点（新节点N一定存在父节点P），当新节点N的父节点P是红色，叔父节点U是黑色时                                                                                              （如果父节点P是红色，由于根节点一定是黑色，那么父节点一定不是根节点，从而推断出新节点N一定存在祖父节点，从而肯定有叔父节点（叔父节点有可能为叶子节点NIL））  

若D是P的左儿子，SR为黑色，SL为红色：以S为中心右旋，将S和SL变色，变为情况2  

SL

如有错误，请指正

以P为中心左旋 将P和S颜色调换  并将SR变为黑色 

①如果新节点N是父节点P的右子节点并且父节点P是祖父节点G的左子节点

若D是P的左儿子，SR为红色：以P为中心左旋，将P和S颜色调换(注意这里是颜色调换，而非变色，因为P的颜色未知)，并将SR变为黑色 

查找：和二叉查找树的查找一样

用N替换掉D然后将N变为黑色

以P为中心右旋 将P和S颜色调换  并将SL变为黑色 

按情况3调整后把节点G当成新节点出现了情况4

11

插入节点11仍满足红黑树性质不需要调整

调整方法：将S变色，把P当成删除黑色叶子节点的情况开始判断，只是不再删除P了

针对节点G做一次右旋将P变为黑色，G变为红色

7

调整方法：此时需要针对父节点P进行一次左旋，此时树不满足平衡树的性质，需要将父节点P当做新插入的节点按情形4-②来处理

1.删除的节点为红色，直接删除即可

注意：正常插入时节点U一定是NIL节点（否则会违反性质5）;

1.删除的节点是叶子节点 

若D是P的右儿子，SL为红色：以P为中心右旋，将P和S颜色调换(注意这里是颜色调换，而非变色，因为P的颜色未知)，并将SL变为黑色 

注意：新插入的节点都是红色的（如果是黑色的话，就会导致根节点到叶子节点的路径上多一个黑色节点，违反了性质5，这种情况是很难调整的；                            如果是红色的话，可能会导致两个连续红色节点的冲突，违反性质4，这种情况下可以通过变色和旋转来调整） 

③新节点N是父节点P的左子节点并且父节点P是祖父节点G的右子节点

调整方法：此时需要针对祖父节点G进行一次左旋，并将父节点P变为黑色，祖父节点G变为红色

将S变色把P当成删除黑色节点的情况开始判断只是不再删除P了

调整方法：将父节点P和叔父节点U变为黑色，祖父节点G变为红色

针对父节点P做一次左旋然后按情形4-②来处理

以下情况均是基于已经插入节点的基础上进行调整的（插入和普通的二叉查找树一样）

然后介绍情况1（删除的节点是叶子节点 ）：

调整方法：将P和S变色

2.如果插入的节点N不是根节点（新节点N一定存在父节点P），当新节点N的父节点P是黑色时，插入新节点N，这时树仍满足红黑树的性质。

12

GP

这里先介绍情况2（删除的节点只有左子树或只有右子树）：

调整方法：用删除节点D的非空儿子替换掉要D，然后将D的非空儿子变为黑色

二者调整方式相同，这里以正常插入时为例：

⑤若S为黑色，侄子节点都为黑色，P为黑色（此时侄子节点一定是NIL节点，否则违反性质5）

若D是P的左儿子：以P为中心左旋，并将P和S变色，然后变为情况②、③、④

GU

②新节点N是父节点P的左子节点并且父节点P是祖父节点G的左子节点

如果祖父节点G为根节点或G的父节点为红色，就违反了红黑树的性质，此时需要将祖父节点G当成新插入的节点从情况1开始重新判断

2.删除的节点只有左子树或只有右子树 

个人理解：将S变色之后，仍需调整，而调整的方法和删除黑色叶子节点后调整的方法一样，因此干脆将节点P当做删除黑色叶子节点的情况进行处理，只是不再删除P了

情况4

②若S为黑色，远侄子节点为红色

1.删除的节点为红色（这种情况是不可能存在的，违反红黑树的性质）

插入：

情况3

删除和二叉查找树一样分为3种情况：

性质4和5保证了从根节点到叶子节点的最长路径不超过最短路径的两倍

针对节点G做一次左旋将P变为黑色，G变为红色

以P为中心左旋并将P和S变色变为情况②、③、④

③若S为黑色，远侄子节点为黑色，近侄子节点为红色（此时远侄子节点一定是NIL节点，否则违反性质5）

调整方法：将N变为黑色

调整方法：此时需要针对祖父节点G进行一次右旋，并将父节点P变为黑色，祖父节点G变为红色

④若S为黑色，侄子节点都为黑色，P为红色（此时侄子节点一定是NIL节点，否则违反性质5）

④新节点N是父节点P的右子节点并且父节点P是祖父节点G的右子节点

①若S为红色（则P一定为黑色，并且SL和SR一定也为黑色）

如果D不是root节点，一定存在父节点P，并且S一定不为空（因为D为黑色，如果S为空，违反了性质5）

以P为中心右旋并将P和S变色变为情况②、③、④

若D是P的右儿子，SL为黑色，SR为红色：以S为中心左旋，将S和SR变色，变为情况2  

1.如果插入的节点N是根节点

如果D是root节点，直接删除即可

若D是P的右儿子：以P为中心右旋，并将P和S变色，然后变为情况②、③、④

2.删除的节点为黑色（那么它的左儿子或右儿子一定是红色）