从2-3-4树开始理解红黑二叉树（JAVA代码手撸版）

经典的红黑二叉树在新增/删除数据时维持自平衡始终对应着一个2-3-4 树。本文只关注2-3-4 对应的经典红黑二叉树。
暂时不考虑 2-3 树对应的左倾红黑二叉树。

背景知识

2-3-4 树简介

一棵 2-3-4 树的结点分为 内部结点 (internal nodes) 和 叶子结点 (leaf nodes) ，定义如下。
内部结点:

• 2-结点: 拥有1个数据项x，2个子结点。

  • 左子树中任意结点数据项均小于x。
  • 右子树中任意结点数据项均大于x。

• 3-结点: 拥有2个数据项x,y，3个子结点。

  • 左子树中任意结点数据项均小于x。
  • 中间子树中任意结点数据项均介于x与y之间。
  • 右子树中任意结点数据项均大于y。

• 4-结点: 拥有3个数据项x,y,z，4个子结点。

  • 左子树中任意结点数据项均小于x。
  • 左侧中间子树中任意结点数据项均介于x与y之间。
  • 右侧中间子树中任意结点数据项均介于y与z之间。
  • 右子树中任意结点数据项均大于z。

• 叶子结点: 无子结点，数据项为 1 项或 2 项或 3项。

2-3-4 树节点变换

插入操作一定是插入叶子节点中，然后根据情况进行调整。

红黑树5条性质

左旋

以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树挪了。

java 代码实现如下(带图解)

/**
 *
 * @param p
 */
void rotate_left(RbNode p) {
    // 1.处理当前节点的父节点
    if (p.parent == null) {
        this.root = p.right;//1
    } else if (p.parent.left != null && p.parent.left.val == p.val) {
        p.parent.left = p.right;//1
    } else {
        p.parent.right = p.right;//1
    }

    // 2.处理历史右子节点。（当前父节点）
    p.right.parent = p.parent;//2
    RbNode rightLeftNode = p.right.left;
    p.right.left = p;//3

    // 3. 处理当前节点
    p.parent = p.right;//4
    p.right = rightLeftNode;//5

    // 4.处理历史右节点的左子节点
    if (rightLeftNode != null) {
        rightLeftNode.parent = p;//6
    }
}

右旋

以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。右旋只影响旋转结点和其左子树的结构，把左子树的结点往右子树挪了。

java 代码实现如下(可优化)

/**
 *
 * @param p
 */
void rotate_right(RbNode p) {
    // 1.处理当前节点的父节点
    if (p.parent == null) {
        this.root = p.left;//1
    } else if (p.parent.left != null && p.parent.left.val == p.val) {
        p.parent.left = p.left;//1
    } else {
        p.parent.right = p.left;//1
    }

    // 2.处理历史左子节点。（当前父节点）
    p.left.parent = p.parent;//2
    RbNode leftRightNode = p.left.right;
    p.left.right = p;//3

    // 3. 处理当前节点
    p.parent = p.left;//4
    p.left = leftRightNode;//5

    // 4.处理历史左节点的右子节点
    if (leftRightNode != null) {
        leftRightNode.parent = p;//6
    }
}

查询某节点的后继节点

依据二叉树中序遍历，查找当前节点的后续节点（寻找继承人）

  RbNode findSuccessorNode(RbNode curNode) {
    if (curNode == null) {
        return null;
    }

    //1. 向下搜索-> 当前节点有 右子节点(红黑二叉树删除节点只使用到这里逻辑).
    if (curNode.right != null) {
        RbNode mySuccessorNode = curNode;
        while (mySuccessorNode.left != null) {
            mySuccessorNode = mySuccessorNode.left;
        }
        return mySuccessorNode;
    }

    //2. 向上搜索-> 当前节点没有 右子节点.
    RbNode parent = curNode.parent;
    //如果没有父节点，则当前节点是root节点，直接返回null
    if (parent == null) {
        return null;
    }

    //如果当前节点是父节点的左子节点,则当前节点的后继节点就是 父节点
    if (parent.left == curNode) {
        return parent;
    }

    //向上搜索当前节点的父节点...中的第一个左节点
    while (parent.parent != null && parent.parent.right == parent) {
        parent = parent.parent;
    }

    return parent.parent;
}

关于黑色节点

子节点为空页当作黑色节点

关于插入节点

插入节点一定是红色，且一定插入在叶子节点，然后根据情况去调整二叉树平衡状态。

关于删除节点

删除节点最终一定是删除叶子节点，如果删除的不是叶子节点，需要发现待删除节点的后继节点（必然在叶子节点），然后替换之后再删除。最后根据场景调整。

在线模拟红黑二叉树地址

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

红黑二叉树插入节点

红黑二叉树插入节点与 2-3-4 树插入节点对照来理解。主要有三种 2-节点插入节点；3-节点插入节点；4-节点插入节点。

插入2-结点 (2变3)

