//右平衡,右边高了
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方向是不一致的,需要反向调整到一致,不然就不是一个排序树了。