目录
前言
上一篇文章 红黑树的插入.中讲了如何向红黑树中插入节点，今天写红黑树中删除节点，相比于插入节点，删除节点要复杂的多，我会尽力说明白的，如果当中有什么问题，请随时指正～
先回顾一下红黑树的性质
红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何特定的红黑树我们增加了如下的额外要求:
1 节点是红色或黑色。
2 根节点是黑色。
3 每个叶节点（这里的叶节点是指NULL节点）是黑色的。
4 从每个叶子到根的所有路径上不能有两个连续的红色节点。
5 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
首先先说一下我们要删除节点的类型
我们知道，对于一棵普通的二叉排序树来说，删除的节点情况可以分为3种：
1 叶子节点
2 只有左子树或只有右子树的节点
3 既有左子树又有右子树的节点。
我们的做法就是，如果要删除既有左子树又有右子树的节点，我们首先要找到该节点的直接后继节点或前驱节点（本篇文章利用的是后继节点），然后用后继节点替换该节点，最后按1或2中的方法删除后继节点即可。
所以情况3可以转换成情况1或2。
我这次写的是只有一种，想一想为什么只有一种呢？我也学习了很多优秀的博客，要删除的节点类型从大的方面来说都是有两种，也就是上面的说法3可以转换为1或者2:
1 单个的叶子节点（不是指NULL节点，就是二叉排序树中的叶子节点的概念）
2 只有右子树（或只有左子树）的节点
我这次的做法是将2也转化为1，意味着终点就是找到一个叶子为止，所以说相当于删除节点只有一种类型，那就是，意味着删除的节点颜色不是黑色，就是红色。
在删除之前我想说一下，就是当我们删掉一个节点的时候，我们要考虑的和插入节点是一样的，就是是不是破坏了红黑树的性质，如果破坏了，那我们要做的就是平衡修复，所以主要要做的就是如何保持在删除了节点还让这棵红黑树是满足要求的。好，那就进入正题了，看下面????????
一 删除节点为红色：
你们是不是想的也是直接删除呢，如果是这样，那恭喜你想对了，原因很简单，少一个红色对红黑树的5个性质并没有什么影响，所以可以直接删除。
二 删除节点为黑色：
在删除节点颜色是黑色的时候，我希望大家能记住一句话就是，先看他兄弟节点的颜色，再看侄子节点的颜色（侄子节点先看远侄子再看近侄子），最后看父亲节点的颜色，不要感觉这些关系很乱，先看一张图片，让你清晰的理解一下，把握记住好这一点，对于理解删除有很大的帮助
假设D为要删除的节点，那么S就是他的兄弟，P是他的父亲，SL是他的近侄子，SR是他的远侄子
情况1：待删除节点D的兄弟节点S为红色
注意：当兄弟为红色时，待删节点的侄子和父亲只能是黑色，因为不能有两个连续的红色出现
D是左节点的情况
分析一下，当我们吧D删掉之后，P的左子树是不是就少一个黑色，那是不是意味着就破坏了红黑树的性质（从根节点到任一叶子节点的路径上黑色节点的个数是相同的,所以我们的做法就是：
将父亲节点和兄弟节点的颜色互换，也就是p变成红色，S变成黑色，然后将P树进行以P的左旋（如何旋转可以看插入的博客介绍☝????）操作结果如下图：
这样我们就将D的兄弟变成了黑色，也就是后面要介绍的情况????????：
D是右节点的情况
做法相同就是旋转方向不同，先将P和S的颜色互换，也就是将P变成红色，将S变成黑色，然后对P右旋。结果如下图：
同样我们就将D的兄弟变成了黑色，也就是后面要介绍的情况????????：
情况2：兄弟节点为黑色，且远侄子节点为红色。
D为左孩子对的情况，这时D的远侄子节点为S的右孩子
没有上色的节点表示黑色红色均可。
这个时候，如果我们删除D，这样经过D的子节点（NULL节点）的路径的黑色节点个数就会减1，但是我们看到S的孩子中有红色的节点，如果我们能把这棵红色的节点移动到左侧，并把它改成黑色，那么就满足要求了，这也是为什么P的颜色无关，因为调整过程只在P整棵子树的内部进行调整过程为：
将P和S的颜色对调，然后对P树进行右旋的操作，最后把SR节点变成黑色，并删除D即可。
交换颜色后接着右旋后，左边就多一个黑色但右边就少一个黑色，所以就把原来红色的也就是远侄子改成黑色就行，然后在删除D就完美啦！如下图：
D为右孩子的情况，此时D的远侄子为S的左孩子
同样，将P和S的颜色对调，然后再对P树进行左旋的操作，最后将SL变成黑色，并删掉D即可。结果如下图：
情况3：兄弟节点S为黑色，远侄子节点为黑色，近侄子节点为红色
D为左孩子的情况，此时近侄子节点为S的左孩子
这种情况就不能直接和上面的做法一致了，因为这个红色节点在进行旋转后会到删除的那一边（左边），相当于右边就不能通过变SL的颜色来增加右边的黑色使之平衡了。所以既然不能直接利用的上面的做法那我就先把你变成上面的样子在进行你的操作不就行了，调整如下：
先将S和SL的颜色互换，在以S进行右旋，这个时候就变成了情况2,所以只要在进行一次平衡修复就可以了。
D为右孩子的情况，此时近侄子节点为S的右孩子
做法同样是将S和SR颜色对调，然后对S进行左旋操作，这样就变成了情况4，结果如下图：
情况4：父亲节p为红色，兄弟节点和兄弟节点的两个孩子都为黑色(或者都为NULL)的情况。
如果删除D，那经过P到D的子节点NULL的路径上黑色就少了一个，这个时候我们可以把P变成黑色，这样删除D后经过D子节点（NULL节点）路径上的黑色节点就和原来一样了。但是这样会导致经过S的子节点（NULL节点）的路径上的黑色节点数增加一个，所以这个时候可以再将S节点变成红色，这样路径上的黑色节点数就和原来一样啦！所以做法是：
将父亲节点P改成黑色，将兄弟节点S改成红色，然后删除D即可。如下图：
情况5：父亲节点p，兄弟节点s和兄弟节点的两个孩子都为黑色(或者两个孩子都是NULL)的情况
方法是将兄弟节点S的颜色改成红色，这样删除D后P的左右两支的黑节点数就相等了，但是经过P的路径上的黑色节点数会少1，这个时候，我们再以P为起始点，继续根据情况进行平衡操 （这句话的意思就是把P当成D（只是不要再删除P了，再看是哪种情况，再进行对应的调整，这样一直向上，直到新的起始点为根节点）结果如下图：
至此，所有的情况都讨论完了，总结一下就是，删除会有好几种情况，这几种情况会有转换的关系，最终就是转成为能直接删除掉的，这样说是不会会好理解一点，其实这也是为什么红黑树比AVL应用更广的原因了，红黑树的删除旋转操作最多只需要进行3次就可以成功删除了，所以比AVL的效率更高一些。最后再来总结最开始的一句话，判断类型的时候，先看待删除的节点的颜色，再看兄弟节点的颜色，再看侄子节点的颜色（侄子节点先看远侄子再看近侄子），最后看父亲节点的颜色。把握好这一点，写代码思路也就清晰了。
代码如下：
/**
* 删除操作
* @param key
*/
public void delete(RBNode<AnyType> root,AnyType key) {
RBNode<AnyType> root1 = root;
while (root1 != null) {
int cmp = key.compareTo(root1.key);
if (cmp > 0) {
root1 = root1.rightChild;
} else if (cmp < 0) {
root1 = root1.leftChild;
} else {
if (root1.leftChild == null && root1.rightChild == null) {
//叶子为红
if (root1.getColor().equals(RED)) {
if (root1.parent != null) {
//可能删除
if (root1.parent.leftChild == root1) {
root1.parent.leftChild = null;
} else {
root1.parent.rightChild = null;
}
} else {
this.root = null;
}
} else {
deleteFix(root1,root1.key);
}
} else if (root1.leftChild != null && root1.rightChild != null) {
//待删除双儿子
RBNode<AnyType> replaceNode = this.findMin(root1.rightChild);
root1.key = replaceNode.key;
delete(root1.rightChild,root1.key);
} else {
if(root1.leftChild != null) {
root1.key = root1.leftChild.key;
delete(root1.leftChild,root1.key);
} else {
root1.key = root1.rightChild.key;
delete(root1.rightChild,root1.key);
}
}
return ;
}
if (root1 == null) {
System.out.println("没有该节点,删除失败");
break;
}
}
}
/**
* 平衡修复
* @param rbNode
* @param Key
*/
public void deleteFix (RBNode < AnyType > rbNode, AnyType Key){
if (rbNode.parent == null) {
rbNode.setColor(BLACK);
return;
}
String s = null;
if (rbNode == rbNode.parent.leftChild) {
s = "0";
} else {
s = "1";
}
if (s.equals("0")) {
//待删节点在左边
RBNode<AnyType> brother = rbNode.parent.rightChild;
//兄弟为红色
if (brother.getColor().equals(RED)) {
rbNode.parent.setColor(RED);
brother.setColor(BLACK);
leftRotation(rbNode.parent);
deleteFix(rbNode, Key);
} else {
//兄弟为黑色
//兄弟的两个孩子为空或者都是黑色
if ((brother.leftChild == null && brother.rightChild == null) || (brother.leftChild != null && brother.rightChild != null
&& brother.leftChild.getColor().equals(BLACK
) && brother.rightChild.getColor().equals(BLACK))) {
brother.setColor(RED);
//兄弟的两个孩子为空或者都是黑色，父亲为红色
if (brother.parent.getColor().equals(RED)) {
brother.parent.setColor(BLACK);
brother.setColor(RED);
//针对向上调整不再删除的情况，下面的同这一条
if(rbNode.key == Key){
rbNode.parent.leftChild = null;
}
} else {
//兄弟的两个孩子为空或者都是黑色，父亲为黑色
if(rbNode.key == Key) {
rbNode.parent.leftChild = null;
}
brother.setColor(RED);
deleteFix(brother.parent, Key);
}
//远侄子为红色
} else if (brother.rightChild != null && brother.rightChild.getColor().equals(RED)) {
String color = brother.parent.getColor();
brother.parent.setColor(BLACK);
brother.setColor(color);
leftRotation(brother.parent);
brother.rightChild.setColor(BLACK);
if(rbNode.key == Key) {
rbNode.parent.leftChild = null;
}
//近侄子为红色
} else if (brother.leftChild != null && brother.leftChild.getColor().equals(RED)) {
String color = brother.leftChild.getColor();
brother.leftChild.setColor(brother.getColor());
brother.setColor(color);
rightRotation(brother);
deleteFix(rbNode, Key);
}
}
} else {
//待删结点在右边
RBNode<AnyType> brother = rbNode.parent.leftChild;
//兄弟为红色
if (brother.getColor().equals(RED)) {
rbNode.parent.setColor(RED);
brother.setColor(BLACK);
rightRotation(rbNode.parent);
deleteFix(rbNode, Key);
} else {
//兄弟为黑色
//兄弟为黑色，两个侄子都是黑或者都是空
if ((brother.leftChild == null && brother.rightChild == null) || (brother.leftChild != null && brother.rightChild != null
&& brother.leftChild.getColor().equals(BLACK
) && brother.rightChild.getColor().equals(BLACK))) {
//兄弟为黑色，两个侄子都是黑或者都是空，母亲为红色
if (rbNode.parent.getColor().equals(RED)) {
rbNode.parent.setColor(BLACK);
brother.setColor(RED);
if(rbNode.key == Key) {
rbNode.parent.rightChild = null;
}
} else {
//兄弟为黑色，两个侄子都是黑或者都是空，母亲为黑色
if(rbNode.key == Key) {
rbNode.parent.rightChild = null;
}
brother.setColor(RED);
deleteFix(brother.parent, Key);
}
//远侄子为红色
} else if (brother.leftChild != null && brother.leftChild.getColor().equals(RED)) {
String color = brother.parent.getColor();
brother.parent.setColor(BLACK);
brother.setColor(color);
rightRotation(brother.parent);
brother.leftChild.setColor(BLACK);
rbNode.parent.rightChild = null;
//近侄子为红色
} else if (brother.rightChild != null && brother.rightChild.getColor().equals(RED)) {
String color = brother.rightChild.getColor();
brother.rightChild.setColor(brother.getColor());
brother.setColor(color);
leftRotation(brother);
deleteFix(rbNode, Key);
}
}
}
}
到此红黑树的插入和删除就结束啦！
可以到这个链接去验证自己的插入和删除是否正确????????
验证红黑树
我的红黑树整体代码
红黑树的应用敬请期待