JDK8：HashMap源码解析：TreeNode类的balanceInsertion方法

川长思鸟来 2024-04-20 08:20 22阅读 0赞

一、概述

balanceInsertion指的是红黑树的插入平衡算法，当树结构中新插入了一个节点后，要对树进行重新的结构化，以保证该树始终维持红黑树的特性。

关于红黑树的特性：

性质1. 节点是红色或黑色。

性质2. 根节点是黑色。

性质3 每个叶节点（NIL节点，空节点）是黑色的。

性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

性质5. 从任一节点到其每个叶子的路径上包含的黑色节点数量都相同。

二、方法解析

/**
     * 红黑树插入节点后，需要重新平衡
     * root 当前根节点
     * x 新插入的节点
     * 返回重新平衡后的根节点
     */
    static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                        TreeNode<K,V> x) {
        x.red = true; // 新插入的节点标为红色
     
        /*
         * 这一步即定义了变量，又开起了循环，循环没有控制条件，只能从内部跳出
         * xp：当前节点的父节点、xpp：爷爷节点、xppl：左叔叔节点、xppr：右叔叔节点
         */
        for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { 
     
            // 如果父节点为空、说明当前节点就是根节点，那么把当前节点标为黑色，返回当前节点
            if ((xp = x.parent) == null) { // L1
                x.red = false;
                return x;
            }
     
            // 父节点不为空
            // 如果父节点为黑色 或者 【（父节点为红色 但是 爷爷节点为空） -> 这种情况何时出现？】
            else if (!xp.red || (xpp = xp.parent) == null) // L2
                return root;
            if (xp == (xppl = xpp.left)) { // 如果父节点是爷爷节点的左孩子  // L3
                if ((xppr = xpp.right) != null && xppr.red) { // 如果右叔叔不为空 并且 为红色  // L3_1
                    xppr.red = false; // 右叔叔置为黑色
                    xp.red = false; // 父节点置为黑色
                    xpp.red = true; // 爷爷节点置为红色
                    x = xpp; // 运行到这里之后，就又会进行下一轮的循环了，将爷爷节点当做处理的起始节点 
                }
                else { // 如果右叔叔为空 或者 为黑色 // L3_2
                    if (x == xp.right) { // 如果当前节点是父节点的右孩子 // L3_2_1
                        root = rotateLeft(root, x = xp); // 父节点左旋，见下文左旋方法解析
                        xpp = (xp = x.parent) == null ? null : xp.parent; // 获取爷爷节点
                    }
                    if (xp != null) { // 如果父节点不为空 // L3_2_2
                        xp.red = false; // 父节点 置为黑色
                        if (xpp != null) { // 爷爷节点不为空
                            xpp.red = true; // 爷爷节点置为 红色
                            root = rotateRight(root, xpp);  //爷爷节点右旋，见下文右旋方法解析
                        }
                    }
                }
            }
            else { // 如果父节点是爷爷节点的右孩子 // L4
                if (xppl != null && xppl.red) { // 如果左叔叔是红色 // L4_1
                    xppl.red = false; // 左叔叔置为 黑色
                    xp.red = false; // 父节点置为黑色
                    xpp.red = true; // 爷爷置为红色
                    x = xpp; // 运行到这里之后，就又会进行下一轮的循环了，将爷爷节点当做处理的起始节点 
                }
                else { // 如果左叔叔为空或者是黑色 // L4_2
                    if (x == xp.left) { // 如果当前节点是个左孩子 // L4_2_1
                        root = rotateRight(root, x = xp); // 针对父节点做右旋，见下文右旋方法解析
                        xpp = (xp = x.parent) == null ? null : xp.parent; // 获取爷爷节点
                    }
                    if (xp != null) { // 如果父节点不为空 // L4_2_4
                        xp.red = false; // 父节点置为黑色
                        if (xpp != null) { //如果爷爷节点不为空
                            xpp.red = true; // 爷爷节点置为红色
                            root = rotateLeft(root, xpp); // 针对爷爷节点做左旋
                        }
                    }
                }
            }
        }
    }
     
     
    /**
     * 节点左旋
     * root 根节点
     * p 要左旋的节点
     */
    static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                                  TreeNode<K,V> p) {
        TreeNode<K,V> r, pp, rl;
        if (p != null && (r = p.right) != null) { // 要左旋的节点以及要左旋的节点的右孩子不为空
            if ((rl = p.right = r.left) != null) // 要左旋的节点的右孩子的左节点 赋给 要左旋的节点的右孩子 节点为：rl
                rl.parent = p; // 设置rl和要左旋的节点的父子关系【之前只是爹认了孩子，孩子还没有答应，这一步孩子也认了爹】
     
            // 将要左旋的节点的右孩子的父节点  指向 要左旋的节点的父节点，相当于右孩子提升了一层，
            // 此时如果父节点为空， 说明r 已经是顶层节点了，应该作为root 并且标为黑色
            if ((pp = r.parent = p.parent) == null) 
                (root = r).red = false;
            else if (pp.left == p) // 如果父节点不为空 并且 要左旋的节点是个左孩子
                pp.left = r; // 设置r和父节点的父子关系【之前只是孩子认了爹，爹还没有答应，这一步爹也认了孩子】
            else // 要左旋的节点是个右孩子
                pp.right = r; 
            r.left = p; // 要左旋的节点  作为 他的右孩子的左节点
            p.parent = r; // 要左旋的节点的右孩子  作为  他的父节点
        }
        return root; // 返回根节点
    }
     
    /**
     * 节点右旋
     * root 根节点
     * p 要右旋的节点
     */
    static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                                   TreeNode<K,V> p) {
        TreeNode<K,V> l, pp, lr;
        if (p != null && (l = p.left) != null) { // 要右旋的节点不为空以及要右旋的节点的左孩子不为空
            if ((lr = p.left = l.right) != null) // 要右旋的节点的左孩子的右节点 赋给 要右旋节点的左孩子 节点为：lr
                lr.parent = p; // 设置lr和要右旋的节点的父子关系【之前只是爹认了孩子，孩子还没有答应，这一步孩子也认了爹】
     
            // 将要右旋的节点的左孩子的父节点  指向 要右旋的节点的父节点，相当于左孩子提升了一层，
            // 此时如果父节点为空， 说明l 已经是顶层节点了，应该作为root 并且标为黑色
            if ((pp = l.parent = p.parent) == null) 
                (root = l).red = false;
            else if (pp.right == p) // 如果父节点不为空 并且 要右旋的节点是个右孩子
                pp.right = l; // 设置l和父节点的父子关系【之前只是孩子认了爹，爹还没有答应，这一步爹也认了孩子】
            else // 要右旋的节点是个左孩子
                pp.left = l; // 同上
            l.right = p; // 要右旋的节点 作为 他左孩子的右节点
            p.parent = l; // 要右旋的节点的父节点 指向 他的左孩子
        }
        return root;
    }

三、图例

1、无旋转

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h6ajgwOTI3_size_16_color_FFFFFF_t_70][]

2、有旋转

![20180603115848623][]

![20180603115905376][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h6ajgwOTI3_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/3f3eeb8e9fd94554a5020cc5e43eabd9.png
[20180603115848623]: https://img-blog.csdn.net/20180603115848623
[20180603115905376]: https://img-blog.csdn.net/20180603115905376