红黑树03——节点的插入与删除-步骤与示例.md

2019-02-17 本文已影响28人 readyou

0. 前言

我们采用nil代替null来简化操作。如果你之前学过，有一些印象，那跟随本文从上到下画一画插入与删除的全过程，将大大地加深你的印象与熟练程度。

插入和删除的主逻辑，与前面的文章——红黑树01——前传-二叉搜索树中基本一致，只是特别处理了一下nil。最大的不同是，当插入结点和它的父结点都为红色时，违反了红黑树的属性，需要重新调整，共有3种情况（本来是6种，因为是对称的，所以只讨论一半）；删除结点时若涉及到黑结点的删除（或替换），会导致一侧黑结点数目减少，违反了红黑树的规则，所以也需要调整，共有4种情况。

本章内容比较长，如果看得吃力了，可以停下，回头再看。但长不可怕，可怕的是看不懂，我尽可能地把那些操作的前因后果讲清楚，希望大家能耐心看下去。经过测试，我指导过的同学，能轻松记住整个过程，且能写出来全部代码。一定要坚持看完弄懂，请相信我，欠下的债迟早要还的。

1. 插入后的调整

为了便于说明，设新插入结点为x，x的父结点为p，p的兄弟结点为pb，x父结点的父结点为pp，pb的左孩子为pbl, pb的右孩子为pbr。因为对称性，我们这里只讨论p == pp.left的情况。已经x和p当前均为红色，pp肯定为黑色。

因为有两个红色结点，我们需要把其中一个变成黑色，变黑的肯定不是x，因为新插入的结点是红色（为什么新插入的是红色呢，因为如果不插入红色的话，那就没有红色了。但为什么不担心没有黑色了呢？因为我们在调整的过程中，会把根置为黑色，所以能保证一定有黑色，另外前面也说了会把p变成黑色），所以变黑的是p。

但这样就多了一个黑色，解决办法有两个，办法1是pb也由红变黑，pp由黑转红，这样两边都一增一减就平衡了。办法2是pp由黑转红，但这样右边会少一个黑色。我们上一篇文章说过旋转就是为了解决这个问题的，所以我们把pp右旋（思考题：变红的pp会不会违反性质？）。

分类	描述	处理方式	后续说明
1	pb为红色	将p和pb置为黑色，pp颜色置为红色，x指向pp，进行下一轮循环判断。	pp由黑变红，可能会违反不能有连续两个红结点的规则，故循环继续。
2	pb为黑色，x、p、pp不在一条直线上	p左旋，使之在一条直线上	转化为情况3。
3	pb为黑色，x、p、pp不在一条直线上	p变黑，pp变红，pp右旋	已经平衡，结束。

    private void insertFixup(Node node) {
        while (node.parent != nil && node.parent.color == RED) {
            Node p = node.parent;
            // 因为父节点为红色，而根节点为黑色，所以父节点肯定不为根，故祖父节点存在，所以这里不需要判断为nil。
            Node pp = node.parent.parent;
            if (pp.left == p) {
                Node pb = pp.right;
                if (pb.color == RED) {
                    insertFixUpStats[0]++;
                    p.color = BLACK;
                    pb.color = BLACK;
                    pp.color = RED;
                    node = pp;
                    continue;
                }

                if (node != p.left) {
                    insertFixUpStats[1]++;
                    rotateLeft(p);
                    node = p;
                    p = node.parent;
                }
                insertFixUpStats[2]++;
                p.color = BLACK;
                pp.color = RED;
                rotateRight(pp);
            } else {
                Node pb = pp.left;
                if (pb.color == RED) {
                    insertFixUpStats[0]++;
                    p.color = BLACK;
                    pb.color = BLACK;
                    pp.color = RED;
                    node = pp;
                    continue;
                }

                if (node != p.right) {
                    insertFixUpStats[1]++;
                    rotateRight(p);
                    node = p;
                    p = node.parent;
                }
                insertFixUpStats[2]++;
                p.color = BLACK;
                pp.color = RED;
                rotateLeft(pp);
            }
        }
        root.color = BLACK;
    }

2. 删除

当黑色结点被替代者替换时，会导致黑色结点的缺失而违反性质4，我们需要对替代者做一些处理，使树恢复平衡。设被删除的结点为x，x的左孩子为xl(left)，右孩子为xr(right)，x的后继为s(successor)，后继的右孩子为sr，替代者为r(replacement)，被替代的颜色为rc(replacedColor)，x的父结点为p，x的兄弟节点为b，b的左右孩子分别为bl, br。

因为删除调整也是对称的，下面我们只讨论x == p.left的情况。

2.1 确定替代者与被替代的颜色

如果xl或xr不存在时，直接把xr或xl替换x即可，故r为xr或xl，rc为x.color；否则转2。
如果xr == s，则只发生一次替换：s -> x，故r为s，rc为x.color。
如果xr != s，则发生两次替换：sr -> s, s -> x。我们保留x位置的颜色不变，则在颜色上的替换只有一次：sr -> s，我们只需要调整一个结点的黑色结点问题，此时r为s.right，rc为s.color。

2.2 调整替代者

因为少了一个黑色的结点，前人发明了一招来治标：假设r指针附带了一层额外的黑色（这个黑色是跟着r指针走的，当r向上移动的时候，这层黑色也会跟着走），这样少的那个黑色又加回来了。但怎么治本呢？我们需要把r上移到某个红色位置，然后再强制给r加上黑色，让虚拟的黑色转为实在的黑色，从而达到治本的效果。当然当r已经到根了，那就直接把根置黑就完事了。

