AVL树¶

约 3392 个字 161 行代码 39 张图片预计阅读时间 13 分钟

AVL树介绍¶

二叉搜索树在某些极端情况下可能会退化，为了解决这个问题，引入了AVL树（平衡搜索二叉树中的一种）控制二叉搜索树的不平衡情况，插入一个新节点后，控制每一个节点的左右子树高度差的绝对值不超过1

Note

之所以控制绝对值不超过1而不是不超过0是因为只有在满二叉树的情况下才可以满足每一个节点的左右子树高度差的绝对值不超过0，为了满足普遍性，选择绝对值不超过1

一棵AVL树具有以下的特点：

每一个节点的左右子树都是AVL树
左右子树高度差的绝对值（通过平衡因子判断）不超过1

Note

绝对值不超过1，包括-1、1和0

以右子树高度减左子树高度为例，下面是含有每一个节点的高度的AVL树示意图：

AVL树平衡因子更新分析¶

在AVL树中，平衡因子更新只有两种情况：1. 增加 2. 减少，但是需要考虑什么时候增加什么时候减少

当插入节点在左子树时，平衡因子减少，例如插入在8节点的左子树
当插入节点在右子树时，平衡因子增加，例如插入在8的右子树

接着考虑插入新节点后，哪些节点的平衡因子需要改变。

如果插入节点在8的左子树，那么更新时只会更新8节点的平衡因子，因为8初始时是1，插入在左子树平衡因子减小，而对于节点7来说，并没有影响到其平衡因子，因为7的右子树总体的高度没有发生变化，而对于根节点的左子树以及7节点的左子树来说没有一点影响
如果按照下图的插入方式，插入节点为红色节点，此时会更新其所有祖先节点
如果插入节点在8的右子树，那么更新时8节点的平衡因子变为了2，因为8初始时是1，插入在右子树平衡因子增加，因为AVL树规定每一个节点的左右子树高度差的绝对值不能超过1，所以此时8节点需要进行额外处理使其恢复AVL树结构

综上所述，存在三种情况：

当插入节点的父亲节点更新为0时：插入节点前父亲节点平衡因子为1或者-1（一边高一边矮），为1时，右子树高，插入位置为左子树；为-1时，左子树高，插入位置为右子树（插入在矮的一边），此时只需要更新父亲节点的平衡因子，因为总高度并没有发生变化。例如8节点的左子树插入节点，树的总高度还是4
当插入节点的父亲节点更新为1或者-1时：插入节点前父亲节点平衡因子为0（左右子树高度相等），当更新为1时，插入位置为右子树，右子树变高，起始为-1时，插入位置为左子树，左子树变高（其中一方变高），此时需要更新所有祖先节点的平衡因子，因为插入的节点导致了树的总高度发生变化，例如例2插入红色节点树的总高度由4变为5
当插入节点的父亲节点更新为2或者-2时：插入节点前父亲节点平衡因子为1或者-1（左右子树存在一方高一方矮），当更新为2时，原父亲节点平衡因子为1，并且插入位置在平衡因子为1的父亲节点的右子树，例如在节点8右子树插入新节点；当更新为-2时，原父亲节点平衡因子为-1，插入位置平衡因子为-1的父亲节点的右子树（高的一方继续变高，矮的一方没有改变），此时需要进行旋转处理将平衡因子为2或者-2的节点对应的树进行调整使其恢复AVL树结构

AVL树插入时旋转与平衡因子更新¶

左单旋¶

当插入的节点在平衡因子为1的父亲节点的右子树的右子树上时，此时父亲节点的平衡因子更新为2，其右孩子节点的平衡因子分别为1和0时需要进行左单旋，例如下面的一种具体情况：

为了便于分析，将插入位置进行抽象化，a、b和c分别是高度h>=0的AVL子树，如下图所示：

此时因为父亲节点10的平衡因子变为了2，需要进行左旋，左旋需要进行的步骤如下：

Info

平衡因子计算：

h+1(新增节点所在层数)-1=1为20节点的平衡因子

h+1+1(20节点所在层数)-h=2为10节点的平衡因子

将20的左孩子给10节点作为其右孩子
将10降下作为20的左孩子
20节点作为本棵子树的根节点
更新10和20节点的平衡因子为0

结合变量parent、subR和subRL：

代码实现：

