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

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

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的左父节点也可能是右父节点这里不影响，而且可以是任意颜色)

（编辑：晋中站长网）

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