红黑树

红黑树的性质

• 性质1：每个节点要么是黑色，要么是红色。
• 性质2：根节点是黑色。
• 性质3：每个叶子节点（NIL）是黑色。
• 性质4：每个红色结点的两个子结点一定都是黑色。
• 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

红黑树的添加

我们可以把红黑树看成是一个四阶b树来理解。对于添加来说，最后的节点一定

红黑红 红黑 黑红 黑 这四种，

如果添加到黑节点的话，不用操作

添加到红色节点的话，又分为添加到 黑红 红黑 和 红黑红两种

如果添加到红黑红的话，把黑色节点提到父节点上，然后递归调用add方法

如果是添加到红黑上面的话，就可通过旋转来完成

protected void afterAdd(Node<E> node) {
        
        Node<E> parent = node.parent;

        if(parent == null){ //如果父节点是空的话，说明此节点是根节点
            black(node);
            return;
        }

        if(isBlack(parent)) return;//这是只有黑的请况，不需要处理

        Node<E> uncle = node.sibling();
        Node<E> grand = parent.parent;
        
        if(isRed(uncle)){//这是红黑红的情况，此时节点已有3个元素，再添加一个就上溢了，把黑节点变成红色提到父节点上去
            //然后把其他节点拆开，红色节点都变成红色。父节点上有可能又会发生上溢，所以需要递归
            black(parent);
            black(uncle);
            red(grand);
            afterAdd(grand);
            return;
        }
        
        //这是红黑 或者黑红的情况，根据添加顺序的不同，分别进行旋转调节.
        //分为左左 ， 右右 ， 左右 ， 右左
        //分别进行右旋转 ， 左旋转 ， 左右旋转 ， 右左旋转
        if(parent.isLeftChild()){
            if(node.isLeftChild()){
                rotateRight(grand);
                red(grand);
                black(parent);
            }else{
                rotateLeft(parent);
                rotateRight(grand);
                black(node);
                red(grand);
            }
        }else{
            if(node.isLeftChild()){
                rotateRight(parent);
                rotateLeft(grand);
                red(grand);
                black(node);
            }else{
                rotateLeft(grand);
                red(grand);
                black(parent);
            }
        }
    }

红黑树的删除

删除分为3种情况，

当删除含有两个子节点的节点时，其实删的是这个节点的前驱或后继节点，所以被删除的元素一定是在4阶b树的最后一层上，也就是 红黑红 黑红 红黑 黑四种情况

当删除的是红色元素时，不会影响红黑树的结构，

当删除的是红黑红的黑色节点时，其实删除的是它的两个红色子节点中的一个。

当删除的 红黑 或黑红的黑色节点时，只需要把红色节点变成黑色就行.

当删除的是黑色节点时，就需要分多种情况了：

　　1.如果这个黑色叶子节点的兄弟节点是黑色的话

　　　　1.如果这个节点有红色子节点的话，通过旋转达到

　　　　2.如果没有红色子节点的话，就把父节点下溢.

　　2.如果兄弟节点时红色的话，就把红色节点的子节点当做是被删节点的兄弟节点，因此又回到了情况1.

    public void afterRemove(Node<E> node, Node<E> replacement) {
        Node<E> parent = node.parent;
        
        if(isRed(node)) return; //如果删除的是红色子节点，直接返回

        if(isRed(replacement)){//如果删除的是 红黑 和 黑红的情况 ， 直接把红色子节点变成黑色
            black(replacement);
            return;
        }

        if(parent == null) return; //如果此节点是根节点，直接返回

        boolean left = parent.left == null || node.isLeftChild(); //判断删除的是左节点还是有节点
        
        Node<E> sibling = left ? parent.right : parent.left; //被删除节点的兄弟节点
        if(left){
            //被删除的是左边节点
            //操作与被删除右边是对称的
        }else{
            //被删除的是右边节点
            if(isRed(sibling)){//如果它的兄弟节点是红色的话，通过右旋转父节点让红色节点的子节点变成被删的兄弟节点
                black(sibling);
                red(parent);
                rotateRight(parent);
                //更新兄弟节点
                sibling = parent.left;
            }

            //如果兄弟节点没有红色子节点的话，把父节点下移,如果父节点是黑色的话，需要递归
            if(isBlack(sibling.left) && isBlack(sibling.right)) {
                boolean parentBlack = isBlack(parent);
                black(parent);
                red(sibling);
                if (parentBlack) {
                    afterRemove(parent, null);
                }

            }else{//兄弟节点至少有一个红色子节点通过旋转达到目的，需要把sibling的颜色变成父节点的颜色
                if(isBlack(sibling.left)){
                    rotateLeft(sibling);
                    sibling = parent.left;
                }

                color(sibling,colorOf(parent));
                black(parent);
                black(sibling.left);
                rotateRight(parent);
            }
        }

    }