C++
// 左单旋
void rotateLeft(node* parent)
{
    // 定义节点
    node* subR = parent->_right;
    node* subRL = subR->_left;

    // 1. subRL变为parent的右孩子
    parent->_right = subRL;
    // 更新subRL的_parent为parent，需要注意当h=0时subRL节点不存在，所以需要进行判断subRL是否为空
    if (subRL)
    {
        subRL->_parent = parent;
    }
    // 2. parent变为subR的左孩子
    subR->_left = parent;
    // 3. subR变为本棵子树的根节点
    // 记录parent的父亲节点
    node* parentParent = parent->_parent;
    // 更新parent节点的父亲节点为subR
    parent->_parent = subR;
    // 更新parent节点的父亲节点的孩子节点为subR
    if (parentParent == nullptr)
    {
        // 父亲节点为空证明是根节点
        _root = subR;
        subR->_parent = nullptr;
    }
    else
    {
        if (parentParent->_left == parent)
        {
            parentParent->_left = subR;
        }
        else
        {
            parentParent->_right = subR;
        }

        // 更新subR的父亲节点
        subR->_parent = parentParent;
    }

    // 4. 更新平衡因子
    parent->_bf = subR->_bf = 0;
}

右单旋¶

当插入的节点在平衡因子为-1的父亲节点的左子树的左子树上时，此时父亲节点的平衡因子更新为-2，其左孩子节点的平衡因子分别为-1和0时需要进行右单旋，例如下面的一种具体情况：

为了便于分析，将插入位置进行抽象化，a、b和c分别是高度h>=0的AVL子树，如下图所示：

此时因为父亲节点10的平衡因子变为了-2，需要进行右旋，右旋需要进行的步骤如下：

Info

平衡因子计算：

h-(h+1(新增节点所在层数))=-1为20节点的平衡因子

h-(h+1+1(20节点所在层数))=-2为10节点的平衡因子

将5的右孩子作为10的左孩子
将10作为5的右孩子
将20作为本棵子树的根节点
更新10和20的平衡因子为0

结合变量parent、subL和subLR：

代码实现：

C++
// 右单旋
void rotateRight(node* parent)
{
    node* subL = parent->_left;
    node* subLR = subL->_right;

    // 1. 将subLR作为parent的左孩子
    parent->_left = subLR;
    // 更新subLR的parent
    if (subLR)
    {
        subLR->_parent = parent;
    }
    // 2. 将parent作为subL的右孩子
    subL->_right = parent;
    // 3. 将subL作为本棵子树的根节点
    // 记录当前parent节点的父亲节点
    node* parentParent = parent->_parent;
    // 更新parent的_parent为subL
    parent->_parent = subL;
    if (parentParent == nullptr)
    {
        _root = subL;
        subL->_parent = nullptr;
    }
    else
    {
        if (parentParent->_left == parent)
        {
            parentParent->_left = subL;
        }
        else
        {
            parentParent->_right = subL;
        }

        // 更新subL的父亲节点
        subL->_parent = parentParent;
    }

    // 4. 更新平衡因子
    subL->_bf = parent->_bf = 0;
}

左右单旋¶

当插入的节点在平衡因子为-1的父亲节点的左子树的右子树上时，此时父亲节点的平衡因子更新为-2，其右孩子节点的平衡因子分别为1和0时需要先进行左单旋再进行右单旋，例如下面的一种具体情况：

为了便于分析，将插入位置进行抽象化

a、b和c分别是高度h=0的AVL子树，如下图所示：

在当前情况下，b位置的节点即为新增节点，a和c位置此时均没有节点，10节点的平衡因子更新为-2，10节点的左孩子节点的平衡因子更新为1

Info

平衡因子计算：

5节点的平衡因子：h+1(新增节点所在层数)-h=1

10节点的平衡因子：h-(h+1+1(5节点所在层数))=-2
a、b、c和d分别是高度h>0的AVL子树，如下图所示：

Note

h>0在上图的情况下代表已经至少存在一个节点，即5的右子树开始有一个节点存在，所以6位置没有节点时用h-1代替

此时插入节点的位置有两种：
1. 在b位置插入，此时6节点的平衡因子变为-1，5节点的平衡因子变为1，10节点的平衡因子变为-2
  
  Info
  
  平衡因子的计算：
  
  6节点的平衡因子：h-1-h(新增节点所在层数)=-1
  
  5节点的平衡因子：h+1(6节点所在层数)-h=1
  
  10节点的平衡因子：h-(h+1+1)=-2
2. 在d位置插入，此时6节点的平衡因子变为-1，5节点的平衡因子变为1，10节点的平衡因子变为-2
  
  Info
  
  平衡因子的计算：
  
  6节点的平衡因子：h+1-h(新增节点所在层数)=1
  
  5节点的平衡因子：h+1(6节点所在层数)-h=1
  
  10节点的平衡因子：h-(h+1+1)=-2

尽管左右单旋有两种主要情况，但是实际上影响到的平衡因子的更新，主要思路还是先左旋再右旋，为了更好观察效果，以第二种情况中的第一种情况为例分析先左旋再右旋的步骤：

