平衡二叉树的右平衡方法
//右平衡,右边高了
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;
    }
}


blob.png

看情况,旋转之后的bf状态值会有所改变,所以要具体分析到每一种情况之下。

LH的情况比较多样这里就不详细分析了,不过要讲它为啥要先左旋其右结点再右旋自己。看图:

blob.png

这种情况就是右平衡的时候,其子树的bf方向是不一致的,需要反向调整到一致,不然就不是一个排序树了。


首页 我的博客
粤ICP备17103704号