//右平衡,右边高了 static void RightBalance(ref Node node) { Node R, r1; R = node.cRight; switch (R.bf) { case RH: //右孩子和它一样的平衡因子,直接右旋转 node.bf = EH; R.bf = EH; L_Rotate(ref node); break; case EH: node.bf = RH; R.bf = LH; L_Rotate(ref node); break; case LH: r1 = R.cLeft; switch (r1.bf) { case EH: node.bf = EH; R.bf = EH; break; case RH: R.bf = EH; node.bf = LH; break; case LH: R.bf = RH; node.bf = EH; break; } r1.bf = EH; R_Rotate(ref node.cRight); L_Rotate(ref node); break; } }
看情况,旋转之后的bf状态值会有所改变,所以要具体分析到每一种情况之下。
LH的情况比较多样这里就不详细分析了,不过要讲它为啥要先左旋其右结点再右旋自己。看图:
这种情况就是右平衡的时候,其子树的bf方向是不一致的,需要反向调整到一致,不然就不是一个排序树了。