红黑树及源码的套路（下）

4. 删除后平衡

删除的方法声明中root不用多说，就是树的根节点，x并不是待删除的节点，而是替换的节点（replacement）。如果对树是如何删除节点不清楚的朋友这里不多做介绍。简单来说，当删除一个树节点的时候，会去找这个节点的后继节点或前置节点。以下图为例，删除节点13，那么它的前置节点是10，后继节点是20，所以删除的办法是用10或20与13节点交换。交换后我们需要把13（p）和23（replacement）交换，进而方便删除13节点。这样一来，20直接和23节点相连，针对23节点的颜色，可能会导致红黑树的不平衡，所以需要进行balanceDeletion

红黑树

我们这里讨论一下红黑树删除的场景，我们在删除一个节点的时候，它可能有无子节点、有一个子节点、有两个子节点，然后删除节点又有红/黑两种，所以总共有6个场景：
场景一：红色无子节点
直接删除即可
场景二：红色有一个子节点
无论这个子节点是红色还是黑色都不可能存在，因为违反了红黑树的平衡原则（可自己思考）
场景三：红色有两个子节点
如果存在两个子节点，所以可以从子节点中找到一个前置节点或后继节点来进行替换，从而将删除节点转移到子节点，又成为最多存在一个子节点的情况
场景四：黑色有一个子节点
首先如果子节点为黑色，不可能出现这种情况，读者可以仔细思考红黑树的平衡原则；
另外如果子节点为红色，则将红色节点替代黑色节点，然后红变黑即可
场景五：黑色有两个子节点
和场景三一样的逻辑
场景六：黑色无子节点
如果删除的节点就是黑色节点而无子节点，那么我们需要考虑一下，一旦删除，结果是它的兄弟子树中黑色偏多一个（原来肯定是一样的）。那么如果父节点是红色（其兄弟节点一定是黑色），将父节点红变黑，兄弟节点黑变红即可；如果父节点是黑色节点，那么可以确定的是父节点颜色不可以变动了，需要通过旋转匀一个黑色节点到被删除的子树上。
下面我们来读一下代码：
首先方法的声明

//root为整棵树的根节点，x为replacement节点
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                                   TreeNode<K,V> x)

            /**
              xp：父节点
              xpl：父左节点
              xpr：父右节点
            */
            for (TreeNode<K,V> xp, xpl, xpr;;)  {  //循环遍历
                if (x == null || x == root)
                    return root;  //如果这个节点是根节点或者为空，表示删除之后，树中仅剩一个replacement节点，也就是此时的root节点
                else if ((xp = x.parent) == null) {
                    x.red = false;
                    return x;  //？没明白这个第一个判断的区别在哪里
                }
                else if (x.red) {
                    x.red = false;  //如果replacement节点是红色，直接红转黑，因为它为红色，意味着之前与其关联的节点是黑色，现在黑色被删除，该分支黑色失衡，红转黑即可
                    return root;
                }

接下来的代码预设的是replacement节点为黑色

                else if ((xpl = xp.left) == x) {  //如果replacement节点是xp的左子节点
                    if ((xpr = xp.right) != null && xpr.red) {
/**如果replacement的兄弟节点存在且为红色，*/
                        xpr.red = false;  
                        xp.red = true;
                        root = rotateLeft(root, xp);
                        xpr = (xp = x.parent) == null ? null : xp.right;
                    }
                    if (xpr == null)
                        x = xp;
                    else {
                        TreeNode<K,V> sl = xpr.left, sr = xpr.right;
                        if ((sr == null || !sr.red) &&
                            (sl == null || !sl.red)) {
                            xpr.red = true;
                            x = xp;
                        }
                        else {
                            if (sr == null || !sr.red) {
                                if (sl != null)
                                    sl.red = false;
                                xpr.red = true;
                                root = rotateRight(root, xpr);
                                xpr = (xp = x.parent) == null ?
                                    null : xp.right;
                            }
                            if (xpr != null) {
                                xpr.red = (xp == null) ? false : xp.red;
                                if ((sr = xpr.right) != null)
                                    sr.red = false;
                            }
                            if (xp != null) {
                                xp.red = false;
                                root = rotateLeft(root, xp);
                            }
                            x = root;
                        }
                    }
                }