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

我们已知xp是xpp的左节点，首先判断了x是xp的左节点还是右节点，如果是右节点的话构成了下面的结构。

这中结构需要进行双旋转，首先先进行一次向左旋转。

7.1 左旋转

 1 static <K, V> TreeNode<K, V> rotateLeft(TreeNode<K, V> root, TreeNode<K, V> p) 
 2 { 
 3 // r：right，右节点。 
 4 // pp：parent parent，父节点的父节点。 
 5 // rl：right left，右节点的左节点。 
 6 TreeNode<K, V> r, pp, rl; 
 7 if (p != null && (r = p.right) != null) 
 8 { 
 9 if ((rl = p.right = r.left) != null) 
10 rl.parent = p; 
11 if ((pp = r.parent = p.parent) == null) 
12 (root = r).red = false; 
13 else if (pp.left == p) 
14 pp.left = r; 
15 else 
16 pp.right = r; 
17 r.left = p; 
18 p.parent = r; 
19 } 
20 return root; 
21 } 

1.刚进入方法时，状态如下图。(RL可能是空的)

2.进入了if块后执行到第10行后。

9 if ((rl = p.right = r.left) != null) 
10 rl.parent = p; 

此时如果9行的条件符合的话执行10行RL指向P，如果RL为null的话，P的右节点指向null。

3.接着看11和12行代码。

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

首先我们看11行if里面的赋值语句所造成的影响。

在if里面的表达式不管符不符合条件()内的内容都会执行。

如果符合条件的话会执行12行的代码，变成了下面的结果。

由于PP为空所以只剩下这三个。

4.如果11行的条件为假的话，执行完11行()内的表达式后执行13行

13 else if (pp.left == p) 
14 pp.left = r; 

满足条件的话R和PP互相关联。

5.由于进入了13和14行所以不进入15和16行的else语句。

15 else 
16 pp.right = r; 

6.看17和18行。

17 r.left = p; 
18 p.parent = r; 

最终执行完了一个旋转变成了我们开始说的第一种旋转的形式，这个结构还需要向右旋转一次。

if (x == xp.right) 
 { 
 root = rotateLeft(root, x = xp); 
 xpp = (xp = x.parent) == null ? null : xp.parent; 
 } 
xpp = (xp = x.parent) == null ? null : xp.parent; 

执行完上面的代码，旋转后调整x，xp，和xpp的关系得到下图。

7.2 右旋转

if (xp != null) 
{ 
xp.red = false; 
if (xpp != null) 
{ 
xpp.red = true; 
root = rotateLeft(root, xpp); 
} 
} 

1.首先让XP变成黑色。

2.如果XPP不为空的话变成红色。

由于我们在rotateLeft(root, xpp)，传进来的是XXP所以下面的的旋转中实际上就是对XP和XXP执行了一次与上面的方向相反其他完全相同的旋转。

（编辑：ASP站长网）