《Java8源码分析》图解HashMap链表如何转红黑树（含红黑树插入节点、平衡、变色、左/右旋）

《Java8源码分析》图解HashMap链表如何转红黑树（含红黑树插入节点、平衡、变色、左/右旋）

一、前言

1、链表是什么时候转红黑树的？

聊完了链表什么时候转红黑树，下面我们来看一下链表是怎么转红黑树的？

上面我们提到了treeifyBin()这个方法，链表转红黑树的逻辑也就在这个方法中。

二、源码分析

1、treeifyBin()

HashMap的putval()方法中调用treeifyBin()方法执行链表转红黑树操作；而treeifyBin()主要做两件事：

1、先根据hash计算出当前链表所在table数组中的位置，然后将其数据结构从​​单向链表Node​​​转为​​双向链表TreeNode​​​； 2、如果双向链表TreeNode的头节点hd不为null，则调用​​​treeify()​​​方法对TreeNode双向链表​​进行树型化操作​​；

final void treeifyBin(Node[] tab, int hash) { int n, index; Node e; // 数组长度小于64时，就先进行扩容 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); // 如果新增的node 要插入的数组位置已经有node存在了，取消插入操作 else if ((e = tab[index = (n - 1) & hash]) != null) { // 步骤一：遍历链表中每个节点，将Node转化为TreeNode // hd指向头节点，tl指向尾节点 TreeNode hd = null, tl = null; do { // 将链表Node转换为红黑树TreeNode结构 TreeNode p = replacementTreeNode(e, null); // 以hd为头结点，将每个TreeNode用prev和next连接成新的TreeNode链表 if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); // 步骤二：如果头结点hd不为null，则对TreeNode双向链表进行树型化操作 if ((tab[index] = hd) != null) // 执行链表转红黑树的操作 hd.treeify(tab); }}

接着我们看一下真正将链表转成红黑树的地方：​​treeify()​​方法；

2、treeify()

treeify()方法中大体上分为三步：

1、遍历TreeNode双向链表，确定​​待插入节点x​​​在其​​父节点的左边还是右边​​​，然后将其插入节点到红黑树中； 2、插入节点之后树结构发生变化，需要通过变色和旋转操作维护红黑树的平衡； 3、因为调整了红黑树，root节点可能发生了变化，所以需要把最新的root节点放到双向链表的头部，并插⼊到table数组中。

final void treeify(Node[] tab) { TreeNode root = null; // 最开始的x表示TreeNode双向链表的头结点 for (TreeNode x = this, next; x != null; x = next) { next = (TreeNode)x.next; x.left = x.right = null; // 构建树的根节点 if (root == null) { x.parent = null; x.red = false; root = x; } else { // 第一部分 K k = x.key; int h = x.hash; Class kc = null; // p 表示parent节点 for (TreeNode p = root;;) { // dir表示x节点在parent节点的左侧还是右侧 int dir, ph; // ph表示parent节点的hash值 K pk = p.key; // pk表示parent节点的key值 // x节点在parent节点的左侧 if ((ph = p.hash) > h) dir = -1; // x节点在parent节点的右侧 else if (ph < h) dir = 1; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) dir = tieBreakOrder(k, pk); // 第二部分 TreeNode xp = p; // xp表示x的父节点 // 如果p节点的左节点/右节点不为空，则令p = p.left/p.right，继续循环 // 直到p.left/p.right为空 if ((p = (dir <= 0) ? p.left : p.right) == null) { // 令待插入节点x的父节点为xp, 即p x.parent = xp; // 根据dir判断插入到xp的左子树(<0)还是右子树(>0) if (dir <= 0) xp.left = x; else xp.right = x; // 往红黑树中插入节点后，进行树的平衡操作 root = balanceInsertion(root, x); break; } } } } // 将root节点插入到table数组中 moveRootToFront(tab, root);}

在往红黑树中插入一个节点之后，会调用​​balanceInsertion()​​方法进行树的平衡操作，我们来看一下红黑树是怎么进行平衡的？

3、balanceInsertion()

这里和TreeMap中插入节点之后进行的红黑树平衡操作​​fixAfterInsertion()​​​类似。在文章：​​图解TreeMap的红黑树平衡操作fixAfterInsertion()，接着手撕红黑树添加节点​​中我们详细介绍；

对红黑树进行平衡操作时，主要分两部分：直接返回、变色旋转后返回；

第一部分：​​直接返回​​根节点：1、如果待插入节点x​​没有parent节点​​，直接把​​x的节点变为黑色​​，并​​作为根节点返回​​；2、如果​​x的父节点为黑色​​、或者​​没有祖父节点​​，则​​直接返回​​根节点root；第二部分：根据x节点在父节点xp的左侧还是右侧、xp节点再其父节点xpp的左侧还是右侧进行​​旋转、变色​​；如果x的父节点xp是祖父节点xpp的​​左子节点​​：0）若x的祖父节点xpp的右子节点xppr存在并且是红色，直接交换祖父节点和其子节点的颜色、并返回。 1）若x是其父节点xp的右子节点，​​交换x和xp的位置​​，然后​​对x进行左旋​​；2）接着设置​​父节点xp为黑色​​、​​祖父节点xpp为红​​色，以​​xpp节点为轴右旋​​。x的父节点xp是祖父节点的右子节点：这里和上面的类似，只是左旋变右旋、右旋变左旋；0）若x的祖父节点xpp的左子节点xppl并在并且是红色，直接交换祖父节点和其子节点的颜色、并返回。 1）若x是其父节点xp的左子节点，​​交换x和xp的位置​​，然后​​对x进行右旋​​；2）接着设置​​父节点xp为黑色​​、​​祖父节点xpp为红​​色，以​​xpp节点为轴左旋​​。

代码如下：

static TreeNode balanceInsertion(TreeNode root, TreeNode x) { // 将待插入节点x的节点颜色置为红色 x.red = true; for (TreeNode xp, xpp, xppl, xppr;;) { // 1、如果x没有父节点，自己变为黑色节点、作为根节点返回 if ((xp = x.parent) == null) { x.red = false; return x; } // 2、如果x的父节点为黑色或者没有祖父节点，则直接返回root else if (!xp.red || (xpp = xp.parent) == null) return root; // 3、如果x的父节点xp是祖父节点的左子节点 if (xp == (xppl = xpp.left)) { // 1）仅变色： // 如果xp和xppr都是红色节点，则把xppr、xp置为黑色、zpp置为红色。 if ((xppr = xpp.right) != null && xppr.red) { xppr.red = false; xp.red = false; xpp.red = true; x = xpp; } // 2）旋转 + 变色： else { // （1）如果x 是其父节点xp的右子节点。令当前节点为其父节点，然后对当前节点x进行左旋 if (x == xp.right) { root = rotateLeft(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } // （2）如果x的父节点xp不为空 if (xp != null) { // 令xp的颜色为黑色 xp.red = false; // 如果x的祖父节点xpp不为空 if (xpp != null) { // 令xpp的颜色为红色 xpp.red = true; // 对祖父节点xpp进行右旋 root = rotateRight(root, xpp); } } } } // 4、x的父节点xp是祖父节点的右子节点 else { // 逻辑和3、类似，只是单纯的左变右、右变左 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); } } } } }}

可能上面一顿文字描述，不够直观，下面我们结合源代码图解分析；

上面第二部分的场景一：

x的父节点xp是祖父节点xpp的​​左子节点​​；

0）变色操作

若x的祖父节点xpp的左子节点xppl并在并且是红色，直接交换祖父节点和其子节点的颜色；

1、2）左旋+变色+右旋操作

（1）步骤一：将树节点左旋到同一侧；

（2）步骤二：父节点和祖父节点变色，以祖父节点xpp为轴右旋；

上面第二部分的场景二：

x的父节点xp是祖父节点xpp的​​右子节点​​；

0）变色操作

若x的祖父节点xpp的左子节点xppl并在并且是红色，直接交换祖父节点和其子节点的颜色；

1、2）右旋+变色+左旋操作

（1）步骤一：将树节点右旋到同一侧；

（2）步骤二：父节点和祖父节点变色，以祖父节点xpp为轴左旋；

4、rotateLeft()

左旋操作是将待旋转节点p的和其右子节点r交换位置和所有的节点关联关系，具体如下：

1、令当前旋转节点​​p的右子节点​​​为其​​原右子节点r的左子节点rl​​（右儿子节点中的 左孙子节点）；rl节点的parent节点为p；2、先令r的parent指向p的parent，然后再判断p节点的父节点pp的情况：1）pp为空时，设置r为root节点，并将r的parent节点置为空；2）p节点是父节点pp的左子节点时，pp的的左子节点变更为r；3）p节点是父节点pp的右子节点时，pp的的右子节点变更为r；3、最后将r的left指向p，p的parent指向r；

static TreeNode rotateLeft(TreeNode root, TreeNode p) { TreeNode r, pp, rl; // r为p的右子节点，pp为p的父节点，rl为r的左子节点 // 如果p的右节点不为空 if (p != null && (r = p.right) != null) { // rl赋值，并将p.right指向r.left if ((rl = p.right = r.left) != null) // rl的父节点为p rl.parent = p; // 1）当p节点没有父节点时，先令r的父节点为p的父节点 if ((pp = r.parent = p.parent) == null) // 把p节点的右子节点r变为黑色，并作为root节点 (root = r).red = false; // 2）p节点在其父节点pp的左子节点 else if (pp.left == p) // 令pp节点的左子节点为r pp.left = r; // 3）p节点在其父节点的右子节点 else // 令pp节点的右子节点为r pp.right = r; // 令r的左子节点为p r.left = p; // p的父节点为r p.parent = r; } return root;}

结合源代码图解分析：

1）左旋操作的最终态：

2）细化每种情况

5、rotateRight()

右旋操作和左旋类似，只是左变右、右变左；本质上逻辑都是一样的；

static TreeNode rotateRight(TreeNode root, TreeNode p) { TreeNode l, pp, lr; // l为p的左子节点，pp为p的父节点，lr为l的右子节点 // 如果p的左节点不为空 if (p != null && (l = p.left) != null) { // rl赋值，并将p.left指向r.right if ((lr = p.left = l.right) != null) // 设置lr的父节点为p lr.parent = p; // 1）将l的parent指向p的parent，如果p的父节点pp为空 if ((pp = l.parent = p.parent) == null) // 将的l的颜色设置为黑色，并作为根节点root (root = l).red = false; // 2）p节点在其父节点pp的右子节点 else if (pp.right == p) // 令pp节点的右子节点为l pp.right = l; // 3）p节点在其父节点pp的左子节点 else // pp节点的左子节点为l pp.left = l; // 令l的右子节点为p l.right = p; // p的父节点为l p.parent = l; } return root;}

结合源代码图解分析：

既然左旋的大家已经看懂了，右旋大家可以尝试一下自己画个图呀；锻炼一下自己的动手能力；

6、moveRootToFront()

在​​treeify()​​​方法中调用​​balanceInsertion()​​​对红黑树平衡完之后，最后会进入​​moveRootToFront()​​方法，将root节点放到整条双向链表的头部，并插⼊到table数组中。

注意这里说的双向链表是红黑树中的​​TreeNode​​。

static void moveRootToFront(Node[] tab, TreeNode root) { int n; if (root != null && tab != null && (n = tab.length) > 0) { // 判断table数组中存储的元素是不是最新的root节点 int index = (n - 1) & root.hash; TreeNode first = (TreeNode)tab[index]; // 如果不是 if (root != first) { // 重塑双向链表的连接，把root放到整个链表的头位置，并将root插入到table数组中 // A <--> root <--> C 变为 root <--> A <--> C Node rn; // rn表示root的下一个节点 tab[index] = root; TreeNode rp = root.prev; // rp表示root的前一个节点 if ((rn = root.next) != null) // rn的prev节点修改为rp ((TreeNode)rn).prev = rp; if (rp != null) // rp的next节点修改为rn rp.next = rn; if (first != null) // 把root节点移动到first节点之前 first.prev = root; root.next = first; // root的前一个节点置为空 root.prev = null; } // 对整个红黑树结构执行check校验 assert checkInvariants(root); }}

重塑双向链表的连接，把root放到整个链表的头位置，并将root插入到table数组中；

将A <–> root(B) <–> C 变为 root(B) <–> A <–> C。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。