平衡二叉树之C语言实现（插入、删除，分裂、合并）附源代码

时间：2021-10-02 10:10:35

平衡二叉树的定义

平衡二叉查找树( Balanced Binary Sort Tree,BBST)简称平衡二叉树。平衡二又树有很多种,其中最著名的是由前苏联数学家 Adele- Veliki和 Landis在1962年提出的高度平衡的二叉树。根据提出者的英文名字首字母简称为AVL树 。

平衡二叉树或者是棵空树,或者是具有下列性质的二叉查找树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过1。若将二叉树结点的平衡因子( Balance Factor)定义为该结点的左子树的高度减去它的右子树的高度,则所有结点的平衡因子只可能为-1、0、1。只要有一个结点的平衡因子的绝对值大于1，那么这棵树就失去了平衡。

平衡二叉树的存储结构及宏定义

#define LH +1 // 左子树比右子树高
#define EH 0 // 左、右子树等高
#define RH -1 // 右子树比左子树高

typedef int KeyType;    // 关键字类型为整数类型

typedef struct {
    KeyType key;   // 关键字项
} RecordType, RcdType;    // 记录类型

typedef struct BBSTNode {
    RcdType data;
    int bf;         // 结点平衡因子
    struct BBSTNode *lchild, *rchild;  // 左右孩子
} * BBSTree;  // 平衡二叉树

平衡二叉树的失衡及调整

最小失衡子树

在平衡二叉树中插入一个新结点后，从该结点起向上寻找第一个不平衡的结点(平衡因子bf变为了-2或2)，以确定该树是否失衡。若找到，则以该结点为根的子树称为最小失衡子树。

平衡二叉树失衡后则需要调整，需要对失衡的情况进行分类，分为以下四种。

(1). LL型

LL型指的是在最小失衡子树的左孩子的左子树上插入了新的结点。失衡调整如下图所示，先找到最小失衡子树的根A，以其左孩子结点B为轴，对不平衡结点A进行顺时针旋转(也称为右旋)。右旋是让B顶替A的位置，并置A为B的右孩子，如果B存在右子树 B R ，则置 B R 为A的左子树。

平衡二叉树之C语言实现（插入、删除，分裂、合并）附源代码

代码实现

/** * 对最小失衡子树p作右旋调整 * * @param p 最小失衡子树 */
void R_Rotate(BBSTree &p) {
    BBSTree lc = p->lchild; // lc指向p结点的左孩子
    p->lchild = lc->rchild; // lc结点的右子树置为p结点的左子树
    lc->rchild = p; // 置p结点为lc结点的右孩子
    p = lc; // p指向新的根结点
}

(2). RR型

对于RR型。正好与LL型对称，对以A为根的最小失衡子树进行逆时针旋转（左旋），如下图所示。

平衡二叉树之C语言实现（插入、删除，分裂、合并）附源代码

实现代码

/** * 对最小失衡子树p作左旋调整 * * @param p 最小失衡子树 */
void L_Rotate(BBSTree &p) {
    BBSTree rc = p->rchild;
    p->rchild = rc->lchild;
    rc->lchild = p;
    p = rc;
}

(3). LR型

LR型指的是最小失衡子树的左孩子的右子树上插入了新的结点。处理办法如下图所示，首先找到以A为根的小失衡子树，以该子树的左孩子结点B为轴,对右子树结点C进行左旋调整，使之变为LL型。再以C为轴，对不平衡结点A进行右旋调整。

平衡二叉树之C语言实现（插入、删除，分裂、合并）附源代码

(4). RL型

RL型与LR型对称，需依次进行右旋处理和左旋处理，如下图所示

平衡二叉树之C语言实现（插入、删除，分裂、合并）附源代码

平衡二叉树的插入

构造平衙二又树可采用依次插人结点的方式，其递归步骤如下：

  1. 若是空树，则插人结点作为根结点,树的高度增加1。
  2. 若待插入结点和根结点相等，则无须插入。
  3. 若待插人结点小于根结点，且在左子树中也不存在相等的结点，则在左子树插入，且若插入后的左子树高度增加1，分情况处理。
    • 原根结点的平衡因子为-1(右子树高于左子树)，更改为0，树的高度不变。
    • 原根结点的平衡因子为0(左右子树高度相等)，更改为1，树的高度增加1。
    • 原根结点的平衡因子为1(左子树高于右子树)：若左子树根结点的平衡因子为1，则属于LL型,需进行右旋平衡调整，并在调整后将根结点及其右孩子的平衡因子更改为0，树的高度不变；若左子树根结点的平衡因子为-1，则属于LR型，需依次进行左旋和右旋处理，并在调整后修改根结点及其左、右孩子的平衡因子，树的高度不变。
  4. 若待插入结点大于根结点，且在右子树中不存在相等的结点，则在右子树插入，且当插入之后的右子树高度加1时，分情况处理
    • 原根结点的平衡因子为1(左子树高于右子树)，更改为0，树的高度不变。
    • 原根结点的平衡因子为0(左右子树高度相等)，更改为-1，树的高度加1。
    • 原根结点的平衡因子为-1(右子树高于左子树)：若右子树根结点的平衡因子为1，则属于RL型，需依次进行右旋和左旋处理,并且在旋转处理之后，修改根结点及其左、右子树根结点的平衡因子，树的高度不变；若右子树根结点的平衡因子为-1，则属于RR型，需要进行一次左旋处理，并且在左旋之后，更新根结点和其左、右子树根结点的平衡因子，树的高度不变。

