3分钟让你大白：HashMap之红黑树树化进程

我们已知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; 

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!