平衡二叉树（AVL）

基本概念

  • 概念

    由于二叉搜索树在某些极端情况下会退化成单链表的，所以需要特殊手段把它维持二叉搜索树的“平衡”。处理失衡的操作有：左旋、右旋

  • 性质

    • 也是一个BST树，满足BST树的性质
    • 左右子树的高度差的绝对值不超过1
    • 左右子树分别也是AVL树

    注：平衡因子 = 左子树的高度 - 右子树的高度（取值只能是 -1、0、1）

  • 最小不平衡子树

    在插入操作后，可能会有多个结点的平衡因子绝对值大于1

    我们只需要找到插入元素最近的不平衡结点，以它为根的树，就是最小不平衡子树

    image-20260315185618559

    • 理解：

      整棵树原本是AVL树，来了一个结点导致失衡，那么失衡结点的平衡因子只能是2或-2

      把最小平衡子树调整平衡后，那么这颗子树的高度就会-1，向上传递的过程中，会让整个路径里的平衡因子向0靠近一位，就平衡了

  • AVL树插入后的失衡与调整

    • LL型失衡

      • 情形：新节点插在最小不平衡子树根的左孩子的左子树上（插入5）

        image-20260315191152110

      • 处理：对最小不平衡子树右旋一次

        右旋：以失衡根的左孩子为轴，失衡根顺时针旋转；轴的右子树，挂到失衡根的左子树位置，最终左孩子成为新根

        image-20260315191624769

    • RR型失衡

      • 情形：新节点插在 最小不平衡子树根的右孩子的右子树 上（插入11）

        image-20260315185835064

      • 处理：对最小不平衡子树 左旋一次

        左旋：以失衡根的右孩子为轴，失衡根逆时针旋转；轴的左子树，挂到失衡根的右子树位置，最终右孩子成为新根

        image-20260315185846310

    • LR型失衡

      • 情形：左孩子右子树插入（插入7）

        image-20260315192533973

      • 处理：左旋左孩子（L），然后右旋根结点（T）（左右双旋）

        1. 左旋左孩子（L），将其转为 LL 型

          左旋：以失衡根的右孩子为轴，失衡根逆时针旋转；轴的左子树，挂到失衡根的右子树位置，最终右孩子成为新根

          image-20260315192619835

        2. 右旋根结点（T）

          image-20260315192734352

    • RL型失衡

      • 情形：右孩子左子树插入（插入9）

        image-20260315192838564

      • 处理：右旋右孩子（R），然后左旋根结点（T）（右左双旋）

        1. 右旋右孩子（R），将其转为 RR 型

          右旋：以失衡根的左孩子为轴，失衡根顺时针旋转；轴的右子树，挂到失衡根的左子树位置，最终左孩子成为新根

          image-20260315192939148

        2. 左旋根结点（T）

          image-20260315192942309

  • AVL树的删除操作

    1. 先用二叉搜索树的方法删除结点e

    2. 从结点e开始，向上找到第一个不平衡结点T（最小不平衡子树）

    3. 再找到T结点为根的子树中最高的 儿结点、孙结点

    4. 根据孙结点与T的位置，分4种情况调整（LL、RR、LR、RL）

    5. 调整后，继续向上查找，重复2-4的操作

    实例（删除权值为6的结点）

    image-20260315205555699

    1. 找到第一个不平衡子树（T权值为8），根据最高儿孙结点位置，判断为RL型

      image-20260315205711352

    2. 调整后，向上找到不平衡子树（T权值为12），根据最高儿孙结点位置，判断为RR型

      注：右旋后，右孩子的左子树要挂在T的右子树上

      image-20260315205732578

    3. 调整完毕

      image-20260315205948796

« 二叉搜索树（BST） ← 返回列表 红黑树（RBT） »