Skip to content

二叉树平衡.md

Latest commit

 

History

History
executable file
·
121 lines (111 loc) · 4.28 KB

二叉树平衡.md

File metadata and controls

executable file
·
121 lines (111 loc) · 4.28 KB

平衡因子 BF

二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF（balance factor）。

平衡二叉树上所有结点的BF只可能是-1、0、+1.

最小不平衡子树

构建平衡二叉树

关键看BF。BF为负且小于-11即等于-2时，左旋；BF为正且大于1即等于2时，右旋。旋转后需要满足二叉排序树的特性，因此有些结点相对位置也会变。直接旋转的前提是最小不平衡子树的根节点与它的子节点的BF符号相同。 若不能直接旋转，则先统一BF符号。

实现构建平衡二叉树时，首先要改进二叉排序树的结点结构，增加bf域。

void R_Rotate(BiTree *P){
    BiTree L;
    L = (*P)->lchild;
    (*P)->lchild = L->rchild;   //L的右孩子大于L且小于P（P是L的父亲）
    L->rchild = (*P);
    *P = L;
}
//左旋类似

#define LH 1    //左高
#define EH 0    //等高
#define RH -1   //右高

/* 对以指针T所指结点为根的二叉树作左平衡旋转处理
算法结束时指针T指向新的根结点 */
void LeftBalance(BiTree *T){
    //调用本函数时已经确认当前子树是不平衡状态，且左子树的高度大于右子树的高度。即此时T的根节点应该是BF大于1的数。

    BiTre L,Lr;
    L = (*T)->lchild;
    switch(L->bf){
        //检查T的左子树的平衡度
        case LH:    //新插入的结点插入在T的左孩子的左子树上，要做单右旋处理
            // 表明与根节点的BF同号，因此都改成0.
            (*T)->bf = L->bf = EH;
            R_Rotate(T);
            break;
        case RH:    //新结点插入在T的左孩子的右子树上，要做双旋处理
            // 表明与根节点的BF异号。
            Lr = L->rchild; //对根节点的不平衡的左孩子的不平衡的右孩子进行平衡处理
            switch(Lr->bf){
                case LH:   
                    (*T)->bf = RH;
                    L->bf = EH;
                    break;
                case EH:
                    (*T)->bf = L->bf = EH;
                    break;
                case RH:
                    (*T)->bf = EH;
                    L->bf = LH;
                    break;
            }
            Lr->bf = EH;
            L_Rotate(&(*T)->lchild);    //对T的左子树做左旋平衡处理
            R_Rotate(T);    //对T做右旋平衡处理
    }
}
  • LH:
  • RH:

右平衡旋转处理函数类似。

主函数：

/* 若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个数据元素为e的新结点并返回1，否则返回0.
若因插入而使二叉排序树失去平衡，则做平衡旋转处理，布尔变量taller反映T长高与否。 */
Status InsertAVL(BiTree *T, int e, Status *taller){
    if(! *T){//当前T为空时，申请内存新增一个结点
        //插入，树长高
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = e;
        (*T)->lchild = (*T)->rchild = NULL;
        (*T)->bf = EH;
        *taller = TRUE;
    }
    else{
        if(e == (*T)->data){
            //树中已经存在和e有相同关键字的结点则不再插入
            *taller = FALSE;
            return FALSE;
        }
        if(e < (*T)->data){
            //应继续在T的左子树中搜索
            if(!InsertAVL(&(*T)->lchild,e,taller)){
                return FALSE;
            }
            if(taller){
                //已插入到T的左子树中且左子树长高
                switch((*T)->bf){
                    //检查T的平衡度
                    case LH:
                        LeftBalance(T);
                        *taller = FALSE;
                        break;
                    case EH:
                        //没有失衡
                        (*T)->bf = LH;
                        *taller = TRUE:
                        break;
                }
            }
        }
        else{
            //在右子树中继续搜索
            //类似左子树。
        }
    }
    return TRUE;
}

Reference