美文网首页
数据结构与算法-AVL树

数据结构与算法-AVL树

作者: 收纳箱 | 来源:发表于2020-05-17 15:39 被阅读0次

    1. 基础数据结构

    #define LH +1 /*  左高 */
    #define EH 0  /*  等高 */
    #define RH -1 /*  右高 */
    
    /// 平衡二叉树
    typedef struct BiTNode {
        int data; // 数据
        int bf; // 平衡因子
        struct BiTNode *lchild, *rchild; // 左右孩子指针
    } BiTNode, *BiTree;
    

    2. 左旋右旋

    这里以右旋为例,P断开了左指针,L断开右指针;L空出来的右指针指向P,P空出来的左指针指向L_R

    右旋
    /// 左旋
    void R_Rotate(BiTree *p) {
        BiTree L = (*p)->lchild; // L是p的左子树
        (*p)->lchild = L->rchild; // L的右子树作为p的左子树
        L->rchild = *p; // 将p作为L的右子树
        *p = L; // 将L替换原有p的根结点位置
    }
    
    /// 右旋
    void L_Rotate(BiTree *p) {
        BiTree R = (*p)->rchild; // R是p的右子树
        (*p)->rchild = R->lchild; // R的左子树作为R的右子树
        R->lchild = *p; // 将p作为R的左子树
        *p = R; // 将R替换原有p的根结点位置
    }
    

    3. 左失衡右失衡

    /// 左失衡
    void LeftBalance(BiTree *T) {
        BiTree Tl = (*T)->lchild;
        BiTree Lr;
        switch (Tl->bf) {
            case LH: // 新结点插入在T的左孩子的左子树上
                (*T)->bf = Tl->bf = EH; // 调整后平衡
                R_Rotate(T); // 进行右旋
                break;
            case RH: // 新结点插入在T的左孩子的右子树上
                Lr = Tl->rchild; // Lr指向T的左孩子的右子树
                // 修改T及其左孩子的平衡因子
                switch (Lr->bf) {
                    case LH:
                        Tl->bf = RH;
                        (*T)->bf = EH;
                        break;
                     case EH:
                        Tl->bf = (*T)->bf = EH;
                        break;
                    case RH:
                        Tl->bf = EH;
                        (*T)->bf = LH;
                        break;
                }
                Lr->bf = EH;
                L_Rotate(&(*T)->lchild); // 对T的左子树作左旋平衡处理
                R_Rotate(T); // 对T作右旋平衡处理
                break;
        }
    }
    
    /// 右失衡
    void RightBalance(BiTree *T) {
        BiTree Tr = (*T)->rchild;
        BiTree Rl;
        switch (Tr->bf) {
            case RH: // 新结点插入在T的右孩子的右子树上
                (*T)->bf = Tr->bf = EH; // 调整后平衡
                L_Rotate(T); // 进行左旋
                break;
            case LH: // 新结点插入在T的右孩子的左子树上
                Rl = Tr->lchild; // Ll指向T的右孩子的左子树
                // 修改T及其左孩子的平衡因子
                switch (Rl->bf) {
                    case LH:
                        Tr->bf = EH;
                        (*T)->bf = RH;
                        break;
                     case EH:
                        Tr->bf = (*T)->bf = EH;
                        break;
                    case RH:
                        Tr->bf = LH;
                        (*T)->bf = EH;
                        break;
                }
                Rl->bf = EH;
                R_Rotate(&(*T)->rchild); // 对T的右子树作右旋平衡处理
                L_Rotate(T); // 对T作左旋平衡处理
                break;
        }
    }
    

    4. 插入结点

    /// 插入结点
    /// @param T AVL树
    /// @param data 被插入数据
    /// @param taller 是否"长高"
    Status InsertAVL(BiTree *T, int data, Status *taller) {
        if (!*T) { // 空结点
            *T = (BiTree)malloc(sizeof(BiTNode));
            (*T)->data = data;
            (*T)->lchild = (*T)->rchild = NULL; // 新结点没有左右子树
            (*T)->bf = EH;
            *taller = TRUE; // 新结点默认"长高"
        } else {
            if (data == (*T)->data) { // 已存在和data有相同关键字的结点则不再插入
                *taller = FALSE;
                return FALSE;
            }
            if (data < (*T)->data) { // 小则在左子树插入
                if (!InsertAVL(&(*T)->lchild, data, taller)) // 插入失败
                    return FALSE;
                // 插入成功
                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, data, taller)) // 插入失败
                    return FALSE;
                // 插入成功
                if (*taller) {
                    switch ((*T)->bf) {
                        case LH:
                            // 原本左子树比右子树高,现左右子树等高
                            (*T)->bf = EH;
                            *taller = FALSE;
                            break;
                        case EH:
                            // 原本左、右子树等高,现因右子树增高而使树增高
                            (*T)->bf = RH;
                            *taller = TRUE;
                            break;
                        case RH:
                            // 原本右子树比左子树高,需要作右平衡处理
                            RightBalance(T);
                            *taller = FALSE;
                            break;
                    }
                }
            }
        }
        return TRUE;
    }
    

    5. 查询

    查询和二叉搜索树相同。

    /// 递归查找二叉排序树T中,是否存在key
    /// @param T AVL树
    /// @param key 被查询值
    /// @param f 指针f指向T的双亲,初始值为NULL
    /// @param p 最后一个被访问结点的指针引用
    ///
    /// 若指针p指向查找路径上访问的最后一个结点则返回FALSE
    Status SearchBST(BiTree T, int key, BiTree f, BiTree *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);
        }
        return TRUE;
    }
    

    相关文章

      网友评论

          本文标题:数据结构与算法-AVL树

          本文链接:https://www.haomeiwen.com/subject/tjrsohtx.html