一简介

平衡二叉查找树简称平衡二叉树，又称之为AVL

以下的树是平衡二叉树：

空树
任意节点的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过1

**平衡因子：**某平衡二叉树结点的左子树的高度减去它的右子树的高度。当一个结点的平衡因子的绝对值大于1时，那么这棵树就失去了平衡。

平衡因子有如下定义：

// 定义平衡因子
// 左高
#define LH +1
// 等高
#define EH 0
// 右高
#define RH -1

对于AVL树有如下定义：

typedef enum Status {
    FALSE = 0, TRUE = 1
} Status;

typedef struct RcdType {
    int key;
} RcdType;

typedef struct BBSTNode {
    RcdType data;
    int bf;
    struct BBSTNode *lchild, *rchild;
} BBSTNode, *BBSTree;

二 AVL的失衡及调整

**最小失衡子树：**在平衡二叉树中插入一个新结点后，从该结点向上寻找第一个不平衡的结点，若找到则以该结点为根的子树称为最小失衡子树。

下面介绍AVL树的几种失衡情况以及其的调整方式

字母右边的数字为平衡因子

2.1 LL型

LL型：指在最小失衡子树的左孩子的左子树上插入了新的结点，对以A为根的最小失衡子树进行顺时针旋转（右旋）。

从下图可以看到，经过右旋后，平衡因子发生的改变：

A的平衡因子由1 -> 2 -> 0
B的平衡因子由0 -> 1 -> 0
其他平衡因子不变，层数不变

左旋代码为：

void R_Rotate(BBSTree *T) {
    BBSTree lc = (*T)->lchild;
    (*T)->lchild = lc->rchild;
    lc->rchild = *T;
    *T = lc;
}

2.2 RR型

RR型：与LL型相反，指在最小失衡子树的右孩子的右子树上插入了新的结点，对以A为根的最小失衡子树进行逆时针旋转（左旋）。

从下图可以看到，经过左旋后，平衡因子发生的改变：

A的平衡因子由**-1** -> -2 -> 0
B的平衡因子由0 -> -1 -> 0
其他平衡因子不变，层数不变

平衡二叉树（旋转操作，插入，删除，合并，分裂，凹入表打印）

void L_Rotate(BBSTree *T) {
    BBSTree rc = (*T)->rchild;
    (*T)->rchild = rc->lchild;
    rc->lchild = *T;
    *T = rc;
}

2.3 LR型

LR型：指的是最小平衡子树的左孩子的右子树上插入了新的结点。处理方法应为找到以A为根的最小失衡树，以该子树的左孩子B为轴，对B的右子树结点C进行左旋调整，使之变成LL型，再以C为轴，对不平衡结点A进行右旋处理。

注：上面字符仅为符号，方便叙述，与下文无关

其中，针对平衡因子的改变，双旋转分为三种情况：

2.3.1 第一种情况

最小平衡子树的左孩子的的平衡因子为LH

从下图可以看到，平衡因子发生的改变：

A的平衡因子由1 -> 2 -> 2 -> -1
B的平衡因子由0 -> -1 -> 0 -> 0
E的平衡因子由0 -> 1 -> 2 -> 0
其他平衡因子结果与插入前不变，层数不变

平衡二叉树（旋转操作，插入，删除，合并，分裂，凹入表打印）

2.3.2 第二种情况

最小平衡子树的左孩子的的平衡因子为EH

从下图可以看到，平衡因子发生的改变：

A的平衡因子由1 -> 2 -> 2 -> 0
B的平衡因子由0 -> -1 -> 0 -> 0
C的平衡因子由0 -> 0
其他平衡因子结果与插入前不变，层数不变

平衡二叉树（旋转操作，插入，删除，合并，分裂，凹入表打印）

2.3.3 第三种情况

最小平衡子树的左孩子的的平衡因子为RH

从下图可以看到，平衡因子发生的改变：

A的平衡因子由1 -> 2 -> 2 -> 0
B的平衡因子由0 -> -1 -> 0 -> 1
C的平衡因子由0 -> -1 -> 1 -> 0
其他平衡因子结果与插入前不变，层数不变

平衡二叉树（旋转操作，插入，删除，合并，分裂，凹入表打印）

2.3.4 左平衡代码

在上面的平衡因子改变中，由第二点即B的初始平衡因子可以判断出该失衡是LL型还是LH型。

若是LH型则由第三点，即B点的右子树可以判断出旋转后A，B的平衡因子

根据以上的LL型以及LR型操作，可以清晰了解下列的左平衡代码：