若在一黑结点下插入，且该黑结点没有红子结点时，那么这个黑结点就代表了2-结点，也就是此时我们会将 x 插入一个2-结点，因此x可直接插入,不需要调整。

插入3-结点 (3变4)

• 若在一红色结点下插入，且该红结点不存在红色兄弟结点时，那么这个红结点就代表了3-结点 (与它的黑父结点构成3-结点)
  ，因此x可直接插入此3-结点。
• 若在一黑色结点下插入，则为左下和右上两种「^」情形，也属于插入3-结点情形。

从上图中可以看出，当待插入结点在一黑色结点下插入时，直接插入而无需其他处理。

插入4-结点 (4分解为三个2-结点后其中一个2变3)

若在一红色结点下插入，且该红结点有一红色兄弟结点时，那么这个红结点就代表了4-结点 (
与它的黑父结点以及红色兄弟结点构成4-结点)，也就是此时我们会将x 插入一个4-结点。

由图可以发现：插入节点的父节点是红色节点且叔叔节点也是红色，则就是插入4-节点的场景。

插入节点代码

 public boolean insert(int value) {
    //如果根节点为空
    if (this.root == null) {
        this.root = new RbNode(value);
        this.root.color = false;
        return true;
    }

    //寻找位置
    RbNode myParent = this.root;
    while (myParent.left != null || myParent.right != null) {
        //新增数据 如果大于当前节点数值，则继续比较当前节点的右节点
        if (value > myParent.val) {
            if (myParent.right == null) {
                break;
            }
            //查看子节点
            myParent = myParent.right;
        } else if (value < myParent.val) {
            if (myParent.left == null) {
                break;
            }
            //查看子节点
            myParent = myParent.left;
        } else {
            return false;
        }
    }

    //初始化当前节点
    RbNode curNode = new RbNode(value);
    curNode.parent = myParent;
    if (value < myParent.val) {
        myParent.left = curNode;
    } else if (value > myParent.val) {
        myParent.right = curNode;
    } else {
        return false;
    }

    //修正
    insert_fix(curNode);

    //节点数量+1
    size++;
    return true;
}

插入节点修正代码

    /**
 * 根据经典红黑树和 2-3-4 完全对应的关系，新增节点总共分为三种场景
 * - 2-3-4 树 插入2-结点 (2变3)
 * - 2-3-4 树 插入3-结点 (3变4)
 * - 2-3-4 树 插入4-结点 (插入4-结点 (4分解为三个2-结点后其中一个2变3))
 *
 * @param curNode
 */
private void insert_fix(RbNode curNode) {
    if (curNode == null) {
        return;
    }

    //父节点为空，则当前节点就是root
    if (curNode.parent == null) {
        curNode.color = false;
        return;
    }

    //父节点是黑色，不需要修正. (父节点是黑色,覆盖全部 2-3-4树的2节点，部分3节点场景)
    if (!curNode.parent.color) {
        return;
    }

    //以下场景父节点颜色为红色
    RbNode myParent = curNode.parent;
    RbNode myGrandParent = curNode.parent.parent;
    RbNode myUncle = curNode.parent.parent.left;
    if (myUncle != null && myUncle.val == myParent.val) {
        myUncle = curNode.parent.parent.right;
    }

    //2-3-4 数 --> 4节点.(父节点和叔叔节点都是红色)
    if (myUncle != null && myUncle.color) {
        //第一步交换颜色
        color_flip_up(curNode.parent.parent);
        //1. x000。
        //2. 0x00。
        //3. 00x0。
        //4. 000x。
        //继续上溯调整
        insert_fix(curNode.parent.parent);
        return;
    }

    //2-3-4 数 --> 3节点.(叔叔节点不是红色或者不存在，父节点是红色) 假设插入节点是x,总共三种情况
    int min = Math.min(Math.min(curNode.val, myParent.val), myGrandParent.val);
    int max = Math.max(Math.max(curNode.val, myParent.val), myGrandParent.val);
    //1. x00。
    if (curNode.val == min) {
        //由于排除了 父节点是黑色，所以排除了 第一个0是父节点的场景，因此 只剩一种场景 第二个0是父节点.
        //所以先对第一和第二个0变色，再对第一个0右旋. 得到第一个0成为父节点，x成为左子节点，第二个0成为右子节点效果。
        color_flip_up(curNode.parent.parent);
        rotate_right(curNode.parent.parent);
    }
    //2. 0x0
    else if (curNode.val > min && curNode.val < max) {
        //场景1 第一个0 是祖父节点。
        if (curNode.parent.val < curNode.parent.parent.val) {
            //x左旋；x和第一个0交换颜色；x右旋
            rotate_left(curNode.parent);
            color_flip_up(curNode.parent);
            rotate_right(curNode.parent);
        }
        //场景2 第二个0 是祖父节点
        else {
            // x右旋；x和第一个0交换颜色；x左旋
            rotate_right(curNode.parent);
            color_flip_up(curNode.parent);
            rotate_left(curNode.parent);
        }
    }
    //3. 00x
    else {
        //由于排除了 父节点是黑色，所以排除了 第二个0是父节点的场景，因此 只剩一种场景 第一个0是父节点.
        //先将第一个和第二个0 交换颜色，然后左旋第二个0
        color_flip_up(curNode.parent.parent);
        rotate_left(curNode.parent.parent);
    }
}

