一、前言
1、链表是什么时候转红黑树的？
1、在putVal()方法中如果链表长度
大于阈值8；会进入到treeifyBin()方法中执行链表转红黑树操作；
2、HashMap中有个MIN_TREEIFY_CAPACITY变量 等于64，表示允许执行treeifyBin()链表转红黑树操作时HashMap数组的最小容量；如果数组容量容量小于64，则先执行扩容操作；
聊完了链表什么时候转红黑树，下面我们来看一下链表是怎么转红黑树的？
上面我们提到了treeifyBin()这个方法，链表转红黑树的逻辑也就在这个方法中。
二、源码分析
1、treeifyBin()
HashMap的putval()方法中调用treeifyBin()方法执行链表转红黑树操作；而treeifyBin()主要做两件事：
1、先根据hash计算出当前链表所在table数组中的位置，然后将其数据结构从
单向链表Node转为双向链表TreeNode；
2、如果双向链表TreeNode的头节点hd不为null，则调用treeify()方法对TreeNode双向链表进行树型化操作；
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> 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<K,V> hd = null, tl = null;
do {
// 将链表Node转换为红黑树TreeNode结构
TreeNode<K,V> 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<K,V>[] tab) {
TreeNode<K,V> root = null;
// 最开始的x表示TreeNode双向链表的头结点
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)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<K,V> 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<K,V> 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 <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
// 将待插入节点x的节点颜色置为红色
x.red = true;
for (TreeNode<K,V> 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 <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> 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 <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> 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 <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
// 判断table数组中存储的元素是不是最新的root节点
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
// 如果不是
if (root != first) {
// 重塑双向链表的连接，把root放到整个链表的头位置，并将root插入到table数组中
// A <--> root <--> C 变为 root <--> A <--> C
Node<K,V> rn; // rn表示root的下一个节点
tab[index] = root;
TreeNode<K,V> rp = root.prev; // rp表示root的前一个节点
if ((rn = root.next) != null)
// rn的prev节点修改为rp
((TreeNode<K,V>)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。
还没有评论，来说两句吧...