【算法】红黑树删除数据（最后一步，平衡红黑树）（五）

删除节点确实比添加节点更为复杂

而且最可怕的是，在我学习添加节点的时候，很多文章我觉得写的有些些乱，然鹅，我在删除节点的时候，情况更多，我看得更乱了，所以我还是秉持着，一遍学习概念和方法，一遍看看java源码中是如何来处理这些操作的！所以本文也会以java的TreeMap源码为主，来解释下如何处理红黑树删除后的平衡！

 

1、首先有两种情况是不需要平衡的，比如删除的是红色节点，删除的是根节点，所以这两种情况我们就可以排除掉了

2、删除的节点是黑色的，那就会导致删除的那条分支少一个黑色节点！

因此我们就进入了平衡

情况1-1：删除的节点是黑色，他的兄弟节点是红色（因为兄弟节点是红色，所以P点不可能是红色）

情况1-1-1：被删除的子节点没有孩子

SL和SR肯定是有黑色节点的，否则删除前就不平衡了。

删除前，左边是两个黑色节点，右边也是两个，删除后平衡后，左边还是两个，右边也两个（其实做的操作就是把兄弟的孩子借过来了）

情况1-1-2：被删除的子节点有孩子（只可能是有一个孩子，并且是右孩子）

首先说下，为什么说只可能有一个孩子，因为要删除的点P，在是否寻找找继承人的时候，需要做判断，如果点P有两个孩子，那就找继承人，继承人是点P右子树中最小的，也就是说，如果继承人有子节点，那只可能是有右孩子，因为如果是有左孩子的话，那左孩子才会是继承人（才会是右子树中最小的那个）！

 

你会发现，删除前左边3个黑色节点（因此右边应该也是3个，我没有具体画出来），平衡后，似乎还是没有满足红黑树的规则，别急，这种情况就得进入到下一层迭代

我们来先看看情况1-1的代码

//TreeMap类的2301行开始
 private void deleteEntry(Entry<K,V> p) {
        modCount++;
        size--;

        // If strictly internal, copy successor's element to p and then make p
        // point to successor.
        if (p.left != null && p.right != null) {
            Entry<K,V> s = successor(p);
            p.key = s.key;
            p.value = s.value;
            p = s;
        } // p has 2 children

        // Start fixup at replacement node, if it exists.
        Entry<K,V> replacement = (p.left != null ? p.left : p.right);

        if (replacement != null) {
            // Link replacement to parent
            replacement.parent = p.parent;
            if (p.parent == null)
                root = replacement;
            else if (p == p.parent.left)
                p.parent.left  = replacement;
            else
                p.parent.right = replacement;

            // Null out links so they are OK to use by fixAfterDeletion.
            p.left = p.right = p.parent = null;

            // Fix replacement
            if (p.color == BLACK)
		//这里调用了第一次fixAfterDeletion，就是情况1-1-2，有孩子的情况
                fixAfterDeletion(replacement);
        } else if (p.parent == null) { // return if we are the only node.
            root = null;
        } else { //  No children. Use self as phantom replacement and unlink.
            if (p.color == BLACK)
		//这里调用了第二次fixAfterDeletion，就是情况1-1-1，没有孩子的情况
                fixAfterDeletion(p);

            if (p.parent != null) {
                if (p == p.parent.left)
                    p.parent.left = null;
                else if (p == p.parent.right)
                    p.parent.right = null;
                p.parent = null;
            }
        }
    }

    /** From CLR */
    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));
		//情况1-1！！兄弟节点如果是红色
                if (colorOf(sib) == RED) {
		    //兄弟节点变黑
                    setColor(sib, BLACK);
		    //父亲变红
                    setColor(parentOf(x), RED);
		    //根据父亲节点左旋
                    rotateLeft(parentOf(x));
		    //重新给定兄弟节点
                    sib = rightOf(parentOf(x));
                }
			//这后面还有一大段代码，我们先不急着看！
            }
        }
        setColor(x, BLACK);
    }

总结下：所以经过情况1-1下面的两种情况，处理方式都是一样的，都会把SL当成新的叔叔，只是没有孩子的情况就不需要继续处理了（因为平衡了），有孩子的情况还得继续往下处理

 

情况1-2：删除的节点的兄弟节点是黑色（因为D和S都是黑色，所以无法确定P点的颜色，但是P的颜色不影响整体）

如果兄弟节点是黑色，那就得看兄弟节点的孩子的情况了

情况1-2-1：兄弟节点有两个黑色的孩子（这里其实也分D有没有孩子，但是其实处理是一样的，所以就不画出来了）

我们知道左边删了一个节点，少了一个黑色，那只要右边拿过来一个，或者右边直接少一个黑色节点就可以了，因此这里的做法是右边少一个黑色节点（直接把兄弟变成红色），然后进入下一次迭代

注：进入下一次迭代，删除的节点就变成P点（x = parentOf(x);），如果P是红色，就违背了红黑树的规则，因此源码中有最后一行（setColor(x, BLACK);），如果P是黑色，那就继续迭代判断

代码如下：

 

 

情况1-2-2：否则（并不是两个孩子都为黑色），如果右孩子是黑色