红黑二叉树删除节点

删除操作据说是最难的部分，掌握了删除逻辑约等于掌握了红黑二叉树。

2-3-4 树删除节点的场景

以key 是否在叶子结点中划分

红黑树删除结点情形

删除调整

通过上述分析，我们发现仅有 x 无孩子结点且为黑 时才需要恢复同构。
为方便叙述，我们将前述归约出的4种情形与「算法导论」给出的 case1~4 对照如下。

※ w 是待删除结点 X 的兄弟结点。

删除操作代码

public boolean remove(int value) {
    //find 节点
    RbNode curNode = find(value);
    if (curNode == null) {
        return false;
    }

    //元素数量减少1
    size--;

    //当前节点 无父节点且无孩子节点，则当前节点是跟节点且只剩唯一节点。
    if (curNode.parent == null && curNode.left == null && curNode.right == null) {
        curNode.parent = curNode.left = curNode.right = null;
        this.root = null;
        return true;
    }

    //1. 2-3-4数key 不在叶子节点中。（根据中序遍历可知: 此时当前节点一定有后继节点，且后继节点一定在叶子节点中）。
    if (curNode.left != null && curNode.right != null) {
        RbNode successorNode = findSuccessorNode(curNode);
        //交换数值
        curNode.val = successorNode.val;
        //指针指向调整
        curNode = successorNode;
    }

    //2. 2-3-4数key 在叶子节点中（直接删除目标键值然后修正2-3-4数平衡）。
    RbNode children = curNode.left != null ? curNode.left : curNode.right;
    //2-a. 红黑二叉树节点 curNode 有一个子节点（左子节点或者右子节点）。
    // [此种场景保证了 curNode一定是黑色，其子节点一定是红色。删除curNode后，子节点变黑即可保持红黑树性质。不需要调整]
    if (children != null) {
        //先处理父节点关系
        RbNode parent = curNode.parent;
        if (parent == null) {
            this.root = children;
        } else if (parent.left.val == curNode.val) {
            parent.left = children;
        } else {
            parent.right = children;
        }

        //再处理当前节点
        curNode.parent = curNode.left = curNode.right = null;

        //最后处理子节点
        children.parent = parent;
        children.color = false;
    }
    //2-b. 红黑二叉树节点 curNode 没有子节点。 此种场景最复杂，当curNode 是红色需要修正。
    else {
        //待删除的节点是黑色 则需要修复
        if (!curNode.color) {
            remove_fix(curNode);
        }

        RbNode parent = curNode.parent;
        if (parent != null) {
            //先处理父节点
            if (parent.left != null && curNode.val == parent.left.val) {
                curNode.parent.left = null;
            } else {
                curNode.parent.right = null;
            }
            //再处理当前节点
            curNode.parent = null;
        }
    }

    return true;
}

删除修复代码

