数据结构与算法-平衡二叉树

平衡二叉树（Balanced Binary Tree 或 Height-Balanced Tree）又称AVL树。它或者是一颗空树，或者具有下列性质的二叉树：

• 它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。
• 若将二叉树上结点的平衡因子BF(Balance Factor)定义为该结点的左子树的深度减去它的右子树深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0、1。

一般情况下，假设由于在二叉排序树上插入结点而失去平衡的最小子树跟结点的指针为a，则失去平衡后进行调整的规律可归纳为下列4种情况：

• 单向右旋平衡处理；
• 单向左旋平衡处理；
• 双向旋转（先左后右）平衡处理；
• 双向旋转（先右后左）平衡处理；

代码实现

typedef int Status;

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

typedef struct BSTNode{
    int data;
    int bf;
    struct BSTNode *lchild,*rchild;
    
}BSTNode, *BSTree;

void R_Rotate(BSTree *p) {
    BSTree lc;
    lc = (*p)->lchild;
    (*p)->lchild = lc->rchild;
    lc->rchild = *p;
    *p = lc;
}

void L_Rotate(BSTree *p) {
    BSTree rc;
    rc = (*p)->rchild;
    (*p)->rchild = rc->lchild;
    rc->lchild = *p;
    *p = rc;
}

void LeftBalance(BSTree *T) {
    BSTree lc, rd;
    lc = (*T)->lchild;
    switch (lc->bf) {
        case LH:
            (*T)->bf = lc->bf = EH;
            R_Rotate(T);
            break;
        case RH:
            rd = lc->rchild;
            switch (rd->bf) {
                case LH:
                    (*T)->bf = RH;
                    lc->bf = EH;
                    break;
                case EH:
                    (*T)->bf = lc->bf = EH;
                    break;
                case RH:
                    (*T)->bf = EH;
                    lc->bf = LH;
                    break;
            }
            rd->bf = EH;
            L_Rotate(&(*T)->lchild);
            R_Rotate(T);
            break;;
    }
}

void RightBalance(BSTree *T) {
    BSTree rc, ld;
    rc = (*T)->rchild;
    switch (rc->bf) {
        case RH:
            (*T)->bf = rc->bf = EH;
            L_Rotate(T);
            break;
        case LH:
            ld = rc->lchild;
            switch (ld->bf) {
                case RH:
                    (*T)->bf = LH;
                    rc->bf = EH;
                    break;
                case EH:
                    (*T)->bf = rc->bf = EH;
                    break;
                case LH:
                    (*T)->bf = EH;
                    rc->bf = RH;
                    break;
            }
            ld->bf = EH;
            R_Rotate(&(*T)->rchild);
            L_Rotate(T);
            break;;
    }
}

Status InsertAVL(BSTree *T, int e, Status *taller) {
    if (!*T) {
        *T = (BSTree)malloc(sizeof(BSTNode));
        (*T)->data = e;
        (*T)->lchild = (*T)->rchild = NULL;
        (*T)->bf = EH;
        *taller = TRUE;
    } else {
        if (e == (*T)->data) {
            *taller = FALSE;
            return FALSE;
        }
        
        if (e < (*T)->data) {
            if (!InsertAVL(&(*T)->lchild, e, taller)) {
                return FALSE;
            } else {
                if (*taller) {
                    switch ((*T)->bf) {
                        case LH:
                            LeftBalance(T);
                            *taller = FALSE;
                            break;
                        case EH:
                            (*T)->bf = LH;
                            *taller = TRUE;
                            break;
                        case RH:
                            (*T)->bf = EH;
                            *taller = FALSE;
                            break;
                    }
                }
            }
        } else {
            if (!InsertAVL(&(*T)->rchild, e, taller)) {
                return FALSE;
            } else {
                if (*taller) {
                    switch ((*T)->bf) {
                        case RH:
                            RightBalance(T);
                            *taller = FALSE;
                            break;
                        case EH:
                            (*T)->bf = RH;
                            *taller = TRUE;
                            break;
                        case LH:
                            (*T)->bf = EH;
                            *taller = FALSE;
                            break;
                    }
                }
            }
        }
    }
    return TRUE;
}

Status SearchBST(BSTree T, int key, BSTree f, BSTree *p){
    if (!T) {
        *p = f;
        return FALSE;
    } else if (key == T->data) {
        *p = T;
        return TRUE;
    } else if (key < T->data) {
        return SearchBST(T->lchild, key, T, p);
    } else {
        return SearchBST(T->rchild, key, T, p);
    }
}