上篇文章说到，若是链表的长度>=7的时候，链表会转成红黑树，本文就来具体的剖析一下红黑树的扭转过程。
首先来看一段代码
本文的提到的红黑树的转换首要是在hd.treeify(tab);这个方式里
具体代码如下，下面来剖析一下具体的过程final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
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;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
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;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
具体看for轮回，第一次执行的时候，root一定是null，所以root指向第一个节点。
为了明确转换的过程，举一个例子如下图所示，假设我们有一个长度为5的链表，用这5个数来表述一下具体的转换的道理，这里举的例子对照简洁，其实只要这个会了，其他的也就一通百通。
按照代码逻辑，第一次是root一定是会指向第一个节点，默认是该节点为黑，即如下图所示。
第二次轮回，则会走到 else里，这里又有一个for轮回，这个for轮回的目的首要是找到合适的位置去插入第二个节点。
在判读hash的时候，我们发现链内外的第二个节点的hash为2，则会在右子树进行插入，究竟如下图所示：
然后会执行到下面的方式
具体的代码如下：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;
}
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) {
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);
}
}
}
}
}
}
在此次轮回里，我们能够获得一个结论，当前的节点会点窜为红树，结果如下：
第三次轮回，按照以上的步伐，将在2的右节点插入3，结果如下图所示
持续执行balanceInsertion这个方式，到这里就显现有意思的事情了，前方高能，注重旁观。
X节点指向3， root为跟节点指向1.
首先设置x节点为红，则整个树酿成了黑->红->红，显着不相符红黑树的特征，则意味着接下来要发生扭转来包管树的均衡。
下面来一行代码一行代码进行剖析。
首先界说了xp, xpp, xppl, xppr
四个暂时变量，从这里也能够看出每个变量代表的寄义。
xp：节点x的父亲节点
xpp：节点x的父亲节点的父亲节点xppl：节点x的父亲节点的父亲节点的左孩子节点
xppr：节点x的父亲节点的父亲节点的右孩子节点
这几个变量先搞清楚，有助于我们接下来的代码剖析。
此时，几个变量指向的地址如图上的红色圆圈里所示。
按照上面的指示，代码会直接执行到下图所示代码块
设置xp节点为黑，xpp节点为红。
紧接着执行root = rotateLeft(root, xpp);
这个方式，这里又有意思了，前方持续高能，即将发生左旋。
注重，这里传入的两个值为root和xpp，这一次两者指向统一个节点。
看下这个方式的具体代码
r指向了p的右节点，此时一定不为空（参照带有红圆圈的那张图）即此时
r指向了节点2。
先来看第一个判断：if ((rl = p.right = r.left) != null)
此时r的左节点一定为空，则能够看出p的右节点此时不在指向r，而是指向了空节点，此时如下图所示：节点1跟右节点断开，节点1的右节点指向为空。
此时r的left则为空，第一个if不知足。if ((pp = r.parent = p.parent) == null)
p此时指向的是根节点，所以parent一定为空，前提知足，
root节点移动，指向r节点，也就是如今的节点2，同时设置为黑
此时的究竟如下：
最后一步：
p的parent节点指向r，r的left节点指向p，则本次左旋到此完成，最后的究竟如下所示：
节点4和节点5的具体过程这里就不在胪陈了，扭转过程和这里很雷同，无非就是左旋酿成了右旋，有乐趣的小伙伴能够本身看下代码，整体过程跟我上面剖析的雷同。
到此，你看领略整个过程了吗？
进展对正在入坑java的小伙伴有所匡助，若是觉着对你有效，迎接收藏并转发，也能够私信我商议问题，感谢。