void remove_fix(RbNode curNode) {
    //2-3-4 树 3-节点和 4-节点 或者根节点 直接删除即可。 不需要修补逻辑
    //当前节点是红色 则停止修正。（删除修复操作在遇到被删除的节点是红色节点或者到达root节点时，修复操作完毕。）
    //需要做的处理是从兄弟节点上借调黑色的节点过来，如果兄弟节点没有黑节点可以借调的话，就只能往上追溯，将每一级的黑节点数减去一个，使得整棵树符合红黑树的定义。
    //删除操作的总体思想是从兄弟节点借调黑色节点使树保持局部的平衡，如果局部的平衡达到了，就看整体的树是否是平衡的，如果不平衡就接着向上追溯调整。
    //算法导论4情形。 vs 2-3-4 四种情形.(w 是待删除节点的兄弟节点)
    //删除修复操作分为四种情况(删除黑节点后)：
    //case 1: w是红色。[只需对当前节点父节点置红以及w节点变黑并且左旋当前节点的父节点，即可转换成下述 2-4场景]
    //case 2: w是黑色，且其孩子左黑右黑
    //case 3: w是黑色，且其孩子左红右黑。（只需对 w 和 w.left 变色，然后右旋w，即为场景4）
    //case 4: w是黑色，且其孩子左黑右红或者左红右红
    while (curNode.val != this.root.val && colorBlack(curNode)) {
        //待删除节点是左节点(一切为了 右边兄弟左旋).
        if (curNode.parent.left != null && curNode.val == curNode.parent.left.val) {
            RbNode w = curNode.parent.right;
            //case 1: w是红色。[只需对当前节点父节点置红以及w节点变黑并且左旋当前节点的父节点，即可转换成下述 2-4场景]
            if (w.color) {
                //1.w置黑
                w.color = false;
                //2. 待删除节点父节点置红
                curNode.parent.color = true;
                //3.待删除节点父节点左旋
                rotate_left(curNode.parent);
                //更新兄弟节点位置
                w = curNode.parent.right;
            }

            //case 2:w是黑色，且其孩子左黑右黑(w变换颜色，然后向上调整).
            if (colorBlack(w.left) && colorBlack(w.right)) {
                //此时 w 一定是黑色(反色目的是让它作为一个3-结点中的红色结点)。
                w.color = true;
                //继续向上调整[唯一一个向上调整]
                curNode = curNode.parent;

                //如果当前节点是红色 则已经平衡
                if (curNode.color) {
                    break;
                }
            } else {
                //case 3: w是黑色，且其孩子左红右黑。（只需对 w 和 w.left 变色，然后右旋w，即为场景4）
                if (colorBlack(w.right)) {
                    //w.left 置黑
                    w.left.color = false;
                    //w 置红
                    w.color = true;
                    //右旋w
                    rotate_right(w);
                    //调整兄弟节点
                    w = curNode.parent.right;
                }

                //case 4: w是黑色，且其孩子左黑右红或者左红右红.
                //置w和curNode.parent 相同颜色
                w.color = curNode.parent.color;
                //置curNode.parent 黑色
                curNode.parent.color = false;
                //置w.right 黑色
                w.right.color = false;
                //左旋curNode.parent
                rotate_left(curNode.parent);
                //兄弟节点不存在或者兄弟节点的子节点不存在 则表示已经平衡. 另：case3和case4调整后必平衡。curNode=this.root
                w = curNode.parent.right;
                if (w == null || (w.left == null && w.right == null)) {
                    break;
                }
            }
        } else {
            //待删除节点是右节点
            RbNode w = curNode.parent.left;
            //case 1: w是红色。[只需对当前节点父节点置红以及w节点变黑并且左旋当前节点的父节点，即可转换成下述 2-4场景]
            if (w.color) {
                //curNode.parent 置黑
                curNode.parent.color = true;
                //w置黑
                w.color = false;
                //curNode.parent右旋
                rotate_right(curNode.parent);
                //更新兄弟节点位置
                w = curNode.parent.left;
            }

            //case 2:w是黑色，且其孩子左黑右黑(w变换颜色，然后向上调整).
            if (colorBlack(w.left) && colorBlack(w.right)) {
                //此时 w 一定是黑色(反色目的是让它作为一个3-结点中的红色结点)。
                w.color = true;
                //继续向上调整[唯一一个向上调整]
                curNode = curNode.parent;
                //如果当前节点是红色 则已经平衡
                if (curNode.color) {
                    break;
                }
            } else {
                //case 3: w是黑色，且其孩子右红左黑。（只需对 w 和 w.right 变色，然后右旋w，即为场景4）
                if (colorBlack(w.left)) {
                    //w.right 置黑
                    w.right.color = false;
                    //w 置红
                    w.color = true;
                    //左旋w
                    rotate_left(w);
                    //调整兄弟节点
                    w = curNode.parent.left;
                }

                //case 4: w是黑色，且其孩子左红右黑或者左红右红.
                //置w和curNode.parent 相同颜色
                w.color = curNode.parent.color;
                //置curNode.parent 黑色
                curNode.parent.color = false;
                //置w.left 黑色
                w.left.color = false;
                //右旋curNode.parent
                rotate_right(curNode.parent);
                //兄弟节点不存在或者兄弟节点的子节点不存在 则表示已经平衡. 另：case3和case4调整后必平衡。curNode=this.root
                w = curNode.parent.left;
                if (w == null || (w.left == null && w.right == null)) {
                    break;
                }
            }
        }
    }

    // while结束要么是case3/case4调整后已平衡 x被被置为root后主动退出，
    // 要么是case1/case2 x为红。若为前者无需此句(此时的root一定是黑的)
    // 若为后者，说明此时的x结点是原3-结点或4-结点出借的结点，如果还保持红色，
    // 将无法脱离原3-结点或4-结点 (2-3-4树)，因此必须置黑。
    // 此句也可以写成这样: if(x != root) x.color = BLACK//
    curNode.color = false;
}

完整代码demo

import java.util.LinkedList;
import java.util.Queue;

/**
 * 对应2-3-4 树；
 * 规则、设定：
 * 新插入的节点是红色的;
 * 新插入节点的父节点是红色才需要修复；
 * 不支持插入相同的数字，如果插入数字相同直接返回。
 * 在线验证调试: https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
 */
public class RBTree {

    static class RbNode {

        /**
         * 父级
         */
        RbNode parent;

        /**
         * true:红色；false 黑色[默认]
         */
        boolean color;

        /**
         * 节点数值,简单起见也当作key使用
         */
        int val;

