美文网首页技术文章
HashMap—红黑树算法结构详解

HashMap—红黑树算法结构详解

作者: BlackJava | 来源:发表于2018-09-11 12:02 被阅读627次

最近在撸Java8-Hashmap源码的时候遇到一个问题红黑树的存储结构,当时看的时候还是有点迷糊的,而且对于左旋还是右旋,直接就缴械投降了。现在花一篇文章来梳理一下自己对这个结构算法的理解。

红黑树也叫自平衡二叉查找树或者平衡二叉B树,
时间复杂度为O(log n)
高度h <= log2(n+1)

红黑树的特点
  性质1. 节点是红色或黑色。
  性质2. 根节点是黑色。
  性质3 每个叶节点(NIL节点,空节点)是黑色的。
  性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

注意:这里有一点需要解释的就是,插入节点一定是插入一个红色的节点,为什么呢?因为这样只是有可能违背性质4,其余四个性质都是符合的,可以减小复杂度。以下我们以HashMap的红黑树实现为例。

插入实现
  /**
     * Tree version of putVal.
     */
    final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                   int h, K k, V v) {
        Class<?> kc = null;
        boolean searched = false;
        TreeNode<K,V> root = (parent != null) ? root() : this;
        for (TreeNode<K,V> p = root;;) {
            int dir, ph; K pk;
            // 比较要插入值 与 节点的 hash值等属性 的大小
            // 确定大小之后然后选择 左右子树 循环继续比较
            if ((ph = p.hash) > h)
                dir = -1;
            else if (ph < h)
                dir = 1;
            else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                return p;
            else if ((kc == null &&
                      (kc = comparableClassFor(k)) == null) ||
                     (dir = compareComparables(kc, k, pk)) == 0) {
                if (!searched) {
                    TreeNode<K,V> q, ch;
                    searched = true;
                    if (((ch = p.left) != null &&
                         (q = ch.find(h, k, kc)) != null) ||
                        ((ch = p.right) != null &&
                         (q = ch.find(h, k, kc)) != null))
                        return q;
                }
                dir = tieBreakOrder(k, pk);
            }

            TreeNode<K,V> xp = p;
            // 只有确认了 要插入的位置的 左子树 或者 右子树为空,即找到了要插入节点的位置
            if ((p = (dir <= 0) ? p.left : p.right) == null) {
                Node<K,V> xpn = xp.next;
                // 创建新的 树的叶子节点
                TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
               // 插入到指定的 分支上
                if (dir <= 0)
                    xp.left = x;
                else
                    xp.right = x;
                xp.next = x;
                x.parent = x.prev = xp;
                if (xpn != null)
                    ((TreeNode<K,V>)xpn).prev = x;
                // 这里需要注意了 这有执行了两步操作,
                // balanceInsertion这一步涉及到了 红黑树的平衡算法,我们只看它
                moveRootToFront(tab, balanceInsertion(root, x));
                return null;
            }
        }
    }

在看平衡算法之前,我们需要对红黑树的特性进行详细说明,确保知道什么时候该旋转,什么时候采用什么旋转。

