算法第四版 - 红黑树的删除结点代码修改

最近在学习红黑树的时候，算法第四版没有给出对于结点删除过多的解释，着实费了一番功夫，在对进行删除操作的时候，发现书中代码有不少问题，现在对于删除最大键，最小健以及删除操作做出修改。

首先是颜色转换操作，这一部分与书中正文的插入操作的颜色转换不一样，书中习题以做说明

void moveflipColors(Node h ){   //  这是用于删除节点的flipColor方法，该方法用于节点的合并，将父节点中的部分给与子节点
        h.color = Black;            
        h.left.color = Red;       
        h.right.color = Red;
    }

下面是删除最小值的操作，在这里书中少了当我们从兄弟节点借了节点之后，我们需要把之前从父节点那里借的还给父节点，即在判断兄弟节点的内部多了moveflipColors(h)

    private Node moveRedLeft(Node h){
        /**
         * 当前节点的左右子节点都是2-节点，左右节点需要从父节点中借一个节点
         * 如果该节点的右节点的左节点是红色节点，说明兄弟节点不是2-节点，可以从兄弟节点中借一个
         */
        moveflipColors(h);     // 从父节点中借一个
        if(isRed(h.right.left)){    // 判断兄弟节点，如果是非红节点，也从兄弟节点中借一个
            h.right = rotateRight(h.right);
            h = rotateLeft(h);
            moveflipColors(h);  //  在从兄弟节点借了一个以后，我们就需要还一个节点给父节点了，因为一开始从父节点那里借了一个
        }
        return h;
    }
    
    public void deleteMin(){
        if(!isRed(root.left) && !isRed(root.right)){
            root.color = Red;   // 如果根节点的左右子节点是2-节点，我们可以将根设为红节点，这样才能进行后面的moveRedLeft操作，因为左子要从根节点借一个
        }
        root = deleteMin(root);
        root.color = Black;  // 借完以后，我们将根节点的颜色复原
    }
    
    private Node deleteMin(Node x){
        if(x.left == null) return null;
        if(!isRed(x.left) && !isRed(x.left))    // 判断x的左节点是不是2-节点
            x = moveRedLeft(x);
        x.left = deleteMin(x.left);
        return balance(x);  //   解除临时组成的4-节点
    }
    
    private Node balance(Node h){
        if (isRed(h.right)) h = rotateLeft(h);
        if (isRed(h.right) && !isRed(h.left)) h=rotateLeft(h);
        if (isRed(h.left) && isRed(h.left.left)) h=rotateRight(h);
        if (isRed(h.left) && isRed(h.right))    flipColors(h);
        h.total = size(h.left)+size(h.right)+1;
        return h;
    }

之后是对最大键的删除操作，与之前一样，少了对父结点的返还操作

    private Node moveRedRight(Node h){
        moveflipColors(h);
        if(isRed(h.left.left)){         // 在这里对于兄弟节点的判断都是.left，因为红色节点只会出现在左边
            h=rotateRight(h);
            moveflipColors(h);
        }
        return h;
    }
    public void deleteMax(){
        if(!isRed(root.left) && isRed(root.right)){
            root.color = Red;
        }
        root = deleteMax(root);
        root.color = Black;
    }
    
    private Node deleteMax(Node h){
        if(isRed(h.left)){             
        /**
         * 这里比deleteMin多了一步操作，因为右子节点从父节点中获得节点的时候，我们需要将左边节点给于到右边节点，如果我们不移动的话，会破坏树的平衡
         *          5,6
         *      1,2     9       对于所展示的这个红黑树，如果不把5从左边移到右边的话，我们会直接删除9，这样会导致树的不平衡，因为红节点总是在左边的，我们进行删除操作的时候，直接将结点给予，只需要改变颜色即可，不需要移动
         *                      对于红黑树而言，6是黑结点，再删除的时候，是不需要移动的，我们移动的是5这样的红结点
         *      
        */                                         
            h = rotateRight(h);
        }
        if(h.right == null){
            return null;
        }
        if(!isRed(h.right) && !isRed(h.right.left)){
            h = moveRedRight(h);
        }
        h.right = deleteMax(h.right);
        return balance(h);
    }

最后是删除操作，在这里，书中是key.compareTo(h.key) == 0 && h.right == null，我认为需要改成，key.compareTo(h.key) != 0 && h.right == null，即当我们找不到目标节点的时候，我们就返回null，个人觉得如果找到了目标节点，并且该节点没有右节点，并不能说服该结点不是一个2结点，直接删除很不合理，我还在之前k<h.key里也加入了判断，如果不存在目标键，我们也返回null

    public void delete(int key){
        if(!isRed(root.left)&& !isRed(root.right)){
            root.color = Red;
        }
        root = delete(root,key);
        root.color = Black;
    }
    
    private Node delete(Node h, int key){
        if(key<h.key){          // 当目标键小于当前键的时候，我们做类似于寻找最小是的操作，向树左边移动，合并父子结点来消除2-结点
            if(h.left == null){
                return null;
            }
            if(isRed(h.left) && !isRed(h.left.left)){
                h = moveRedLeft(h);
            }
            h.left = delete(h.left,key);
        }else{                  // 当目标键大于当前键的时候，我们向右移动，并做与deleteMax相同的操作，如果相同的话，我们使用和二叉树的删除一样的操作，获取当前键的右子树的最小健，然后交换，并将目标键删除
            if(isRed(h.left)){
                h = rotateRight(h);
            }
            if(key != h.key && h.right == null){    // 我们没有找到目标键，我们将其删除
                return null;
            }
            if(!isRed(h.right) && isRed(h.right.left)){
                h = moveRedRight(h);
            }
            if(key == h.key){
                h.val = get(h.right,min(h.right).key);
                h.key = min(h.right).key;
                h.right = deleteMin(h.right);
            }
            else h.right = delete(h.right,key);
        }
        return balance(h);
    }

这是对书中代码的修改，如果有错误请指正出来。