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块

（编辑：PHP编程网 - 黄冈站长网）

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