红黑树伤感操作(下篇)
删除
算法描述：
1. 找到删除的节点。
2. 如果该节点有2个孩子，则找到该节点的直接后继节点，并交换内容，继而删除后继节点，这时候后继节点要么是叶节点，要么只含有右子节点一个孩子，则会进入3,4两种情况加以考虑。
3. 如果该节点只含有一个孩子，就让孩子替换该节点。若该节点不可能是红色的(?红色的是第四种叶节点的情况)；若该节点是黑色的则导致黑高度降1，则用仅有的红色孩子替换染黑就可以(setColor(x, BLACK);)，见附图中的(1)
4. 如果该节点是叶子节点，若节点是红色直接的删除，若叶子节点是黑色的，删除之后需要调整平衡。以下分四种情况调整：[以下图中黑色即黑色，白色非黑即红，灰白色即红色]
1) 当前节点的兄弟节点是红色的，则父节点必为黑色的，调整方案如下，该方案还要进一步使用2) 3) 4)调整，以便最后删除A节点。
2) 当前节点的兄弟节点以及兄弟的两个孩子也是黑色的，其实这种情况分2种情况加以考虑，分别如附图中的(2-4)和(3-4)。
a) 附图(2-4)的调整是平衡的，删除完毕。
b) 附图(3-4)的调整使黑高度降1，需要以父节点为删除节点向上继续调整……
3) 当前节点的兄弟节点是黑色的，父亲非黑即红，兄弟节点的右孩子是黑色的，方案是以D节点为轴右旋染色，之后进入4)步继续调整，附图情况有2种，分别如附图中(2-1)和(3-1)。
思虑黑洞
算法描述中的α，β，γ，ε，ζ可能都是外部节点，如附图中考虑的那样；也可能都是具有相同黑高度的内部节点。考虑2)-b中的情况，当前删除节点向上继续调整的时候，α，β，γ，ε，ζ就会都是有黑高度的内部节点，我们可以自己举例思考向上调整的过程，在向上的调整过程中，遇到了删除结束的条件，这样就完成了一次删除。咳咳，自己考虑……
代码实现:
主要关注调整代吗：
private void fixAfterDeletion(Entry<K,V> x) {
while (x != root && colorOf(x) == BLACK) {
if (x == leftOf(parentOf(x))) {
Entry<K,V> sib =rightOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) ==BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(rightOf(sib))== BLACK) {
setColor(leftOf(sib),BLACK);
setColor(sib, RED);
rotateRight(sib);
sib =rightOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x),BLACK);
setColor(rightOf(sib),BLACK);
rotateLeft(parentOf(x));
x = root;
}
} else { // symmetric
Entry<K,V> sib =leftOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) ==BLACK &&
colorOf(leftOf(sib)) ==BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) ==BLACK) {
setColor(rightOf(sib),BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib =leftOf(parentOf(x));
}
setColor(sib,colorOf(parentOf(x)));
setColor(parentOf(x),BLACK);
setColor(leftOf(sib),BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
}
附图：
对D节点的删除都是在平衡的基础上进行的删除，图中除了3.4 需要继续调整平衡外，其余情况均都在图中的展示得以平衡。
转载请注明出处。
参考：
https://blog.****.net/qq_37169817/article/details/78880110