void LeftBalance(BBSTree *T) {
    BBSTree lc = NULL;
    BBSTree rd = NULL;
    lc = (*T)->lchild;
    switch (lc->bf) {
        case LH: {
            // LL型，直接右旋转T
            (*T)->bf = lc->bf = EH;
            R_Rotate(T);
            break;
        }
        // 删除结点时有该可能性
        case EH: {
            (*T)->bf = LH;
            (*T)->lchild->bf = RH;
            R_Rotate(T);
            break;
        }
        case RH: {
            // LR型，分为三种情况
            rd = lc->rchild;
            switch (rd->bf) {
                case LH: {
                    // 左子树的右子树存在左孩子
                    // 对应情况1
                    (*T)->bf = RH;
                    lc->bf = EH;
                    break;
                }
                case EH: {
                    // 左子树的右子树不存在孩子
                    // 对应情况2
                    (*T)->bf = lc->bf = EH;
                    break;
                }
                case RH: {
                    // 左子树的右子树存在右孩子
                    // 对应情况3
                    (*T)->bf = EH;
                    lc->bf = LH;
                    break;
                }
                default:
                    break;
            }
            // 先左旋后右旋
            rd->bf = EH;
            L_Rotate(&(*T)->lchild);
            R_Rotate(T);
        }
        default: {
            break;
        }
    }
}

2.4 RL型

LR型：指的是最小平衡子树的右孩子的左子树上插入了新的结点。处理方法应为找到以A为根的最小失衡树，以该子树的右孩子结点B为轴，对B的左子树结点C进行右旋调整，使之变成RR型，再以C为轴，对不平衡结点A进行左旋处理。

注：上面字符仅为符号，方便叙述，与下文无关

其中，针对平衡因子的改变，双旋转分为三种情况：

2.3.1 第一种情况

最小平衡子树的右孩子的的平衡因子为LH

从下图可以看到，平衡因子发生的改变：

A的平衡因子由-1 -> -2 -> -2 -> 0
C的平衡因子由0 -> 1 -> -1 -> -1
D的平衡因子由0 -> 1 -> -1 -> 0
其他平衡因子结果与插入前不变，层数不变

平衡二叉树（旋转操作，插入，删除，合并，分裂，凹入表打印）

2.3.2 第二种情况

从下图可以看到，平衡因子发生的改变：

A的平衡因子由**-1** -> -2 -> -2 -> 0
B的平衡因子由0 -> 1 -> 0 -> 0
C的平衡因子由0 -> 0
其他平衡因子结果与插入前不变，层数不变

平衡二叉树（旋转操作，插入，删除，合并，分裂，凹入表打印）

2.3.3 第三种情况

从下图可以看到，平衡因子发生的改变：

A的平衡因子由**-1** -> -2 -> -2 -> 1
C的平衡因子由0 -> 1 -> 0 -> 0
D的平衡因子由0 -> -1 -> -2 -> 0
其他平衡因子结果与插入前不变，层数不变

平衡二叉树（旋转操作，插入，删除，合并，分裂，凹入表打印）

2.4.4 右平衡代码

在上面的平衡因子改变中，由第二点的初始平衡因子可以判断出该失衡是RR型还是RL型。

若是RL型则由第三点，即第二点的右子树可以判断出旋转后A，B的平衡因子

根据以上的RR型以及RL型操作，可以清晰了解下列的右平衡代码：

void RightBalance(BBSTree *T) {
    BBSTree rc = NULL;
    BBSTree rd = NULL;
    rc = (*T)->rchild;
    switch (rc->bf) {
        case RH: {
            // RR型，直接左旋转T
            (*T)->bf = rc->bf = EH;
            L_Rotate(T);
            break;
        }
        case EH: {
            // 删除结点时有该可能性
            (*T)->bf = RH;
            (*T)->rchild->bf = LH;
            L_Rotate(T);
            break;
        }
        case LH: {
            // RL型，分为三种情况
            rd = rc->lchild;
            switch (rd->bf) {
                case LH: {
                    // 右子树的左子树存在左孩子
                    // 对应情况1
                    (*T)->bf = EH;
                    rc->bf = RH;
                    break;
                }
                case EH: {
                    // 右子树的左子树不存在孩子
                    // 对应情况2
                    (*T)->bf = rc->bf = EH;
                    break;
                }
                case RH: {
                    // 右子树的左子树存在右孩子
                    // 对应情况3
                    (*T)->bf = LH;
                    rc->bf = EH;
                    break;
                }
                default:
                    break;
            }
            // 先右旋再左旋
            rd->bf = EH;
            R_Rotate(&(*T)->rchild);
            L_Rotate(T);
            break;
        }
        default:
            break;
    }
}

三插入

