/**
     * 红黑树插入操作
     * @param root 根节点
     * @param x 新插入节点
     * @return
     */
    static <K,V> HashMap.TreeNode<K,V> balanceInsertion(HashMap.TreeNode<K,V> root,
                                                        HashMap.TreeNode<K,V> x) {
        // 新节点默认为红色
        x.red = true;
        /**
         * xp：表示新节点的父节点
         * xpp：表示新节点的祖父节点
         * xppl：表示祖父节点的左子节点
         * xppr：表示祖父节点的右子节点
         */
        for (HashMap.TreeNode<K,V> xp, xpp, xppl, xppr;;) {
            // 如果新节点的父节点为空，则新节点就是根节点
            if ((xp = x.parent) == null) {
                // 将颜色设置为黑色
                x.red = false;
                return x;// 返回这个节点
            }
            //如果父节点是黑色，或祖父节点为空
            else if (!xp.red || (xpp = xp.parent) == null)
                //直接返回根节点
                return root;
            //如果父节点等于祖父节点的左子节点
            if (xp == (xppl = xpp.left)) {
                // 如果祖父节点的右节点不为空，并且叔叔节点是红色的
                if ((xppr = xpp.right) != null && xppr.red) {
                    xppr.red = false; // 叔叔节点变为黑色
                    xp.red = false; // 父节点变为黑色
                    xpp.red = true; // 祖父节点变为红色
                    x = xpp; // 祖父节点变为新节点X
                }
                // 叔叔节点为空，或者叔叔节点时黑色的
                else {
                    // 如果新节点等于父节点的有子节点
                    if (x == xp.right) {
                        // 先将新节点的父节点左旋
                        root = rotateLeft(root, x = xp);
                        // 左旋完结构xpp(pp) -> xp(r，原来的新节点) -> x(p，原理新节点的父节点)
                        xpp = (xp = x.parent) == null ? null : xp.parent;
                    }
                    // 如果xp不为空
                    if (xp != null) {
                        // xp变为黑色
                        xp.red = false;
                        // 如果xpp不为空
                        if (xpp != null) {
                            // xpp变为红色
                            xpp.red = true;
                            // 将新节点X的祖父节点xpp右旋
                            root = rotateRight(root, xpp);
                        }
                    }
                }
            }
            else {
                if (xppl != null && xppl.red) {
                    xppl.red = false;
                    xp.red = false;
                    xpp.red = true;
                    x = xpp;
                }
                else {
                    if (x == xp.left) {
                        root = rotateRight(root, x = xp);
                        xpp = (xp = x.parent) == null ? null : xp.parent;
                    }
                    if (xp != null) {
                        xp.red = false;
                        if (xpp != null) {
                            xpp.red = true;
                            root = rotateLeft(root, xpp);
                        }
                    }
                }
            }
        }
    }

    /**
     * 负责节点左旋
     * @param root 根节点
     * @param p == px，新节点的父节点
     * @return
     */
    static <K,V> HashMap.TreeNode<K,V> rotateLeft(HashMap.TreeNode<K,V> root,
                                                  HashMap.TreeNode<K,V> p) {
        /**
         * r：p的右子节点，就是外面的新节点X
         * pp：就是外面的ppx，新节点的祖父节点
         * rl：r的左子节点
         */
        HashMap.TreeNode<K,V> r, pp, rl;
        // 判断传入的p不为空，并且p的右子节点也不为空，将p的由子节点赋值给r，这个r其实就是外面的新节点X
        if (p != null && (r = p.right) != null) {
            // 将 r 的左子节点赋值给 p 的右子节点，并赋值给 rl，如果rl不为空（r的右子节点不为空），将rl的父节点设置为p
            if ((rl = p.right = r.left) != null)
                //rl的父节点设置为p
                rl.parent = p;
            // 将r的父节点设置为p的父节点，并赋值给pp，pp就是外面的xpp，X新节点的祖父节点，如果这个节点为空
            if ((pp = r.parent = p.parent) == null)
                // 将r设置为根节点，并变成黑色
                (root = r).red = false;
            // pp不为空，如果pp的左子节点等于p
            else if (pp.left == p)
                // pp的左子节点这是为r
                pp.left = r;
            // pp的左子节点不等于p
            else
                // pp的右子节点设置为r
                pp.right = r;
            // r的左子节点这是为p
            r.left = p;
            // 拍的父节点设置为r
            p.parent = r;
        }
        return root;
    }

    /**
     * 负责节点的右旋
     * @param root 根节点
     * @param p 是外面的xpp节点
     * @return
     */
    static <K,V> HashMap.TreeNode<K,V> rotateRight(HashMap.TreeNode<K,V> root,
                                                   HashMap.TreeNode<K,V> p) {
        /**
         * l：p.left，p节点的左子节点
         * pp：p的父节点
         * lr：是l的右子节点
         */
        HashMap.TreeNode<K,V> l, pp, lr;
        if (p != null && (l = p.left) != null) {
            if ((lr = p.left = l.right) != null)
                lr.parent = p;
            if ((pp = l.parent = p.parent) == null)
                (root = l).red = false;
            else if (pp.right == p)
                pp.right = l;
            else
                pp.left = l;
            l.right = p;
            p.parent = l;
        }
        return root;
    }