JAVA基础集合框架【四】HashMap之源码分析红黑树-插入

文章首发于：clawhub.club

红黑树插入操作与二叉查找树的插入方式是一样的，之不过插入后，会影响到树的平衡，所以要对树进行旋转和着色操作，使其符合红黑树的5条性质。
继续贴上性质：

每个结点要么是红的，要么是黑的。
根结点是黑的。
每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。
如果一个结点是红的，那么它的俩个儿子都是黑的。
对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

新插入的节点是红色的（如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的。但是设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过颜色调换（color flips）和树旋转来调整。），
插入修复操作如果遇到父节点的颜色为黑则修复操作结束。也就是说，只有在父节点为红色节点的时候是需要插入修复操作的。

为什么要插入修复？

因为插入节点后，会影响到性质4与5。

不会造成性质破坏的插入

1插入节点作为根节点

直接插入后，将节点设置为黑色。

2插入节点作为根节点的子节点

既然能作为根节点的字节点，即数中只有根节点与叶子节点为黑色。不会影响到性质4与5。

3插入节点的父结点是黑色的

因为插入的节点使红色的，所以不会影响到性质4与5。

即只有祖父节点不为空并且父结点是红色的，才需要插入修复。

需要修复的插入

插入修复情况1：

当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色。
修复操作为：将叔、父重绘为黑色，祖绘为红色，这种修复并不是一次性的，修复完毕需要继续进行从头开始的插入后修复判断。

插入修复情况2：

叔结点为黑色（空），并且子父祖三节点位于同侧斜线上。
修复操作为：将父绘黑，祖绘红，然后以祖为枢纽进行向相反侧的方向旋转，同在右侧斜线上的就往左旋转，同在左侧斜线上的就往右旋转。

插入修复情况3：

叔结点为黑色（空），并且子父祖三节点位于异侧斜线上。
修复操作分为了两步：
第一步是根据子父所在的那一侧的方向，以父为枢向相反方向旋转，这样就实现了将子父祖异侧转换为了父子祖同侧(并且是子父原所在侧的相反侧)；
第二步是发现它符合插入修复情况2 了，那就将现在的父(原来的子)绘黑，祖(原来的祖)绘红，再旋转。

插入操作很复杂，学的我脑壳疼。以下准备用JAVA代码实现上述操作。

辅助函数

/**
 * 返回结点的父结点或者null
 *
 * @param p the p
 * @return the node
 */
private Node<T> parentOf(Node<T> p) {
    return (p == null ? null : p.parent);
}

/**
 * 判断节点是否为红色
 *
 * @param p the p
 * @return the boolean
 */
private boolean isRed(Node<T> p) {
    return p.color == Node.RED;
}

/**
 * 将节点绘制成红色
 *
 * @param p the p
 */
void makeRed(Node<T> p) {
    p.color = Node.RED;
}

/**
 * 将节点绘制成黑色
 *
 * @param p the p
 */
void makeBlack(Node<T> p) {
    p.color = Node.BLACK;
}

二叉搜索树插入

/**
 * 二叉树添加节点
 *
 * @param value 插入的值
 * @return 返回节点位置
 */
private Node<T> insertBST(T value) {
    //当前节点
    Node<T> current = new Node<>(value);
    //父节点
    Node<T> parent = null;

    //根节点替代品
    Node<T> temp = root;
    //循环查找到待插入的节点的父节点
    while (true) {
        //如果根节点为null,跳出寻循环
        if (temp == null) {
            break;
        }
        //指向根节点
        parent = temp;

        //如果待插入的值 等于 temp节点的值
        if (temp.value.equals(current.value)) {
            //频率加1
            current.freq++;
            //程序结束
            return temp;

        } else if (temp.value.compareTo(current.value) < 0) {
            //如果待插入的值 大于 temp节点的值,则查找当前节点右边的节点
            temp = temp.right;
        } else {
            //如果待插入的值 小于 temp节点的值,则查找当前节点左边的节点
            temp = temp.left;
        }
    }
    //找到待插入值的父节点
    if (null != parent) {
        //如果待插入的值 大于 父节点的值，则插入到父节点的右边
        if (parent.value.compareTo(current.value) < 0) {
            current.parent = parent;
            parent.right = current;
        } else {
            //如果待插入的值 小于 父节点的值，则插入到父节点的左边
            current.parent = parent;
            parent.left = current;
        }
    } else {
        //如果父节点为空，就此节点作为根节点
        root = current;
    }
    //返回插入后的节点
    return current;
}

红黑树插入修正（重点）

