在上一篇插入节点分析中已经提过，红黑树的插入节点相对于AVL树来讲，需要的调节平衡的操作比较少，一方面表示红黑树的平衡定义与AVL树不同，另一方面也说明了红黑树不是严格意义上的平衡树，即查询操作不是严格的O(log n)。不过带来的好处则是需要的调节操作少，在插入、删除节点时具有较少的性能消耗，也就是所谓的统计性能较好。
回顾一下红黑树的五个特性：
1.节点颜色为红或者为黑
2.根节点为黑
3.叶子节点为黑（叶子作为结束标志，可以以空表示或者自定义实体节点作为结束标志，后面树中没有画出来）
4.红色节点必须有两个黑色子节点（子节点可以为结束标志）
5.任一节点出发到叶节点路径上包含相同数量的黑色节点
因为删除操作很多依赖于特性5，所以需要记熟。
由AVL树中的删除过程可知，给出的待删除的节点，在执行时可能实际删除的只是它的“替身”，而对原来要删除的节点只是更改了它的值而已。这里所说的过程也就是，当待删除节点的左右子节点都存在（不是表示结束的叶子节点），则找到该节点的左子树最大值节点或者右子树的最小值节点，将该极值节点的值赋值给待删除节点，然后删除该极值节点。
当待删除节点没有同时包含左子节点和右子节点，则当前节点即为极值节点（以该节点为根的子树中，该节点即为此子树范围内的极值）。也就是说，当该节点无子节点或者只有一个子节点时，该节点即为极值节点。
下面讨论的待删除节点都是待删除的极值节点。待删除节点已经确定为某个极值点后，则开始进行平衡检查工作，平衡检查的起始节点即为该待删除节点，如果不能一次检查通过，则更换检查节点，迭代进行平衡检查，检查通过后，删除待删除节点（不是当前的检查节点）。
代码演示：
选择极值点：
void delete(node root,int value){//根据值来删除节点 while(root.value!=value){//找到删除位置 if(value<root.value){ root=root.left; }else{ root=root.right; } } int temp=find_the_point(root).value; root.value=temp; root=find_the_point(root);//是否要给待删除的节点找替身 index=root;//指定要删除的节点 delete_check(root);//删除检查 delete_dir(index);//检查完成，删除节点 } node find_the_point(node t){//是否要给待删除的节点找替身 if(children_number(t)==2){//两个孩子都有，则找替身，并返回替身 return min_right(t.right);//返回左子树的最大值 } return t; } int children_number(node t){//返回子节点个数 int c=0; if(t.left!=null){ c++; } if(t.right!=null){ c++; } return c; } node min_right(node t){//返回右子树的最小值 while(t.left!=null){ t=t.left; } return t; }
情景演示
类似与节点插入的演示，在删除节点之前，先描述一个删除场景
x：待删除节点，f：父节点，s：兄弟节点，sr：兄弟节点右孩子
通过以f节点为根，进行左旋转，将f节点的颜色赋予s节点，f节点变为黑。能够实现的是：右边一条线黑色节点数不变，左边黑色节点树加一，从而可以实现删除节点x，不会导致特性5不符。
情形0：当前检查节点为红色节点。
由待删除节点为极值节点，最多一个子节点，由特性4，5可知，如果待删除节点为红色，则该节点无子节点，删除不影响树的平衡，此时检查平衡完成。
情形1：当前检查节点为黑色节点，只有一个子节点存在时
当前检查节点最多只有一个子节点，由特性5可知，该子节点为红
此时，无论x的子节点是左子节点或者右子节点，只需要将子节点的值赋予自身即可，更改待删除节点为子节点，完成检查。
代码演示：
删除红色子节点：
void delete_and_take(node t){//以子节点变色代替，其实就是用了子节点的值，还删了子节点 if(t.left!=null){ t.value=t.left.value; index=t.left; return; } if(t.right!=null){ t.value=t.right.value; index=t.right; return; } if(t.parent==null){ root=t; } }情形2：当前检查节点为黑色节点，父节点存在，兄弟节点为黑
当前检查节点为黑色节点时，因为删除会导致特性5不符，需要进行平衡调节。删除根据兄弟节点的情形如下
情形2.1：当兄弟节点存在红色子节点时
通过旋转变色操作保持以父节点为根的子树部分，保持整体平衡性，完成检查，具体场景如下
情形2.1.1：当兄弟节点右孩子为红色节点时，如上面情景演示，通过变色左旋即可
情形2.1.2：当兄弟节点左孩子为红色节点时，先进行变色右旋，再进行左旋
代码演示：
兄弟节点存在红孩子：
void left_or_right(node s){//具有至少一个红色节点,此时的s是待删除节点的兄弟节点 if(check_for_side(s)){//s是父节点的左节点 if(s.left!=null){ s.left.color=false; s.color=s.parent.color; s.parent.color=false;; right_rotate(s.parent); return; } if(s.right!=null){//根据特性5，s有子节点的话，子节点为红 s.right.color=s.parent.color; s.parent.color=false; s=left_rotate(s); right_rotate(s.parent); return; } }else{//s是父节点的右节点 if(s.right!=null){//根据特性5，s有子节点的话，子节点为红 s.right.color=false;//右孩子变为黑色 s.color=s.parent.color;//将父节点的颜色换给s s.parent.color=false;//父节点颜色变为黑色 left_rotate(s.parent); return; } if(s.left!=null){ s.left.color=s.parent.color; s.parent.color=false; s=right_rotate(s); left_rotate(s.parent); return; } } }
情形2.2：当兄弟节点不存在红色子节点时
该情形下采用的一种方式，类似于“上诉”的场景，将父节点作为新的检查节点，迭代进行平衡检查。根据父节点的颜色，进行颜色变换，当前步骤不需要进行旋转。有以下两种情形：
情形2.2.1：父节点为红
当父节点为红时，将兄弟节点变为红，父节点变为黑，则f-s路线上黑色节点个数不变，f-x待删除路线上黑色节点个数加一，删除节点x不会导致特性5不符，保持整体平衡性，完成检查。
情形2.2.2：父节点为黑
通过将兄弟节点变为红，维持以f为根的子树内部平衡性，即局部平衡，此时f为新的待检查节点，进行迭代平衡检查。
情形3：当前检查节点为黑色节点，父节点存在，兄弟节点为红
当兄弟节点s为红，对f，s进行变换颜色，以f节点为根作左旋转。以上图中的左右侧来说，旋转前f右侧的子树，与旋转后s右侧的子树，黑色节点数不变，不存在特性5不符。但是检查点x换做新的检查点x（虽然指向的节点不变，但是环境已经改变）。
所以此次的调节操作目的在于，对同样的检查点提供新的检查环境（以当前为例，旋转之后，如果sl节点存在红孩子，则根据情形2.1，最多再两次旋转即可解决问题；如果sl节点没有红孩子，则根据情形2.2.1，一次旋转都不用，只需要变个色即可解决问题）。
代码演示：
兄弟节点为红：
/* 兄弟节点为红，则父节点黑，兄弟节点的子节点为黑 */ void delete_s_red(node t){//兄弟节点为红 node s=brother(t); s.color=false;//兄弟节点变为黑色 s.parent.color=true;//父节点变为红色 if(check_for_side(t)){//如果t是左节点 t=left_rotate(s.parent);//左旋 delete_check(t.left.left); }else{//右节点，则右旋 t=right_rotate(s.parent); delete_check(t.right.right); } }
情形4：当前检查节点为黑色节点，父节点不存在，两个子节点都存在时
当前检查节点为根节点，并且两个子节点都存在，则很明显由下层迭代检查到根节点，此时不作处理，检查平衡完成（例如由情形2.2.2的“上诉”，如果上诉到根节点，则表示以根节点作为的根节点的子树内部保持局部平衡性，也就是说整个树都是平衡的）。
删除节点时进行判断，选择待执行的调节操作。
代码演示：
插入节点检查：
void delete_check(node t){//删除检查 if(t.parent!=null){//不是根节点 if(t.color){//为红色节点,且无子节点 return; } if((t.left==null&&t.right!=null)||(t.left!=null)&&t.right==null){//只有一个子节点 delete_and_take(t); return; } node s=brother(t);//获取t的兄弟节点 if(s.color){//兄弟节点为红 delete_s_red(t);//旋转 }else{//兄弟节点为黑 if((s.left!=null&&s.left.color)||(s.right!=null&&s.right.color)){//兄弟有红孩子 left_or_right(s); }else{//没有孩子或者有黑孩子 s.color=true;//变为红 if(s.parent.color){//如果父节点为红，置为黑，结束 s.parent.color=false; }else{ if(s.parent.parent!=null){//父节点不为根节点 delete_check(s.parent); } } } } }else{//根节点 if(root.left!=null){ root.value=root.left.value; root.left=null; return; } if(root.right!=null){ root.value=root.right.value; root.right=null; return; } root=null; } }
在该代码中做了一点优化，在情形2.2.2中的“上诉”中，直接判断是否是根节点，如果是根节点则检查完成，而没有以新的检查点再次执行平衡检查操作。
由以上的操作可知，红黑树的平衡相对于AVL树来说不是特别严禁的，但是带来的好处则是调节平衡操作的简洁性。插入节点最多需要进行两次旋转即可达到平衡，删除节点最多需要三次旋转即可平衡。
示例：
以12 ,1 ,9 ,2, 0, 11, 7, 19, 4 ,15, 18 ,5 ,14, 13 ,10, 16 ,6, 3, 8, 17作为插入节点和删除节点测试
插入删除完整代码如下：
public class t{ public static void main(String[] args){ int[] arr=new int[]{12 ,1 ,9 ,2, 0, 11, 7, 19, 4 ,15, 18 ,5 ,14, 13 ,10, 16 ,6, 3, 8, 17}; tree tr=new tree(); for(int i:arr){ tr.insert(i); } for(int i=0;i<16;i++){ tr.delete(arr[i]); } System.out.println("=========================="); tree.pre_show(tr); } } final class node{//简单起见，所有设置属性的方法省略，提供直接访问 boolean color=true;//构造默认颜色红色，true表示红色，false表示黑色 int value=0;//键值 node left=null;//左孩子 node right=null;//右孩子 node parent=null;//父节点 node(int value){ this.value=value; } } final class tree{ static node index=null; node root=null; tree(){} void insert(int value){ if(root==null){//这里的root表示根节点 root=new node(value); root.color=false;//设置根节点的颜色为黑色 }else{ insert(root,value); } } void insert(node root,int value){//插入节点 node temp=null;//记录父节点 boolean left=false;//记录新节点在父节点tmep的左右哪边 while(root!=null){//找到插入位置 while(root!=null&&value<root.value){//左边找 temp=root; root=root.left; left=true; } while(root!=null&&value>root.value){//右边找 temp=root; root=root.right; left=false; } if(root!=null&&root.value==value){ System.out.println("include the same value!"); break; } } node t=new node(value);//创建该节点 if(left){//设置父节点一边的孩子 temp.left=t; }else{ temp.right=t; } t.parent=temp;//设置新节点的父节点 insert_check(t);//插入检查 } void delete(int value){ delete(root,value); } void delete(node root,int value){//根据值来删除节点 while(root.value!=value){//找到删除位置 if(value<root.value){ root=root.left; }else{ root=root.right; } } int temp=find_the_point(root).value; root.value=temp; root=find_the_point(root);//是否要给待删除的节点找替身 index=root;//指定要删除的节点 delete_check(root);//删除检查 delete_dir(index);//检查完成，删除节点 } node find_the_point(node t){//是否要给待删除的节点找替身 if(children_number(t)==2){//两个孩子都有，则找替身，并返回替身 return min_right(t.right);//返回左子树的最大值 } return t; } int children_number(node t){//返回子节点个数 int c=0; if(t.left!=null){ c++; } if(t.right!=null){ c++; } return c; } node min_right(node t){//返回左子树的最大值 while(t.left!=null){ t=t.left; } return t; } void delete_check(node t){//删除检查 if(t.parent!=null){//不是根节点 if(t.color){//为红色节点,且无子节点 return; } if((t.left==null&&t.right!=null)||(t.left!=null)&&t.right==null){//只有一个子节点 delete_and_take(t); return; } node s=brother(t);//获取t的兄弟节点 if(s.color){//兄弟节点为红 delete_s_red(t);//旋转 }else{//兄弟节点为黑 if((s.left!=null&&s.left.color)||(s.right!=null&&s.right.color)){//兄弟有红孩子 left_or_right(s); }else{//没有孩子或者有黑孩子 s.color=true;//变为红 if(s.parent.color){//如果父节点为红，置为黑，结束 s.parent.color=false; }else{ if(s.parent.parent!=null){//父节点不为根节点 delete_check(s.parent); } } } } }else{//根节点 if(root.left!=null){ root.value=root.left.value; root.left=null; return; } if(root.right!=null){ root.value=root.right.value; root.right=null; return; } root=null; } } void delete_and_take(node t){//以子节点变色代替，其实就是用了子节点的值，还删了子节点 if(t.left!=null){ t.value=t.left.value; index=t.left; return; } if(t.right!=null){ t.value=t.right.value; index=t.right; return; } if(t.parent==null){ root=t; } } /* 兄弟节点为红，则父节点黑，兄弟节点的子节点为黑 */ void delete_s_red(node t){//兄弟节点为红 node s=brother(t); s.color=false;//兄弟节点变为黑色 s.parent.color=true;//父节点变为红色 if(check_for_side(t)){//如果t是左节点 t=left_rotate(s.parent);//左旋 delete_check(t.left.left); }else{//右节点，则右旋 t=right_rotate(s.parent); delete_check(t.right.right); } } void left_or_right(node s){//具有至少一个红色节点,此时的s是待删除节点的兄弟节点 if(check_for_side(s)){//s是父节点的左节点 if(s.left!=null){ s.left.color=false; s.color=s.parent.color; s.parent.color=false;; right_rotate(s.parent); return; } if(s.right!=null){//根据特性5，s有子节点的话，子节点为红 s.right.color=s.parent.color; s.parent.color=false; s=left_rotate(s); right_rotate(s.parent); return; } }else{//s是父节点的右节点 if(s.right!=null){//根据特性5，s有子节点的话，子节点为红 s.right.color=false;//右孩子变为黑色 s.color=s.parent.color;//将父节点的颜色换给s s.parent.color=false;//父节点颜色变为黑色 left_rotate(s.parent); return; } if(s.left!=null){ s.left.color=s.parent.color; s.parent.color=false; s=right_rotate(s); left_rotate(s.parent); return; } } } void delete_dir(node t){//当前节点为红，则直接删除 if(t.parent==null){//根节点的话 root=null; t=null; return; } if(t==t.parent.left){ t.parent.left=null; }else{ t.parent.right=null; } } void insert_check(node t){//插入检查 if(t.parent==null){//如果问题已经上升到根节点，则就是check的最后一步 t.color=false;//下层都已经整理好，直接改根节点为黑色 root=t; }else{ if(t.parent.color){//父节点存在，且为红 if(uncle(t)!=null&&uncle(t).color){//如果叔节点存在且为红 check_case1(t);//叔节点为红 }else{ check_case2(t);//叔节点为黑 } } } } /* check_case1解决问题，父节点红色，则祖父节点为黑色，叔节点为红色的情况 */ void check_case1(node t){//叔节点为红 node uncle=uncle(t); t.parent.color=false;//父节点变黑 uncle.color=false;//叔节点变黑 uncle.parent.color=true;//祖父节点变红 insert_check(uncle.parent);//以祖父节点作为新的检查点 } /* check_case2解决问题，父节点红色，则祖父节点为黑色，叔节点不为红色的情况 直接插入新节点不会出现这种情况，因为祖父节点到叔节点和到父节点情况，违背红黑树特性5 所以这种情况是由check_case1变化颜色导致的 */ void check_case2(node t){//叔节点为黑 if(t==t.parent.right&&t.parent==grandparent(t).left){//左右拐弯 t=left_rotate(t.parent);//以父节点为根左旋，将新的父节点返回 t.color=false; t.parent.color=true; t=right_rotate(t.parent);//以父节点为根右旋，将新的父节点返回 }else if(t==t.parent.left&&t.parent==grandparent(t).right){//右左拐弯 t=right_rotate(t.parent);//以父节点为根右旋，将新的父节点返回 t.color=false; t.parent.color=true; t=left_rotate(t.parent);//以父节点为根左旋，将新的父节点返回 }else if(t==t.parent.left&&t.parent==grandparent(t).left){//左边一条道 t.parent.color=false; t.parent.parent.color=true; t=right_rotate(grandparent(t));//以祖父节点为根右旋 }else if(t==t.parent.right&&t.parent==grandparent(t).right){ t.parent.color=false; t.parent.parent.color=true; t=left_rotate(grandparent(t));//以祖父节点为根左旋 } } /* 当父节点存在时，判断当前节点是父节点的左子节点或者右子节点 返回true表示左，false表示右 */ boolean check_for_side(node t){ return t==t.parent.left?true:false; } node left_rotate(node t){//以t为根节点，左旋 node par=t.parent; node t_rig=t.right; boolean l=false; if(par!=null){ l=check_for_side(t); } t.right=t_rig.left; if(t_rig.left!=null){ t_rig.left.parent=t; } t_rig.left=t; t.parent=t_rig; t_rig.parent=par; if(par!=null){ if(l){ par.left=t_rig; }else{ par.right=t_rig; } } if(t_rig.parent==null){ root=t_rig; } return t_rig; } node right_rotate(node t){//以t为根节点，右旋 node par=t.parent; node t_lef=t.left; boolean l=false; if(par!=null){ l=check_for_side(t); } t.left=t_lef.right; if(t_lef.right!=null){ t_lef.right.parent=t; } t_lef.right=t; t.parent=t_lef; t_lef.parent=par; if(par!=null){ if(l){ par.left=t_lef; }else{ par.right=t_lef; } } if(t_lef.parent==null){ root=t_lef; } return t_lef; } node grandparent(node t){//获取t的祖父节点 return t.parent.parent; } node brother(node t){//返回兄弟节点 return t==t.parent.left?t.parent.right:t.parent.left; } /* 获取t的叔节点，这里没有判断祖父节点是否存在的情况 */ node uncle(node t){// node g=grandparent(t); return t.parent==g.left?g.right:g.left; } static void pre_show(tree tr){//前序遍历树 pre_show(tr.root); } static void pre_show(node root){//前序遍历树 if(root!=null){ System.out.println("value:"+root.value+",color:"+(root.color==true?"-----------------":"black")); pre_show(root.left); pre_show(root.right); } } }
参考：https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91