第一:插入的节点是红色
第二:平衡、或者 旋转算法是对三层树形结构进行的。如果你站在整个树结构上看,你会发现无从下手
第三:什么时候该旋转,不满足h <= log2(n+1),即前两层树形结构不是满二叉树
第四:在插入节点之前,树的结构是符合红黑树的(这个前提很重要

balanceInsertion平衡算法
  static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) {
        x.red = true;
        for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
            // 这是一层树形结构,也就是只有一个节点
            // 直接进行着色操作
            if ((xp = x.parent) == null) {
                x.red = false;
                return x;
            }
            // 这里是二层树形结构,xp 存在,或者xpp 为空
            // 这里需要说明一下,有人会认为这不仅仅包含二层树形结构,可能还有三层
            // 从条件上来说是的,可能包含三层,但是这里有一个我们上面说的前提,那就是插入之前必须是红黑树,
             // 那也就是说!xp.red 意思就是 xp 为黑色节点,而且xp 是符合红黑树的,那么插入一个红色节点是不会改变它是红黑树的特性
            // 反过来想插入之前的问题
            // 这里我们把问题缩小一点,就插入点的三层树形结构。而且插入之前还必须符合红黑树
            // 如果xp 插入之前是黑色的并且符合红黑树,这种特性是不是跟只有一个根节点是一样的
            else if (!xp.red || (xpp = xp.parent) == null)
                return root;
            // 三层结构,如果是左分支
            if (xp == (xppl = xpp.left)) {
                // 这里是判断前两层是否是满二叉树,也就是是否满足h <= log2(n+1)
                // 如果满足是不需要进行 旋转的,因为无法对其旋转(左旋,右旋),
                // 也不需要旋转,只需要进行重新着色就可以满足红黑树的五大特性了
                if ((xppr = xpp.right) != null && xppr.red) {
                    xppr.red = false;
                    xp.red = false;
                    xpp.red = true;
                    x = xpp;
                }
                else {
                    // 接下来就是 不满足满二叉树,或者说 不满足h <= log2(n+1)
                    // 这个时候我们就需要考虑旋转了,怎样旋转呢,这里我先说结果,后面分析原因,或者为什么
                    if (x == xp.right) {
                        // 树形结构是  L — R   -->  左旋,变成 L— L树形结构
                        root = rotateLeft(root, x = xp);
                        // x、xp、xpp 重新赋值
                        xpp = (xp = x.parent) == null ? null : xp.parent;
                    }
                    if (xp != null) {
                        // xp 着色
                        xp.red = false;
                        if (xpp != null) {
                            // xpp 着色
                            xpp.red = true;
                            // L — L   --> 右旋
                           // 将三层树形结构  右旋 变成一个 二层结构,满足 h <= log2(n+1) 特性
                            root = rotateRight(root, xpp);
                        }
                    }
                }
            }
            else {
                 //  这里也是一样的
                // 判断前两层是否是满二叉树,也就是是否满足h <= log2(n+1)
                // 如果满足是不需要进行 旋转的,因为无法对其旋转(左旋,右旋),
                // 也不需要旋转,只需要进行重新着色就可以满足红黑树的五大特性了
                if (xppl != null && xppl.red) {
                    xppl.red = false;
                    xp.red = false;
                    xpp.red = true;
                    x = xpp;
                }
                else {
                   // 接下来也是 不满足满二叉树,或者说 不满足h <= log2(n+1)
                    if (x == xp.left) {
                        // 树形结构是  R — L   -->  右旋,变成 R— R树形结构
                        root = rotateRight(root, x = xp);
                        // x、xp、xpp 重新赋值
                        xpp = (xp = x.parent) == null ? null : xp.parent;
                    }
                    if (xp != null) {
                        // xp 着色
                        xp.red = false;
                        if (xpp != null) {
                            // xpp 着色
                            xpp.red = true;
                            // R — R   --> 右旋
                           // 将三层树形结构  左旋 变成一个 二层结构,满足 h <= log2(n+1) 特性
                            root = rotateLeft(root, xpp);
                        }
                    }
                }
            }
        }
    }

接下来我们重点说一下,左旋和右旋,首先不管是左旋还是右旋,都是只对两个节点进行修改,有一个节点的位置是不发生改变的。

  • 第一什么时候需要进行旋转 ?,以及需要旋转几次 ?

判断树的结构是否满足h <= log2(n+1),如果不满足则需要进行旋转,如果满足只需要重新进行着色即可。

  • 第二是什么叫做左旋,还是右旋 ?

判断采用左旋,还是右旋,就是当前这两个节点的位置关系,是左分支,还是右分支,则相应的旋转之后是相反的分支,例如:现有是 左分支的关系, 旋转之后就是右分支,则是进行了右旋操作,同样现有关系是右分支的关系,旋转之后就是左分支,则是进行了 左旋操作
把上面balanceInsertion平衡算法统计一下,我们可以得到下面
L(左分支)——L(左分支) → R (右旋)
L(左分支)——R(右分支)→ L(左旋)——R (右旋)
R(右分支)——R(右分支)→ L(左旋)
R(右分支)——L(左分支)→ R (右旋)——L(左旋)

下面我们以图来看一看包含两步的旋转过程来,对照一下
L(左分支)——R(右分支)→ L(左旋)——R (右旋)
R(右分支)——L(左分支)→ R (右旋)——L(左旋)
  • 第三:如何确定我该做左旋,还是右旋

个人理解,如果原来的树曲曲折折,需要先掰直了下面部分,如果是直线的树了 再把上面部分掰弯,形成一个倒V型。这个只是方面理解,真正的原因是,如果不采用上面的步骤进行旋转,旋转顺序换掉,都会得到一种结果那就是,整个二叉树不成立了,失去了二叉树的意义了。当然我们也可以一步到位,以空间换时间,这是没有问题的,从复杂度来讲左旋和右旋是最精炼的,最基础的,可以完美适配的。

rotateLeft(左旋)
  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.parent = p;
            if ((pp = r.parent = p.parent) == null)
                // 只有当p 已经探到了树的底部的时候,左旋,会改变根的指向,所以这里需要修改掉root 的指向
                (root = r).red = false;
            else if (pp.left == p)
                pp.left = r;
            else
                pp.right = r;
            r.left = p;
            p.parent = r;
        }
        return root;
    }
rotateRight(右旋)
  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.parent = p;
            if ((pp = l.parent = p.parent) == null)
                // 只有当p 已经探到了树的底部的时候,左旋,会改变根的指向,所以这里需要修改掉root 的指向
                (root = l).red = false;
            else if (pp.right == p)
                pp.right = l;
            else
                pp.left = l;
            l.right = p;
            p.parent = l;
        }
        return root;
    }

我相信看完上面的解释,你对左旋和右旋的实现会有了一个更为清晰的认知了。
好了,分析到这里了。

相关文章

网友评论

    本文标题:HashMap—红黑树算法结构详解

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