        /**
         * 左节点
         */
        RbNode left;

        /**
         * 右节点
         */
        RbNode right;

        public RbNode(int val) {
            this.val = val;
            //新插入的节点是红色的
            this.color = true;
        }
    }

    /**
     * 主节点
     */
    RbNode root;

    /**
     * 尺寸
     */
    int size;

    public boolean insert(int value) {
        //如果根节点为空
        if (this.root == null) {
            this.root = new RbNode(value);
            this.root.color = false;
            return true;
        }

        //寻找位置
        RbNode myParent = this.root;
        while (myParent.left != null || myParent.right != null) {
            //新增数据 如果大于当前节点数值，则继续比较当前节点的右节点
            if (value > myParent.val) {
                if (myParent.right == null) {
                    break;
                }
                //查看子节点
                myParent = myParent.right;
            } else if (value < myParent.val) {
                if (myParent.left == null) {
                    break;
                }
                //查看子节点
                myParent = myParent.left;
            } else {
                return false;
            }
        }

        //初始化当前节点
        RbNode curNode = new RbNode(value);
        curNode.parent = myParent;
        if (value < myParent.val) {
            myParent.left = curNode;
        } else if (value > myParent.val) {
            myParent.right = curNode;
        } else {
            return false;
        }

        //修正
        insert_fix(curNode);

        //节点数量+1
        size++;
        return true;
    }

    /**
     * 根据经典红黑树和 2-3-4 完全对应的关系，新增节点总共分为三种场景
     * - 2-3-4 树 插入2-结点 (2变3)
     * - 2-3-4 树 插入3-结点 (3变4)
     * - 2-3-4 树 插入4-结点 (插入4-结点 (4分解为三个2-结点后其中一个2变3))
     *
     * @param curNode
     */
    private void insert_fix(RbNode curNode) {
        if (curNode == null) {
            return;
        }

        //父节点为空，则当前节点就是root
        if (curNode.parent == null) {
            curNode.color = false;
            return;
        }

        //父节点是黑色，不需要修正. (父节点是黑色,覆盖全部 2-3-4树的2节点，部分3节点场景)
        if (!curNode.parent.color) {
            return;
        }

        //以下场景父节点颜色为红色
        RbNode myParent = curNode.parent;
        RbNode myGrandParent = curNode.parent.parent;
        RbNode myUncle = curNode.parent.parent.left;
        if (myUncle != null && myUncle.val == myParent.val) {
            myUncle = curNode.parent.parent.right;
        }

        //2-3-4 数 --> 4节点.(父节点和叔叔节点都是红色)
        if (myUncle != null && myUncle.color) {
            //第一步交换颜色
            color_flip_up(curNode.parent.parent);
            //1. x000。
            //2. 0x00。
            //3. 00x0。
            //4. 000x。
            //继续上溯调整
            insert_fix(curNode.parent.parent);
            return;
        }

        //2-3-4 数 --> 3节点.(叔叔节点不是红色或者不存在，父节点是红色) 假设插入节点是x,总共三种情况
        int min = Math.min(Math.min(curNode.val, myParent.val), myGrandParent.val);
        int max = Math.max(Math.max(curNode.val, myParent.val), myGrandParent.val);
        //1. x00。
        if (curNode.val == min) {
            //由于排除了 父节点是黑色，所以排除了 第一个0是父节点的场景，因此 只剩一种场景 第二个0是父节点.
            //所以先对第一和第二个0变色，再对第一个0右旋. 得到第一个0成为父节点，x成为左子节点，第二个0成为右子节点效果。
            color_flip_up(curNode.parent.parent);
            rotate_right(curNode.parent.parent);
        }
        //2. 0x0
        else if (curNode.val > min && curNode.val < max) {
            //场景1 第一个0 是祖父节点。
            if (curNode.parent.val < curNode.parent.parent.val) {
                //x左旋；x和第一个0交换颜色；x右旋
                rotate_left(curNode.parent);
                color_flip_up(curNode.parent);
                rotate_right(curNode.parent);
            }
            //场景2 第二个0 是祖父节点
            else {
                // x右旋；x和第一个0交换颜色；x左旋
                rotate_right(curNode.parent);
                color_flip_up(curNode.parent);
                rotate_left(curNode.parent);
            }
        }
        //3. 00x
        else {
            //由于排除了 父节点是黑色，所以排除了 第二个0是父节点的场景，因此 只剩一种场景 第一个0是父节点.
            //先将第一个和第二个0 交换颜色，然后左旋第二个0
            color_flip_up(curNode.parent.parent);
            rotate_left(curNode.parent.parent);
        }
    }