左旋（将多条路径更新化为一条路径更新）
1. 将6节点的左孩子作为5节点的右孩子
2. 将5节点作为6节点的左孩子
3. 将6节点作为本棵树的根节点，链接到10节点的左孩子（因为开始的父亲节点5是10节点的左孩子）
右旋（更新单一路径）
1. 将6节点的右孩子作为10节点的左孩子
2. 将10节点作为6节点的右孩子
3. 将6节点作为本棵树的根节点
4. 更新平衡因子

当树旋转结束后需要更新对应的平衡因子，此时需要考虑到两种主要情况，即h=0和h>0，结合变量parent、subL和subLR：

h=0，左右双旋结束后如下图所示：

h>0

插入位置在b，左右双旋结束后如下图所示：
插入位置在d，左右双旋结束后如下图所示：

代码实现：

C++
// 左右双旋
void rotateLR(node* parent)
{
    // 记录旋转前的平衡因子
    node* subL = parent->_left;
    node* subLR = subL->_right;
    int bf = subLR->_bf;

    // 1. 左右双旋
    // 左旋
    rotateLeft(parent->_left);
    // 右旋
    rotateRight(parent);

    // 更新平衡因子
    if (bf == 0)
    {
        subL->_bf = parent->_bf = 0;
    }
    else if (bf == -1)// 插入在d位置
    {
        subL->_bf = 0;
        subLR->_bf = 0;
        parent->_bf = 1;
    }
    else if (bf == 1)
    {
        subL->_bf = -1;
        subLR->_bf = 0;
        parent->_bf = 0;
    }
    else
    {
        assert(false);
    }
}

右左单旋¶

当插入的节点在平衡因子为1的父亲节点的右子树的左子树上时，此时父亲节点的平衡因子更新为2，其右孩子节点的平衡因子分别为-1和0时需要先进行右单旋再进行左单旋，例如下面的一种具体情况：

为了便于分析，将插入位置进行抽象化

a、b和c分别是高度h=0的AVL子树，如下图所示：

在当前情况下，c位置的节点即为新增节点，a和b位置此时均没有节点，10节点的平衡因子更新为-2，10节点的左孩子节点的平衡因子更新为1
a、b、c和d分别是高度h>0的AVL子树，如下图所示：

Note

h>0在上图的情况下代表已经至少存在一个节点，即20的左子树开始有一个节点存在，所以15位置没有节点时用h-1代替

此时插入节点的位置有两种：
1. 当插入在c位置时，15的平衡因子变为1，20的平衡因子变为-1，10的平衡因子变为2
2. 当插入在d位置时，15的平衡因子变为-1，20的平衡因子变为-1，10的平衡因子变为2

尽管右左单旋有两种主要情况，但是实际上影响到的平衡因子的更新，主要思路还是先右旋再左旋，为了更好观察效果，以第二种情况中的第一种情况为例分析先右旋再左旋的步骤：

右旋（将多条路径更新化为一条路径更新）
1. 将15的右孩子作为20的左孩子
2. 将20作为15的右孩子
3. 15作为本棵子树的根节点，链接到10节点的右孩子位置
左旋（更新单一路径）
1. 将15节点的左孩子作为10节点的右孩子
2. 10节点作为15节点的左孩子
3. 15作为本棵子树的根
4. 更新平衡因子

当树旋转结束后需要更新对应的平衡因子，此时需要考虑到两种主要情况，即h=0和h>0，结合变量parent、subR和subRL：

h=0，左右双旋结束后如下图所示：
h>0
1. 插入位置在c，左右双旋结束后如下图所示：
2. 插入位置在d，左右双旋结束后如下图所示：

代码实现：

C++
// 右左双旋
void rotateRL(node* parent)
{
    // 记录旋转前的平衡因子
    node* subR = parent->_right;
    node* subRL = subR->_left;
    int bf = subRL->_bf;

    // 1. 右左双旋
    // 右旋
    rotateRight(parent->_right);
    // 左旋
    rotateLeft(parent);

    // 更新平衡因子
    if (bf == 0)
    {
        subR->_bf = parent->_bf = 0;
    }
    else if (bf == 1)// 插入在c位置
    {
        subR->_bf = 0;
        subRL->_bf = 0;
        parent->_bf = -1;
    }
    else if (bf == -1) // 插入在d位置
    {
        subR->_bf = 1;
        subRL->_bf = 0;
        parent->_bf = 0;
    }
    else
    {
        assert(false);
    }
}

判断AVL树是否平衡¶

如果想知道上面设计的AVL树是否平衡，可以参考算法：二叉树基础练习篇的代码

AVL旋转可行性¶

以左单旋为例，其余类比推理即可

在左单旋中，选择b子树作为10节点的右孩子节点是可行的，因为b子树的所有节点满足比10节点大，比20节点小，根据二叉搜索树的规则进行旋转

AVL树节点删除（待补充）¶

AVL树分析¶

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即\(log_2 (N)\)。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合