/**
 * 红黑树插入修正函数
 * 父节点存在，并且父节点的颜色是红色
 * Case 1条件：当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色
 * Case 2条件：叔叔结点为黑色（空），并且子父祖三节点位于同侧斜线上
 * Case 3条件：叔叔结点为黑色（空），并且子父祖三节点位于异侧斜线上
 *
 * @param node 插入的结点
 */
private void insertFixUp(Node<T> node) {
    //父节点 祖父节点
    Node<T> parent, gparent;

    // 若父节点存在，并且父节点的颜色是红色,即执行到根节点或者节点颜色为黑色，跳出循环
    while (((parent = parentOf(node)) != null) && isRed(parent)) {
        //祖父节点
        gparent = parentOf(parent);
        //叔叔节点
        Node<T> uncle;
        //若父节点是祖父节点的左节点
        if (parent == gparent.left) {
            uncle = gparent.right;
        } else {
            //若父节点是祖父节点的右节点，则叔叔为左节点
            uncle = gparent.left;
        }

        // Case 1条件：当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色
        if ((uncle != null) && isRed(uncle)) {
            //将叔叔绘成黑色
            makeBlack(uncle);
            //将父亲绘成黑色
            makeBlack(parent);
            //将祖父绘成红色
            makeRed(gparent);
            //当前节点指向祖父节点
            node = gparent;
            //跳出本次循环
            continue;
        }

        //若父节点是祖父节点的左节点
        if (parent == gparent.left) {
            // Case 3条件：叔叔结点为黑色（空），并且子父祖三节点位于异侧斜线上，即当前节点是父节点的右节点。
            if (parent.right == node) {
                Node<T> tmp;
                //第一步以父为枢纽向相反方向旋转,子在父右侧就往左旋转，子在父左侧就往右旋转，这样就实现了将子父祖异侧转换为了父子祖同侧
                //因为子节点在父节点的右测，则将父节点左旋
                rotateLeft(parent);
                //子节点变为父节点
                tmp = parent;
                parent = node;
                node = tmp;
                //第二步是发现它符合Case 2情况了，那就将现在的父(原来的子)绘黑，祖(原来的祖)绘红，祖(原来的祖)旋转
                //走到Case 2
            }
            // Case 2条件：叔叔结点为黑色（空），并且子父祖三节点位于同侧斜线上，即当前节点是父节点的左节点
            // 这个判断可以省略
            if (parent.left == node) {
                //将父亲绘成黑色
                makeBlack(parent);
                //将祖父绘成红色
                makeRed(gparent);
                //以祖为枢纽进行向相反侧的方向旋转，同在右侧斜线上的就往左旋转，同在左侧斜线上的就往右旋转
                //因为都在左侧斜线上，所以右旋转
                rotateRight(gparent);
            }

        } else {
            //若父节点是祖父节点的右节点
            // Case 3条件：叔叔结点为黑色（空），并且子父祖三节点位于异侧斜线上，即当前节点是父节点的左节点。
            if (parent.left == node) {
                Node<T> tmp;
                //第一步以父为枢纽向相反方向旋转,子在父右侧就往左旋转，子在父左侧就往右旋转，这样就实现了将子父祖异侧转换为了父子祖同侧
                //因为子节点在父节点的左测，则将父节点右旋
                rotateRight(parent);
                //子节点变为父节点
                tmp = parent;
                parent = node;
                node = tmp;
                //第二步是发现它符合Case 2情况了，那就将现在的父(原来的子)绘黑，祖(原来的祖)绘红，祖(原来的祖)旋转
                //走到Case 2
            }
            // Case 2条件：叔叔结点为黑色（空），并且子父祖三节点位于同侧斜线上，即当前节点是父节点的右节点
            // 这个判断可以省略
            if (parent.right == node) {
                //将父亲绘成黑色
                makeBlack(parent);
                //将祖父绘成红色
                makeRed(gparent);
                //以祖为枢纽进行向相反侧的方向旋转，同在右侧斜线上的就往左旋转，同在左侧斜线上的就往右旋转
                //因为都在右侧斜线上，所以左旋转
                rotateLeft(gparent);
            }

        }
    }
    // 将根节点设为黑色
    makeBlack(root);
}

红黑树插入操作


/**
 * Insert.
 *
 * @param value the value
 */
public void insert(T value) {
    //以二叉搜索树的方式插入节点
    Node<T> current = insertBST(value);
    //父节点为红色节点的时候是需要插入修复操作的
    insertFixUp(current);
}

参考文档：
红黑树深入剖析及Java实现
 教你透彻了解红黑树
 红黑树(五)之 Java的实现