HashMap红黑二叉树

输入平衡操作

static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                    TreeNode<K,V> x) {
            //root是根节点
            //x是已经插入的节点
            //刚插入节点设置为红节点
            x.red = true;
            //xp是父节点，xpp是祖父节点，xppl是左叔父节点，xppr是右叔父节点
            for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
                //循环进行平衡操作
                if ((xp = x.parent) == null) {
                    //如果父节点 为空，代表x是根节点，直接设置为黑节点，并返回
                    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;
                    }
                    else {
                        //叔父节点是空节点或者黑色节点
                        if (x == xp.right) {
                            //如果插入的节点x是父节点的右子节点，则：
                            //需要对父节点进行左旋转
                            root = rotateLeft(root, x = xp);
                            //旋转之后，重新去祖父节点
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        if (xp != null) {
                            //如果父节点不为空，则
                            //父节点设置为黑色节点
                            xp.red = false;
                            if (xpp != null) {
                                //祖父节点不为空，
                                //将祖父节点设置为红色节点
                                xpp.red = true;
                                //对祖父节点进行右旋处理
                                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);
                            }
                        }
                    }
                }
            }
        }

平衡操作：

• 当前的节点标间为红节点（原因：）
• 如果当前节点是根节点 ，改为黑节点，并作为根节点返回
• 如果当前节点的父节点是黑节点或者根节点，则直接返回根节点，没有操作不平衡
• 如果当前节点的叔父节点（不了是左叔父或者右叔父节点）不为空且是红色节点，代表父节点是黑色，则直接进行变色处理：父节点和叔父节点变为黑节点，同时祖父节点变为红色节点，将祖父节点作为当前节点继续进行一样的平衡操作
• 如果叔父节点为空或者是黑色节点，那么父节点很大可能是红节点，那就可能存在连续两个红节点破坏红黑二叉树特性，就需要进行选择操作：
  • 如果当前节点是其父节点的右子树，代表右子树深度可能比左子树还深，需要先将当前节点进行左旋转，将当前节点变为其右子节点的左子树，同时其右子节点提升为当前节点的父节点，这样可以减少右子树的深度，左旋转之后将父节点变为黑节点，祖父节点变为红节点，祖父节点不为空的情况下再对祖父节点进行右旋转，接着继续下一步的平衡操作
  • 如果当前节点是父节点的左子树，代表左子树深度可能比右子树还深，需要先将当前节点进行右旋转，将当前节点变为其左子节点的右子树，同时其右子树提升为当前节点的父节点，这样可以减少左子树的深度，右旋转之后将父节点变为黑节点，祖父节点变为红节点，祖父节点不为空的情况下再对祖父节点进行左旋转，接着继续下一步的平衡操作

总结：

• 平衡操作是让树保持红黑二叉树的特性，如果发现不满足红黑二叉树的特性就需要变色、左旋、右旋，左旋或者右旋操作可以降低深度
• 发生旋转的条件：
  • 叔父节点为空或者是黑节点
  • 如果当前节点是祖父节点的左子孙树，同时是父节点的右子树，则对先对其父节点进行左旋再对其祖父节点进行右旋操作；如果当前节点是祖父节点的右子孙树，同时是父节点的左子树，则对先对父节点进行右旋操作，再对其祖父节点做左旋操作

左旋

static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                              TreeNode<K,V> p) {
            //r是当前节点的右子节点，rl是右子节点的左子节点，pp是当前节点的父节点
            TreeNode<K,V> r, pp, rl;
            if (p != null && (r = p.right) != null) {
                //当前节点不为空且右子节点不为空
                if ((rl = p.right = r.left) != null)
                    //将当前节点的右节点指向原右子节点的左子节点
                    //同时原右子节点的左子节点的父节点指向当前节点
                    rl.parent = p;
                if ((pp = r.parent = p.parent) == null)
                    //原右子节点的父节点指向当前节点的父节点
                    //同时设置原右子节点为黑节点，同时将根节点设置为原右子节点
                    (root = r).red = false;
                else if (pp.left == p)
                    //父节点的左子节点 == 当前节点
                    //父节点的左子节点改为原右子节点
                    pp.left = r;
                else
                    //父节点的右子节点 == 当前节点
                    //父节点的右子节点改为原右子节点
                    pp.right = r;
                //原右子节点的左子节点指向当前节点
                r.left = p;
                //当前节点的父节点指向原右子节点
                p.parent = r;
            }
            返回根节点
            return root;
        }

总结：

• 左旋操作是对当前节点进行顺时针旋转
• 将右子节点变为当前节点父节点，即父子关系互换，且当前节点是作为原右子节点的左子树（排序二叉树的特性：右比左及父节点大）
• 将右子节点的左子树作为当前节点的右子树（排序二叉树的特性：右比左及父节点大）

总的来说可以把左旋理解为把当前节点作为其右子节点的左子树，同时保持排序二叉树的特性

右旋

static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                               TreeNode<K,V> p) {
            //l是当前节点的左子节点，lr是左子节点的右子节点，pp是当前节点的父节点
            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;
        }

总结：

• 右旋操作是对当前节点进行逆时针旋转
• 将左子节点变为当前节点父节点，即父子关系互换，且当前节点是作为原左子节点的右子树（排序二叉树的特性：右比左及父节点大）
• 将左子节点的右子树作为当前节点的左子树（排序二叉树的特性：左比右及父节点大）

总的来说可以把右旋理解为把当前节点作为其左子节点的右子树，同时保持排序二叉树的特性