美文网首页
HashMap红黑二叉树

HashMap红黑二叉树

作者: jxiang112 | 来源:发表于2022-04-22 10:06 被阅读0次

输入平衡操作

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;
        }

总结:

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

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

相关文章

  • 算法之红黑树

    JDK1.8引入了红黑树(HashMap,CurrentHashMap) 红黑树是一个平衡的二叉树,但不是一个完美...

  • 源码阅读 - HashMap

    本文涉及到红黑树的部分参考二叉树 - 红黑树 0. HashMap是什么 一种增删改查操作(不考虑哈希冲突)能达到...

  • HashMap底层实现原理(上)

    本来想先在专栏里简单的说一下二叉树,红黑树的内容后再说HashMap的,但看到评论区里不断的出现HashMap这个...

  • <--个人成长笔记系列-->知识点解析之HashMap(二)

    JAVA知识点: (掌握)红黑树:是一个特殊的二叉树 (掌握)HashMap源码分析: (1)pu...

  • HashMap

    HashMap JDK1.8中如果链表长度到达阀值(默认是8),就会将链表转换成红黑二叉树。 threshold=...

  • 红黑二叉树

    红黑二叉树 红黑二叉树(简称:红黑树),它首先是一棵二叉树,同时也是一棵自平衡的排序二叉树。 红黑树在...

  • 红黑树

    啥是红黑树,红黑树 = 二叉树

  • HashMap红黑二叉树

    输入平衡操作 平衡操作: 当前的节点标间为红节点(原因:) 如果当前节点是根节点 ,改为黑节点,并作为根节点返回 ...

  • HashMap

    HashMap是数组+链表+红黑树。 Node.hash是key的hash1.8的HashMap增加了红黑树来增加...

  • Java类集框架 —— LinkedHashMap源码分析

    前言 我们知道HashMap底层是采用数组+单向线性链表/红黑树来实现的,HashMap在扩容或者链表与红黑树转换...

网友评论

      本文标题:HashMap红黑二叉树

      本文链接:https://www.haomeiwen.com/subject/njniertx.html