3分钟让你明白：HashMap之红黑树树化过程(7)

接着我们看向右旋转的代码

static <K, V> TreeNode<K, V> rotateRight(TreeNode<K, V> root, TreeNode<K, V> p) 
 { 
 // l：left，左节点。 
 // pp：parent parent，父节点的父节点。 
 // lr：left right，左节点的右节点。 
 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; 
 } 

3.刚进来的时候结构是这个样子。

在这里的P就是刚才传进来的XPP。

4.这里我们认为LR是存在的，其实这个不影响主要的旋转，为空就指向null呗，直接执行完9和10行。

9 if ((lr = p.left = l.right) != null) 
0 lr.parent = p; 

5.在这里我们假使PP是存在的，直接执行完11的表达式不再执行12行。(不再分析不存在的情况)。

11 if ((pp = l.parent = p.parent) == null) 
12 (root = l).red = false; 

6.由于11行的条件不符合，现在直接执行13行的表达式，不符合执行15行else，执行16行。

15 else 
16 pp.left = l; 

7.最后执行层17和18行。

17 l.right = p; 
18 p.parent = l; 

最终完成两次的旋转。

08 疑问?

大家可能觉得和刚才接不上其实是这样的，刚才在右旋转前的时候的图像是这个样的。

因为我们传进来的是XPP，所以结合上一次的向左旋转我们在向右旋转的时候看到全图应该是这个样子的。(注：XPPP可能是XPP的左父节点也可能是右父节点这里不影响，而且可以是任意颜色)

现在知道为什么XPPP可以是任意颜色的了吧，因为旋转过后X是黑色的即便XPPP是红色，此时我们又可以对两个红色的子节点进行颜色变换了，变换后X和XPPP有发生了颜色冲突，接着进行旋转直到根。

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)) 
 { 
 // 插入位置父节点在祖父节点的左边。 
 } 
 else 
 { 
 // 插入位置父节点在祖父节点的右边。 
 } 
 } 
 } 

我们值分析了插入位置父节点在祖父节点的左边的情况，并没有分析另外一面的对称情况，其实是一样的因为调用的都是相同的方法。

以上就是在1.8中的HashMap新引进的红黑树树化的过程，与原来的链表相比当同一个bucket上存储很多entry的话树形的查找结构明显要比链表线性的的效率要高。

（编辑：ASP站长网）