若T为空，则直接插入。插入后利用taller指针调整父节点的位置，为TRUE时调整

若某最小失衡树根结点在调整后失衡，则调用左平衡函数或者右平衡函数

若不失衡，则仅仅修改其平衡因子

上面加粗的平衡因子变化就是插入结点时平衡因子的变化

实现代码如下：

Status InsertAVL(BBSTree *T, RcdType e, Status *taller) {
    // T为空，树长高
    if (NULL == (*T)) {
        (*T) = (BBSTree) malloc(sizeof(BBSTNode));
        (*T)->data = e;
        (*T)->bf = EH;
        (*T)->lchild = (*T)->rchild = NULL;
        *taller = TRUE;
    } else if (e.key == (*T)->data.key) {
        // 树中已存在与e相等的节点，不插入
        *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) {
                // 检查T的平衡因子
                case LH: {
                    // 原左高，左平衡处理，高度不变
                    LeftBalance(T);
                    *taller = FALSE;
                    break;
                }
                case EH: {
                    // 原等高，左变高，高度改变
                    (*T)->bf = LH;
                    *taller = TRUE;
                    break;
                }
                case RH: {
                    // 原右高，变等高，高度不变
                    (*T)->bf = EH;
                    *taller = FALSE;
                    break;
                }
                default:
                    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;
                }
                default:
                    break;
            }
        }
    }
    return TRUE;
}

四删除

在删除根结点的操作中，删除根结点左侧的某一元素而导致的左子树高度降低可反向视为右子树的高度升高。

因此，删除结点的操作中可以使用反向插入的平衡调整进行操作。

尽管如此，删除结点跟插入结点还是有些不同

在左平衡处理中，删除结点的左子树的平衡结点可能有等高，而插入则没有该可能性。右平衡亦是
在左平衡处理后，删除结点后若当前子树根结点的左子树平衡因子为EH，则高度降低，否则不变。（可以画出删除的三种可能性找出其中的相同处）

实现代码如下：

/**
 * 删除值e
 * @param T AVL树根节点
 * @param e 要删除的数值
 * @param shorter 高度是否降低
 * @return 删除成功与否
 */
Status DelAVL(BBSTree *T, RcdType e, Status *shorter) {
    if (NULL == (*T)) {
        // 树为空
        return FALSE;
    } else if ((*T)->data.key == e.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;
            p->data = e;
            // 在左子树中删除前驱结点
            return DelLeft(&(*T), e, shorter);
        }
    } else if ((*T)->data.key > e.key) {
        return DelLeft(&(*T), e, shorter);
    } else {
        return DelRight(&(*T), e, shorter);
    }
    return TRUE;
}

Status DelLeft(BBSTree *T, RcdType e, Status *shorter) {
    if (DelAVL(&(*T)->lchild, e, 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)->bf != EH) {
                    *shorter = FALSE;
                }
                break;
            }
            default:
                break;
        }
    }
    return TRUE;
}

Status DelRight(BBSTree *T, RcdType e, Status *shorter) {
    if (DelAVL(&(*T)->rchild, e, shorter) == FALSE) {
        return FALSE;
    }
    if (*shorter == TRUE) {
        switch ((*T)->bf) {
            case LH: {
                // 相当于在左边插入节点，使得左边高度相对增大，平衡后高度不变
                LeftBalance(T);
                if ((*T)->bf != EH) {
                    *shorter = FALSE;
                }
                break;
            }
            case EH: {
                // 原等高，变左高，高度不变
                (*T)->bf = LH;
                *shorter = FALSE;
                break;
            }
            case RH: {
                (*T)->bf = EH;
                *shorter = TRUE;
                break;
            }
            default:
                break;
        }
    }
    return TRUE;
}

五合并与分裂

5.1 算法简介

问题：将两棵平衡二叉树合并为一棵平衡二叉树

最常规的方法自然是，将两个二叉树中的元素一个个插入到新的平衡二叉树中。然而，这样做的时间复杂度很大。但是，如果通过递归来做，则可以在不破坏两棵树的前提下创建一棵新的平衡二叉树，并且时间复杂度比前者要优越很多。

操作步骤：

分别中序遍历两棵二叉树，得到两个有序序列。
将两个有序序列合并为一个有序序列。
利用该有序序列来创建一棵新的平衡二叉树。

递归部分：

终止条件（序列中只剩下一个或两个记录）：
- **一个时：**直接建节点，插入记录，平衡因子为EH
- **两个时：**可建节点，将前者插入，然后后者作为前者的右孩子插入。前者平衡因子为RH，后者平衡因子为EH
递归（当序列数大于二时）：
- 首先建立节点，将序列最中间的记录插入，然后递归，将中间节点之前的记录作为左孩子插入，中间节点后面的记录作为右孩子插入。