    /**
     * 左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。
     * 左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树挪了。
     *
     * @param p
     */
    void rotate_left(RbNode p) {
        // 1.处理当前节点的父节点
        if (p.parent == null) {
            this.root = p.right;//1
        } else if (p.parent.left != null && p.parent.left.val == p.val) {
            p.parent.left = p.right;//1
        } else {
            p.parent.right = p.right;//1
        }

        // 2.处理历史右子节点。（当前父节点）
        p.right.parent = p.parent;//2
        RbNode rightLeftNode = p.right.left;
        p.right.left = p;//3

        // 3. 处理当前节点
        p.parent = p.right;//4
        p.right = rightLeftNode;//5

        // 4.处理历史右节点的左子节点
        if (rightLeftNode != null) {
            rightLeftNode.parent = p;//6
        }
    }

    /**
     * 右旋： 以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。
     * 右旋只影响旋转结点和其左子树的结构，把左子树的结点往右子树挪了。
     *
     * @param p
     */
    void rotate_right(RbNode p) {
        // 1.处理当前节点的父节点
        if (p.parent == null) {
            this.root = p.left;//1
        } else if (p.parent.left != null && p.parent.left.val == p.val) {
            p.parent.left = p.left;//1
        } else {
            p.parent.right = p.left;//1
        }

        // 2.处理历史左子节点。（当前父节点）
        p.left.parent = p.parent;//2
        RbNode leftRightNode = p.left.right;
        p.left.right = p;//3

        // 3. 处理当前节点
        p.parent = p.left;//4
        p.left = leftRightNode;//5

        // 4.处理历史左节点的右子节点
        if (leftRightNode != null) {
            leftRightNode.parent = p;//6
        }
    }

    /**
     * @param node
     */
    void color_flip_up(RbNode node) {
        node.color = true;
        //子节点变黑
        if (node.left != null) {
            node.left.color = false;
        }
        if (node.right != null) {
            node.right.color = false;
        }
    }

    /**
     * 是否是黑色。
     * 注：空节点当作黑色
     *
     * @param node
     * @return
     */
    boolean colorBlack(RbNode node) {
        return node == null || !node.color;
    }

    /**
     * 2-3-4 树 删除key 按照key 是否在叶子节点中划分为两种场景：
     * 1. key 不在叶子节点中-->用key 后继键值替换key，然后删除后继键值（后继键必为某叶子结点中的最小键）。
     * 2. key 在叶子节点中-->直接删除目标键值（若目标键在2-结点中，删除后失去2-3-4树结构性质，要调整）。
     * <p>
     * 红黑树删除节点key 情形以删除节点的子节点情况划分3种场景
     * 1. key 有左右子节点-->用候机节点替换key（数值和节点关系），然后删除后继节点（删除后继节点必为情形2或者情形3？不是 1/2/3？）。
     * 2. key 有一个子节点-->简历子节点与 key节点的父节点的链接，然后删除key节点（key极其子节点构成3-节点，删除后不影响同构）。
     * 3. key 没有子节点-->直接删除key（key如果对应2-3-4树中的2-节点，则删除后失去同构，需修正。）。
     * <p>
     * ⚠️：依据BST数删除节点的规则（交换当前节点和后继绩点，然后删除后继节点）。无论删除的结点在何处，最终都会 删除一个对应于2-3-4树上的叶子结点。
     *
     * @param value
     * @return
     */
    public boolean remove(int value) {
        //find 节点
        RbNode curNode = find(value);
        if (curNode == null) {
            return false;
        }

        //元素数量减少1
        size--;

        //当前节点 无父节点且无孩子节点，则当前节点是跟节点且只剩唯一节点。
        if (curNode.parent == null && curNode.left == null && curNode.right == null) {
            curNode.parent = curNode.left = curNode.right = null;
            this.root = null;
            return true;
        }

        //1. 2-3-4数key 不在叶子节点中。（根据中序遍历可知: 此时当前节点一定有后继节点，且后继节点一定在叶子节点中）。
        if (curNode.left != null && curNode.right != null) {
            RbNode successorNode = findSuccessorNode(curNode);
            //交换数值
            curNode.val = successorNode.val;
            //指针指向调整
            curNode = successorNode;
        }

        //2. 2-3-4数key 在叶子节点中（直接删除目标键值然后修正2-3-4数平衡）。
        RbNode children = curNode.left != null ? curNode.left : curNode.right;
        //2-a. 红黑二叉树节点 curNode 有一个子节点（左子节点或者右子节点）。
        // [此种场景保证了 curNode一定是黑色，其子节点一定是红色。删除curNode后，子节点变黑即可保持红黑树性质。不需要调整]
        if (children != null) {
            //先处理父节点关系
            RbNode parent = curNode.parent;
            if (parent == null) {
                this.root = children;
            } else if (parent.left.val == curNode.val) {
                parent.left = children;
            } else {
                parent.right = children;
            }

            //再处理当前节点
            curNode.parent = curNode.left = curNode.right = null;

            //最后处理子节点
            children.parent = parent;
            children.color = false;
        }
        //2-b. 红黑二叉树节点 curNode 没有子节点。 此种场景最复杂，当curNode 是红色需要修正。
        else {
            //待删除的节点是黑色 则需要修复
            if (!curNode.color) {
                remove_fix(curNode);
            }

            RbNode parent = curNode.parent;
            if (parent != null) {
                //先处理父节点
                if (parent.left != null && curNode.val == parent.left.val) {
                    curNode.parent.left = null;
                } else {
                    curNode.parent.right = null;
                }
                //再处理当前节点
                curNode.parent = null;
            }
        }

        return true;
    }