那要怎样才能让r移动呢？答案是不断地制造冲突，是的，要搞点事情出来才能打破僵局，不破不立嘛。一个原则：不能减少左边结点上的黑色（只能将r上移来减少虚拟的黑色）。

首先区分出4种情况：按b的颜色可分为两种情况，而b为黑时，又根据bl, br的颜色，可分为全黑、左红、右红3种情况（为什么不考虑全红：因为单独考虑左红、右红已经包含全红了。另外，右红经过左旋可转化为左红，是的，跟上面插入时一样，如果不在一条直线上则旋转到一条直线上）。然后再逐个攻破。

情况1：如果b为红色，则p、bl和br都为黑色。因不能连续两红，故p、bl、br都不能变色，唯一能变化的只能是b，故将其置为黑色，这样右边又多了一个黑色，现在多了2个黑色；那就把p置红（这里为什么敢置红呢？先试试嘛，万一不行不变就是了，恰好接下来的左旋操作，使得p的父亲变成黑色的b，所以不会出现两个红色），右边黑色数目恢复，但左边又少了一个黑色。那就p左旋（对，旋转就是用来将一边的颜色添加到另一边的），这时b的黑色作用到两边使左右两边的黑色数目都恢复。另外p左旋导致原来的bl成了p.right，成为x的新兄弟，且bl是黑色的，故转换为情况2/3/4的一种。
情况2：b, bl, br都为黑色，但bl, br不能置红（因为它们的子结点不知道什么情况，如果是红色的就会出现两个连续红色从而违反红黑树的性质），同样p不知道什么颜色，故唯一能变化的只能是b变红。这样右边少一个黑色，将r上移指向p，相当于给右边添加了一层虚拟的黑色，恢复平衡。于是进入下一次循环继续判断。
情况3：b为黑色，bl为红色，因p, b, bl不在一条直线上，故b置红，bl置黑，右旋b，再重置b，转为情况4。
情况4：b为黑色，br为红色，则p, b, br在一条直线上，这个时候怎么搞事情呢？因为br是红色，所以b不能再变红，而bl和p颜色不确定，所以也不能直接修改颜色。故只能将br置黑，则右边多了一个黑色。因为不能将p置红来减少右边的黑色，唯一能做的就是想办法把b的黑色弄到左边去。首先想到的就是左旋p，但如果p是黑色的，左旋p会导致右边黑色减1左边加1，最终左边黑色数目比右边多2（算上那个虚拟黑色），所以不能直接左旋p。我们试着交换p和b的颜色，再左旋p，则p原来的颜色还在右边，b的黑色成功置换到左边了。但现在左边又多了一个黑色，我们把r移走，指向root，则总体平衡了（右边黑色一加一减不变，左边增加了一个），结束处理。

所以将来大家记不住4种情况分别是什么时，不妨自己在纸上画画，强迫自己搞点事情出来，再逐步恢复之前的局势，想必能帮助你想起来。

分类	描述	处理方式	后续说明
1	b为红	b置黑，p置红，左旋p，重置b，继续	转化为情况2/3/4的一种
2	b, bl, br均为黑	b置红，r指向p，继续	2和3、4是排他的，而3和4在同一次循环操作中
3	b为黑，bl为红	b置红，bl置黑，右旋b，再重置b	转化为情况4
4	b为黑，br为红	br置黑，p, b互换颜色，左旋p，r指向root	结束

    private void deleteFixUp(Node node) {
        while (node != root && node.color == BLACK) {
            Node parent = node.parent;
            if (node == parent.left) {
                Node brother = parent.right;
                if (brother.color == RED) {
                    deleteFixUpStats[0]++;
                    brother.color = BLACK;
                    parent.color = RED;
                    rotateLeft(parent);
                    brother = parent.right;
                }

                // 因为有哨兵nil，所以这里不需要判断brother.left是否存在。
                if (brother.left.color == BLACK && brother.right.color == BLACK) {
                    deleteFixUpStats[1]++;
                    brother.color = RED;
                    node = parent;
                } else {
                    if (brother.left.color == RED) {
                        deleteFixUpStats[2]++;
                        brother.left.color = BLACK;
                        brother.color = RED;
                        rotateRight(brother);
                        brother = parent.right;
                    }

                    deleteFixUpStats[3]++;
                    // 旋转与变色是相互独立的，所以顺序不是固定的，随意就行。不妨把下面这句rotateLeft(parent)换个地方试试。
//                    rotateLeft(parent);
                    brother.color = parent.color;
                    parent.color = BLACK;
                    brother.right.color = BLACK;
                    rotateLeft(parent);
                    node = root;
                }
            } else {
                Node brother = parent.left;
                if (brother.color == RED) {
                    deleteFixUpStats[0]++;
                    brother.color = BLACK;
                    parent.color = RED;
                    rotateRight(parent);
                    brother = parent.left;
                }

                if (brother.left.color == BLACK && brother.right.color == BLACK) {
                    deleteFixUpStats[1]++;
                    brother.color = RED;
                    node = parent;
                } else {
                    if (brother.right.color == RED) {
                        deleteFixUpStats[2]++;
                        brother.right.color = BLACK;
                        brother.color = RED;
                        rotateLeft(brother);
                        brother = parent.left;
                    }

                    deleteFixUpStats[3]++;
                    brother.color = parent.color;
                    parent.color = BLACK;
                    brother.left.color = BLACK;
                    rotateRight(parent);
                    node = root;
                }
            }
        }
        node.color = BLACK;
    }