该算法一定会构建出平衡二叉树：

每次递归保证了左边的点小于根节点，右边的点大于根节点，因此为排序树。
递归过程中保证了左右孩子的数目相等或相差一个，这样保证了左右孩子的深度绝对值只差不会超过 1

（1）按中序遍历平衡树以获得记录数组：

/**
 * 按中序遍历平衡树以获得记录数组
 * @param T AVL树
 * @param key 数组
 * @param last 数组的最后一个索引
 * @param restore 是否是由其他函数调用
 * @return 是否遍历成功
 */
Status InOrder(BBSTree T, int key[], int *last, int restore) {
    static int i = 0;
    if (!restore)
        // 当每次调用主函数中的函数时，将i恢复为0
        i = FALSE;
    if (!T)
        return TRUE;
    else {
        if (InOrder(T->lchild, key, last, ++restore)) {
            // 得到数组列表
            key[i++] = T->data.key;
            if (InOrder(T->rchild, key, last, ++restore)) {
                // 将数组长度-1
                *last = i - 1;
                return TRUE;
            }
        }
        return FALSE;
    }
}

（2）按从小到大的顺序合并数组：

/**
 * 按从小到大的顺序合并数组
 * @param key 合并后的数组
 * @param key1 数组1
 * @param key2 数组2
 * @param len1 数组1长度
 * @param len2 数组2长度
 * @param last 指向末尾
 */
void MergeArray(int key[], int key1[], int key2[], int len1, int len2, int *last) {
    int i, j, k;
    // 得到第一个小值
    key[0] = (key1[0] < key2[0]) ? key1[0] : key2[0];

    // 按从小到大的顺序合并数组
    for (i = 0, j = 0, k = 1; i <= len1 && j <= len2;) {
        // 防止重复数值
        if (key1[i] < key2[j]) {
            if (key1[i] != key[k - 1])
                key[k++] = key1[i++];
            else
                i++;
        } else {
            // 防止重复数值
            if (key2[j] != key[k - 1])
                key[k++] = key2[j++];
            else
                j++;
        }
    }
    // 合并剩余的key1
    if (i <= len1) {
        while (i <= len1) {
            key[k++] = key1[i++];
        }
    } else if (j <= len2) {
        // 合并剩余的key2
        while (j <= len2) {
            key[k++] = key2[j++];
        }
    } else;
    *last = k - 1;
}

（3）利用有序队列创建一棵新的平衡二叉树：

/**
 * 使用排列好的数组创建AVL
 * @param T 被构造的数
 * @param key 数组
 * @param first 头节点
 * @param last 尾节点
 */
Status Join(BBSTree *T, int key[], int first, int last) {
    if (first == last) {
        // 剩下一个数值时，直接建节点，插入记录。
        *T = (BBSTree) malloc(sizeof(BBSTNode));
        (*T)->data.key = key[first];
        (*T)->lchild = (*T)->rchild = NULL;
        (*T)->bf = EH;
    } else if (first == last - 1) {
        // 剩下两个数值时，建节点，将前者插入，然后再后一个作为前者的右孩子插入。
        *T = (BBSTree) malloc(sizeof(BBSTNode));
        (*T)->data.key = key[first];
        (*T)->rchild = (BBSTree) malloc(sizeof(BBSTNode));
        (*T)->rchild->data.key = key[last];
        (*T)->lchild = (*T)->rchild->lchild = (*T)->rchild->rchild = NULL;
        (*T)->bf = RH;
        (*T)->rchild->bf = EH;
    } else {
        // 建立节点，将序列最中间的记录插入
        int middle = (first + last) / 2;
        *T = (BBSTree) malloc(sizeof(BBSTNode));
        (*T)->data.key = key[middle];
        (*T)->bf = EH;
        // 将中间节点之前的记录作为左孩子插入递归
        if (Join(&((*T)->lchild), key, first, middle - 1))
            (*T)->bf = LH;
        // 将中间节点后面的记录作为右孩子插入递归
        if (Join(&((*T)->rchild), key, middle + 1, last)) {
            if ((*T)->bf == EH) {
                (*T)->bf = RH;
            } else {
                (*T)->bf = EH;
            }
        }
    }
    return TRUE;
}

5.2 合并

/**
 * 合成树
 * @param T 合成的树
 * @param T1 起源树1
 * @param T2 起源树2
 * @return 是否合成成功
 */