    /**
     * 中序遍历，查找当前节点的后续节点（寻找继承人）
     *
     * @param curNode
     * @return
     */
    RbNode findSuccessorNode(RbNode curNode) {
        if (curNode == null) {
            return null;
        }

        //1. 向下搜索-> 当前节点有 右子节点
        if (curNode.right != null) {
            RbNode mySuccessorNode = curNode;
            while (mySuccessorNode.left != null) {
                mySuccessorNode = mySuccessorNode.left;
            }
            return mySuccessorNode;
        }

        //2. 向上搜索-> 当前节点没有 右子节点.
        RbNode parent = curNode.parent;
        //如果没有父节点，则当前节点是root节点，直接返回null
        if (parent == null) {
            return null;
        }
        //如果当前节点是父节点的左子节点,则当前节点的后继节点就是 父节点
        if (parent.left == curNode) {
            return parent;
        }
        //向上搜索当前节点的父节点...中的第一个左节点
        while (parent.parent != null && parent.parent.right == parent) {
            parent = parent.parent;
        }

        return parent.parent;
    }

    /**
     * 删除修复。【只有当前节点是黑色才会修复】
     *
     * @param curNode
     */
    void remove_fix(RbNode curNode) {
        //2-3-4 树 3-节点和 4-节点 或者根节点 直接删除即可。 不需要修补逻辑
        //当前节点是红色 则停止修正。（删除修复操作在遇到被删除的节点是红色节点或者到达root节点时，修复操作完毕。）
        //需要做的处理是从兄弟节点上借调黑色的节点过来，如果兄弟节点没有黑节点可以借调的话，就只能往上追溯，将每一级的黑节点数减去一个，使得整棵树符合红黑树的定义。
        //删除操作的总体思想是从兄弟节点借调黑色节点使树保持局部的平衡，如果局部的平衡达到了，就看整体的树是否是平衡的，如果不平衡就接着向上追溯调整。
        //算法导论4情形。 vs 2-3-4 四种情形.(w 是待删除节点的兄弟节点)
        //删除修复操作分为四种情况(删除黑节点后)：
        //case 1: w是红色。[只需对当前节点父节点置红以及w节点变黑并且左旋当前节点的父节点，即可转换成下述 2-4场景]
        //case 2: w是黑色，且其孩子左黑右黑
        //case 3: w是黑色，且其孩子左红右黑。（只需对 w 和 w.left 变色，然后右旋w，即为场景4）
        //case 4: w是黑色，且其孩子左黑右红或者左红右红
        while (curNode.val != this.root.val && colorBlack(curNode)) {
            //待删除节点是左节点(一切为了 右边兄弟左旋).
            if (curNode.parent.left != null && curNode.val == curNode.parent.left.val) {
                RbNode w = curNode.parent.right;
                //case 1: w是红色。[只需对当前节点父节点置红以及w节点变黑并且左旋当前节点的父节点，即可转换成下述 2-4场景]
                if (w.color) {
                    //1.w置黑
                    w.color = false;
                    //2. 待删除节点父节点置红
                    curNode.parent.color = true;
                    //3.待删除节点父节点左旋
                    rotate_left(curNode.parent);
                    //更新兄弟节点位置
                    w = curNode.parent.right;
                }

                //case 2:w是黑色，且其孩子左黑右黑(w变换颜色，然后向上调整).
                if (colorBlack(w.left) && colorBlack(w.right)) {
                    //此时 w 一定是黑色(反色目的是让它作为一个3-结点中的红色结点)。
                    w.color = true;
                    //继续向上调整[唯一一个向上调整]
                    curNode = curNode.parent;

                    //如果当前节点是红色 则已经平衡
                    if (curNode.color) {
                        break;
                    }
                } else {
                    //case 3: w是黑色，且其孩子左红右黑。（只需对 w 和 w.left 变色，然后右旋w，即为场景4）
                    if (colorBlack(w.right)) {
                        //w.left 置黑
                        w.left.color = false;
                        //w 置红
                        w.color = true;
                        //右旋w
                        rotate_right(w);
                        //调整兄弟节点
                        w = curNode.parent.right;
                    }

                    //case 4: w是黑色，且其孩子左黑右红或者左红右红.
                    //置w和curNode.parent 相同颜色
                    w.color = curNode.parent.color;
                    //置curNode.parent 黑色
                    curNode.parent.color = false;
                    //置w.right 黑色
                    w.right.color = false;
                    //左旋curNode.parent
                    rotate_left(curNode.parent);
                    //兄弟节点不存在或者兄弟节点的子节点不存在 则表示已经平衡. 另：case3和case4调整后必平衡。curNode=this.root
                    w = curNode.parent.right;
                    if (w == null || (w.left == null && w.right == null)) {
                        break;
                    }
                }
            } else {
                //待删除节点是右节点
                RbNode w = curNode.parent.left;
                //case 1: w是红色。[只需对当前节点父节点置红以及w节点变黑并且左旋当前节点的父节点，即可转换成下述 2-4场景]
                if (w.color) {
                    //curNode.parent 置黑
                    curNode.parent.color = true;
                    //w置黑
                    w.color = false;
                    //curNode.parent右旋
                    rotate_right(curNode.parent);
                    //更新兄弟节点位置
                    w = curNode.parent.left;
                }

                //case 2:w是黑色，且其孩子左黑右黑(w变换颜色，然后向上调整).
                if (colorBlack(w.left) && colorBlack(w.right)) {
                    //此时 w 一定是黑色(反色目的是让它作为一个3-结点中的红色结点)。
                    w.color = true;
                    //继续向上调整[唯一一个向上调整]
                    curNode = curNode.parent;
                    //如果当前节点是红色 则已经平衡
                    if (curNode.color) {
                        break;
                    }
                } else {
                    //case 3: w是黑色，且其孩子右红左黑。（只需对 w 和 w.right 变色，然后右旋w，即为场景4）
                    if (colorBlack(w.left)) {
                        //w.right 置黑
                        w.right.color = false;
                        //w 置红
                        w.color = true;
                        //左旋w
                        rotate_left(w);
                        //调整兄弟节点
                        w = curNode.parent.left;
                    }

                    //case 4: w是黑色，且其孩子左红右黑或者左红右红.
                    //置w和curNode.parent 相同颜色
                    w.color = curNode.parent.color;
                    //置curNode.parent 黑色
                    curNode.parent.color = false;
                    //置w.left 黑色
                    w.left.color = false;
                    //右旋curNode.parent
                    rotate_right(curNode.parent);
                    //兄弟节点不存在或者兄弟节点的子节点不存在 则表示已经平衡. 另：case3和case4调整后必平衡。curNode=this.root
                    w = curNode.parent.left;
                    if (w == null || (w.left == null && w.right == null)) {
                        break;
                    }
                }
            }
        }

        // while结束要么是case3/case4调整后已平衡 x被被置为root后主动退出，
        // 要么是case1/case2 x为红。若为前者无需此句(此时的root一定是黑的)
        // 若为后者，说明此时的x结点是原3-结点或4-结点出借的结点，如果还保持红色，
        // 将无法脱离原3-结点或4-结点 (2-3-4树)，因此必须置黑。
        // 此句也可以写成这样: if(x != root) x.color = BLACK//
        curNode.color = false;
    }

