- //hashmap的红黑树平衡
- static TreeNode balanceInsertion(TreeNode root,
- TreeNode x) {
- x.red =true;
- //死循环加变量定义,总感觉JAVA很少这样写代码 哈
- for(TreeNode xp, xpp, xppl, xppr;;) {
- //xp X父节点, XPP X的祖父节点, XPPL 祖父左节点 XXPR 祖父右节点
- if((xp = x.parent) ==null) {
- x.red =false;
- return x;
- }
- // 如果父节点是黑色, 或者XP父节点是空,直接返回
- else if(!xp.red || (xpp = xp.parent) ==null)
- return root;
- // 下面的代码就和上面的很treeMap像了,
- if(xp == (xppl = xpp.left)) {
- // 第一种情况, 赋值xppl
- //父节点是左节点的情况,下面这种
- /**
- * G
- * P(RED) U
- */
- if((xppr = xpp.right) !=null&& xppr.red) {
- //如果红叔的情况
- // 这种情况
- /**
- * G
- * P(RED) U(RED)
- * X
- */
- //改变其颜色,xppr.red =false;
- xp.red =false;
- xpp.red =true;
- x = xpp;
- }
- else {
- // 黑叔的情况
- // 这种情况
- /**
- * G
- * P(RED) U(BLACK)
- */
- if(x == xp.right) {
- //如果插入节点在右边 这种
- // 这种情况
- /**
- * G
- * P(RED) U(BLACK)
- * X
- */
- //需要进行左旋root = rotateLeft(root, x = xp);
- xpp = (xp = x.parent) ==nullnull : xp.parent;
- }
- //左旋后情况都是这种了
- /**
- * G
- * P(RED) U(BLACK)
- * X
- */
- // 到这,X只能是左节点了,而且P是红色,U是黑色的情况
- if(xp !=null) {
- //把P和G改成黑色,以G为节点进行右旋xp.red =false;
- if(xpp !=null) {
- xpp.red =true;
- root = rotateRight(root, xpp);
- }
- }
- }
- }
- else {
- //父节点在右边的
- /**
- * G
- * U P(RED)
- */
- //获取U
- if(xppl !=null&& xppl.red) {
- //红父红叔的情况
- /**
- * G
- * U(RED) P(RED)
- */
- xppl.red =false;
- xp.red =false;
- xpp.red =true;
- x = xpp;
- }
- else {
- if(x == xp.left) {
- //如果插入的X是右节点
- /**
- * G
- * U(BLACK) P(RED)
- * X
- */
- root = rotateRight(root, x = xp);
- xpp = (xp = x.parent) ==nullnull : xp.parent;
- }
- //右旋后
- /**
- * G
- * U(BLACK) P(RED)
- * X
- */
- if(xp !=null) {
- xp.red =false;
- if(xpp !=null) {
- xpp.red =true;
- root = rotateLeft(root, xpp);
- }
- }
- }
- }
- }
来源: http://www.bubuko.com/infodetail-1949271.html