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

我们看balanceInsertion

static <K, V> TreeNode<K, V> balanceInsertion(TreeNode<K, V> root, TreeNode<K, V> x) 
 { 
 // 正如开头所说，新插手树节点默认都是赤色的，不会粉碎树的布局。 
 x.red = true; 
 // 这些变量名不是作者任意界说的都是故意义的。 
 // xp：x parent，代表x的父节点。 
 // xpp：x parent parent，代表x的祖父节点 
 // xppl：x parent parent left，代表x的祖父的左节点。 
 // xppr：x parent parent right，代表x的祖父的右节点。 
 for (TreeNode<K, V> xp, xpp, xppl, xppr;;) 
 { 
 // 假如x的父节点为null声名只有一个节点，该节点为根节点，根节点为玄色，red = false。 
 if ((xp = x.parent) == null) 
 { 
 x.red = false; 
 return x; 
 }  
 // 进入else声名不是根节点。 
 // 假如父节点是玄色，那么大吉大利（今晚吃鸡），赤色的x节点可以直接添加到玄色节点后头，返回根就行了不必要任何多余的操纵。 
 // 假如父节点是赤色的，但祖父节点为空的话也可以直接返回根此时父节点就是根节点，由于根必需是玄色的，添加在后头没有任何题目。 
 else if (!xp.red || (xpp = xp.parent) == null) 
 return root; 
  
 // 一旦我们进入到这里就声名白两件是情 
 // 1.x的父节点xp是赤色的，这样就碰着两个赤色节点相连的题目，以是必需颠末旋转调动。 
 // 2.x的祖父节点xpp不为空。 
  
 // 判定假如父节点是否是祖父节点的左节点 
 if (xp == (xppl = xpp.left)) 
 { 
 // 父节点xp是祖父的左节点xppr 
 // 判定祖父节点的右节点不为空而且是否是赤色的 
 // 此时xpp的阁下节点都是红的，以是直接举办上面所说的第三种调动，将两个子节点酿成玄色，将xpp酿成赤色，然后将赤色节点x顺遂的添加到了xp的后头。 
 // 这里各人有疑问为什么将x = xpp？ 
 // 这是因为将xpp酿成赤色往后也许与xpp的父节点产生两个相连赤色节点的斗嘴，这就又组成了第二种旋转调动，以是必需从底向上的举办调动，直到根。 
 // 以是令x = xpp，然后举办下下一层轮回，接着往上走。 
 if ((xppr = xpp.right) != null && xppr.red) 
 { 
 xppr.red = false; 
 xp.red = false; 
 xpp.red = true; 
 x = xpp; 
 } 
 // 进入到这个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 
 { 
 if (xppl != null && xppl.red) 
 { 
 xppl.red = false; 
 xp.red = false; 
 xpp.red = true; 
 x = xpp; 
 } else 
 { 
 if (x == xp.left) 
 { 
 root = rotateRight(root, x = xp); 
 xpp = (xp = x.parent) == null ? null : xp.parent; 
 } 
 if (xp != null) 
 { 
 xp.red = false; 
 if (xpp != null) 
 { 
 xpp.red = true; 
 root = rotateLeft(root, xpp); 
 } 
 } 
 } 
 } 
 } 
 } 

假如您的遐想手段很强的话预计到这里应该已司领略这齐集调动的首要的相关。

下面简述一下前面的两各种荣幸的环境

（编辑：湖南网）

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