    public RbNode find(int value) {
        RbNode myParent = this.root;
        while (myParent != null) {
            if (value > myParent.val) {
                if (myParent.right == null) {
                    return null;
                }
                myParent = myParent.right;
            } else if (value < myParent.val) {
                if (myParent.left == null) {
                    return null;
                }
                myParent = myParent.left;
            } else {
                return myParent;
            }
        }

        return null;
    }

    /**
     * 广度优先遍历
     */
    public void printTree() {
        Queue<RbNode> queue = new LinkedList<>();
        if (this.root == null) {
            return;
        }
        //首次
        queue.add(this.root);
        //开始遍历
        while (!queue.isEmpty()) {
            //遍历
            int length = queue.size();
            for (int i = 0; i < length; i++) {
                //从队尾取出数据
                RbNode n = queue.poll();
                System.out.print((n.color ? "R" : "B") + ":" + n.val + "\t");
                //从队首增加
                if (n.left != null) {
                    queue.add(n.left);
                }
                if (n.right != null) {
                    queue.add(n.right);
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        RBTree rbTree = new RBTree();
        System.out.println(rbTree.insert(1));
        System.out.println(rbTree.insert(2));
        System.out.println(rbTree.insert(3));
        System.out.println(rbTree.insert(4));
        System.out.println(rbTree.insert(5));
//        rbTree.printTree();
        System.out.println(rbTree.insert(6));
//        rbTree.printTree();
        System.out.println(rbTree.insert(7));
//        rbTree.printTree();
        System.out.println(rbTree.insert(8));
//        rbTree.printTree();
        System.out.println(rbTree.insert(9));
//        rbTree.printTree();
        System.out.println(rbTree.insert(10));
//        rbTree.printTree();
        System.out.println("###### 开始删除操作 ######");

        for (int i = 10; i >= 1; i--) {
            if (i == 1) {
                System.out.println(i);
            }
            System.out.println(rbTree.remove(i));
            rbTree.printTree();
        }

    }
}

参考（如有冒犯请联系删除）

文中部分定义和图片参考链接