左平衡处理操作

/** * 树T的左平衡处理 * * @param T 树T */
void LeftBalance(BBSTree &T) {
    BBSTree 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;
        }
    }
}

右平衡处理操作

/** * 树T的右平衡处理 * * @param T 树T */
void RightBalance(BBSTree &T) {
    BBSTree 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;
    }
}

插入代码实现

/** * 平衡二叉树的插入操作 * * @param T 平衡二叉树T * @param e 待插入元素 * @param taller 高度是否变高 * @return 成功返回TRUE */
Status InsertAVL(BBSTree &T, RcdType e, Status &taller) {
    if (NULL == T) {
        // T为空，树长高
        T = (BBSTree)malloc(sizeof(BBSTNode));
        T->data = e;
        T->bf = EH;
        T->lchild = NULL;
        T->rchild = NULL;
        taller = TRUE;
    } else if (e.key == T->data.key) {
        // 已经存在该点
        taller = FALSE;
        return FALSE;
    } else if (e.key < T->data.key) {
        // 插入到左子树
        if (FALSE == InsertAVL(T->lchild, e, taller)) {
            return FALSE;
        }
        if (TRUE == 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 (FALSE == InsertAVL(T->rchild, e, taller)) {
            return FALSE;
        }
        if (TRUE == 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;
}

平衡二叉树的删除

平衡二叉树的删除可以看做插入的反过程，所以调整的方向也是相反的，所以操作起来并不难。

其中的查找前驱结点的依据是平衡二叉树的中序遍历是有序序列。且被删结点的直接前驱位于其左子树的右下角。用前驱结点的值代替被删结点的值，然后删除前驱结点，这样就跟简单的操作一样了。

代码实现

/** * 平衡二叉树的删除操作 * * @param T * @param key * @param shorter * @return */
Status DeleteAVL(BBSTree &T, KeyType key, Status &shorter) {
    if (NULL == T) {
        // 树为空
        return FALSE;
    } else if (T->data.key == key) {
        // 找到元素结点
        BBSTree p = NULL;
        if (NULL == T->lchild) {
            // 左子树为空
            p = T;
            T = T->rchild;
            free(p);
            shorter = TRUE; // 高度变矮
        } else if (T->rchild == NULL) {
            // 右子树为空
            p = T;
            T = T->lchild;
            free(p);
            shorter = TRUE; // 高度变矮
        } else {
            // 左右子树都存在
            p = T->lchild;
            while (p->rchild != NULL) {
                p = p->rchild;
            }
            T->data = p->data;
            // 在左子树中删除前驱结点
            DeleteAVL(T->lchild, p->data.key, shorter);
        }
    } else if (T->data.key > key) {
        if (DeleteAVL(T->lchild, key, shorter) == FALSE) {
            return FALSE;
        }
        if (shorter == TRUE) {
            switch (T->bf) {
                case LH: {
                    T->bf = EH;
                    shorter = TRUE;
                    break;
                } case EH: {
                    T->bf = RH;
                    shorter = FALSE;
                    break;
                } case RH: {
                    RightBalance(T);
                    if (T->rchild->bf == EH) {
                        shorter = FALSE;
                    } else {
                        shorter = TRUE;
                    }
                    break;
                }
            }
        }
    } else {
        if (DeleteAVL(T->rchild, key, shorter) == FALSE) {
            return FALSE;
        }
        if (shorter == TRUE) {
            switch (T->bf) {
                case LH: {
                    LeftBalance(T);
                    if (T->lchild->bf == EH) {
                        shorter = FALSE;
                    } else {
                        shorter = TRUE;
                    }
                    break;
                } case EH: {
                    T->bf = LH;
                    shorter = FALSE;
                    break;
                } case RH: {
                    T->bf = EH;
                    shorter = TRUE;
                    break;
                }
            }
        }
    }
    return TRUE;
}

平衡二叉树的分裂和合并

平衡二叉树的分裂和合并是根据插入操作来实现的，具体请看以下代码。

/** * 分裂平衡二叉树，分成大于key和小于key两棵树 * * @param T 待分裂的平衡二叉树 * @param key 分裂的关键字 * @param T1 关键字全部小于key的平衡二叉树 * @param T2 关键字全部大于key的平衡二叉树 */
void SpiltBBST(BBSTree T, KeyType key, BBSTree &T1, BBSTree &T2) {
    Status taller = FALSE;
    if (T != NULL) {
        SpiltBBST(T->lchild, key, T1, T2); // 递归访问左子树
        if(T->data.key > key) {
            InsertAVL(T1, T->data, taller);
        } else {
            InsertAVL(T2, T->data, taller);
        }
        SpiltBBST(T->rchild, key, T1, T2);
    }
}

/** * 合并平衡二叉树 * * @param T1 合并后的平衡二叉树 * @param T2 待合并的平衡二叉树 */
void MergeBBST(BBSTree &T1, BBSTree T2) {
    Status taller = FALSE;
    if (T2 != NULL) {
        MergeBBST(T1, T2->lchild);
        InsertAVL(T1, T2->data, taller);
        MergeBBST(T1, T2->rchild);
    }
}

如需获取完整的代码以及测试函数，请到https://github.com/zhengjunming/ds/tree/master/avl-tree 中clone。

标签：

相关文章