Status MergeTree(BBSTree *T, BBSTree T1, BBSTree T2) {
    int key[MMAX], key1[MAX], key2[MAX];
    int len1, len2, last;
    // 得到数组
    InOrder(T1, key1, &len1, 0);
    InOrder(T2, key2, &len2, 0);
    // 合并数组
    MergeArray(key, key1, key2, len1, len2, &last);
    // 创建树
    Join(T, key, 0, last);
    return TRUE;
}

5.3 分裂

/**
 * 把一棵平衡二叉树分裂为两棵平衡二叉树
 * 使得在一棵树中的所有关键字都小于或等于e，另一棵树中的任一关键字都大于e。
 * @param T 初始树
 * @param T1 分裂子树1
 * @param T2 分裂子树2
 * @param e 关键字
 * @return 是否需要分裂
 */
Status Split(BBSTree T, BBSTree *T1, BBSTree *T2, RcdType e) {
    int key[MAX];
    int last, index_x;
    // 得到排列后的数组
    InOrder(T, key, &last, 0);
    // 得到关键字e在数组key中的索引
    int get_x = GetIndexX(key, last, e.key, &index_x);
    if (get_x) {
        // 存在该关键字则调用Join创建AVL
        Join(T1, key, 0, index_x);
        Join(T2, key, index_x + 1, last);
        return TRUE;
    } else {
        // 不存在关键字e则不需要分裂AVL
        *T1 = T;
        *T2 = NULL;
        return FALSE;
    }
}

得到数组中关键字的位置：

/**
 * 得到数组中关键字的位置
 * @param key 数组key
 * @param last 指向数组末尾
 * @param x 关键字
 * @param index_x 关键字的索引
 * @return 是否查找成功
 */
Status GetIndexX(int key[], int last, int x, int *index_x) {
    int i, j;
    for (i = 0; i <= last; i++) {
        j = i + 1;
        if (key[i] <= x && key[j] > x && j <= last) {
            *index_x = i;
            return TRUE;
        }
    }
    return FALSE;
}

六打印

采用凹入表打印输出树：

使用先序遍历输出树结点，并利用level[MAX][2]来存储该结点是上一结点的左结点，右结点还是根结点，以及相对左侧的距离。

/**
 * 凹入法打印树
 * @param T AVL树根节点
 * @return 是否打印成功
 */
Status PrintAVL(BBSTree T) {
    //stack[top]为指针数组
    BBSTree stack[MAX], p;
    int level[MAX][2], top, i, n, width = 4;
    //top为stack栈指针、levle[Max][2]为二维数组，0维度-width(输出空格数)、1维度-不同节点
    char type = 'r';

    if (T != NULL) {
        top = 1;
        //左节点之前输出(0)
        stack[top] = T;
        //根节点入栈
        level[top][0] = width;
        //2代表根节点
        level[top][1] = 2;

        //栈不为空时，循环继续
        while (top > 0)
        {
            //退栈并凹入显示该节点值
            p = stack[top];
            n = level[top][0];

            switch (level[top][1]) {
                case 0:
                    //左节点之前输出(0)
                    type = '0';
                    break;
                case 1:
                    //右节点之前输出(1)
                    type = '1';
                    break;
                case 2:
                    //根节点之前输入(r)
                    type = 'r';
                    break;
                default:
                    break;
            }

            //n为输出的空格数，字符以右对齐显示
            for (i = 1; i <= n; i++)
                printf(" ");
            printf("%d(%c):[%d]", p->data.key, type, p->bf);
            for (i = n + 1; i <= MAX; i += 2)
                printf("-");
            printf("\n");
            //根节点出栈
            top--;

            if (p->rchild != NULL) {
                stack[++top] = p->rchild;          //将右子树根节点入栈
                level[top][0] = n + width;        //输出空格数增加width
                level[top][1] = 1;              //1表示是右子树
            }
            if (p->lchild != NULL) {
                stack[++top] = p->lchild;          //将左子树根节点入栈
                level[top][0] = n + width;        //输出空格数增加width
                level[top][1] = 0;              //0代表左子树
            }
        }
    }
    return TRUE;
}

平衡二叉树（旋转操作，插入，删除，合并，分裂，凹入表打印）

一 简介

二 AVL的失衡及调整

2.1 LL型

2.2 RR型

2.3 LR型

2.3.1 第一种情况

2.3.2 第二种情况

2.3.3 第三种情况

2.3.4 左平衡代码

2.4 RL型

2.3.1 第一种情况

2.3.2 第二种情况

2.3.3 第三种情况

2.4.4 右平衡代码

三 插入

四 删除

五 合并与分裂

5.1 算法简介

5.2 合并

5.3 分裂

六 打印

相关推荐

一简介

三插入

四删除

五合并与分裂

六打印