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

x自己为根节点返回x。 x的父节点为玄色可能x的父节点是根节点直接返回不必要调动。 如若上述两个前提不满意的话，就要举办调动了，应承我再贴一点代码......没有代码说明起来很坚苦。

06 颜色调动

if (xp == (xppl = xpp.left)) 
 { 
 if ((xppr = xpp.right) != null && xppr.red) 
 { 
 xppr.red = false; 
 xp.red = false; 
 xpp.red = true; 
 x = xpp; 
 } 
} 

这里是一个典范的一个玄色节点的两个子节点都是赤色的以是要举办颜色调动，由于插入的都是赤色节点，当检测到祖父节点的阁下子节点都是赤色的时辰两个赤色就发生了斗嘴，以是先将节点举办这种颜色调动，将祖父节点酿成赤色，然后将祖父的两个子节点酿成玄色，这样我们插入的赤色节点就不会违反红黑树的法则了。

这里有人会有疑问，假如祖父节点是根节点呢，那样的话祖父节点也会酿成玄色，由于每次轮回举办插入均衡的操纵当举办这种颜色调动之后城市将插入节点的引用指向祖父节点，当举办下一轮轮回的时辰会优先检测当前节点是否是根节点，假如是根节点那就将颜色酿成玄色，下面看图：

当将节点指向祖父节点举办下一轮轮回时：

07 两个焦点旋转(左旋转和右旋转)

// 一旦我们进入到这里就声名白两件是情 
 // 1.x的父节点xp是赤色的，这样就碰着两个赤色节点相连的题目，以是必需颠末旋转调动。 
 // 2.x的祖父节点xpp不为空。 
  
 // 判定假如父节点是否是祖父节点的左节点 
 if (xp == (xppl = xpp.left)) 
 { 
 if ((xppr = xpp.right) != null && xppr.red) 
 {// ...... 
 } 
 // 进入到这个else内里声名。 
 // 父节点xp是祖父的左节点xppr。 
 // 祖父节点xpp的右节点xppr是玄色节点可能为空，默认划定空节点也是玄色的。 
 // 下面要判定x是xp的左节点照旧右节点。 
 else 
 { 
 // x是xp的右节点，此时的布局是：xpp左->xp右->x。这明明是第二中调动必要举办两次旋转，这里先举办一次旋转。 
 // 下面是第一次旋转。 
 if (x == xp.right) 
 { 
 root = rotateLeft(root, x = xp); 
 xpp = (xp = x.parent) == null ? null : xp.parent; 
 } 
 // 针对自己就是xpp左->xp左->x的布局可能因为上面的旋转造成的这种布局举办一次旋转。 
 if (xp != null) 
 { 
 xp.red = false; 
 if (xpp != null) 
 { 
 xpp.red = true; 
 root = rotateRight(root, xpp); 
 } 
 } 
 } 
 }  

颜色调动完成后进入下面的else块

（编辑：湖南网）

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