【动画笔记】数据结构-AVL树的插入操作

本笔记主要围绕AVL树的平衡因子、纸上做题思路、失衡类型(LL/RR/LR/RL)、失衡调整方法、插入后回溯这几部分知识点展开。

⚠ 本笔记前置知识 : 二叉搜索(排序)树及其插入操作。

本文主要围绕AVL树的 平衡因子 、 纸上做题思路 、 失衡类型(LL/RR/LR/RL) 、 失衡调整方法 、 插入后回溯 这几部分知识点展开。

注:

本笔记中的平衡二叉树规定 所有左子树都小于其父节点，所有右子树都大于其父节点 。

本笔记中的平衡因子计算方法是 左子树高度 - 右子树高度 。

目录

简单介绍一下下 平衡因子 简述平衡二叉树的插入操作 什么是失衡节点 纸上快速做题思路 程序中定义树节点 失衡类型 - LL型失衡 举例 调整方法-右旋转 程序实现 失衡类型 - RR型失衡 举例 调整方法-左旋转 程序实现 失衡类型 - LR型失衡 举例 调整方法-先左旋转再右旋转 程序实现 失衡类型 - RL型失衡 举例 调整方法-先右旋转再左旋转 程序实现 程序中判断失衡类型 插入后一定要回溯到根节点吗？ 遇到平衡因子为0的节点时回溯可以停止 原因 相关题目 谢谢

简单介绍一下下

AVL树又称二叉 平衡搜索(排序)树 ，其最大的特点就是能维持所有节点的 左右子树高度差绝对值不大于1 。

因此，AVL树的 插入操作 要能维持住:

二叉搜索树的节点大小关系。

平衡二叉树中每个节点的【平衡因子】 绝对值不大于1 。

平衡因子

一般对于AVL树中的每个节点都会添加一个 平衡因子(Balance Factor)字段 ，平衡因子的值就是 左右子树的高度差 ，程序借此判断某棵子树是否平衡。

简述平衡二叉树的插入操作

AVL树的插入操作在 二叉搜索(排序)树的插入 的基础上新增了如下两个过程:

插入过程中将 沿途比较的节点 压入 栈 。

插入完成后，借助 弹栈 来沿着插入时比较的各节点 回到整棵树的根节点 (从叶节点到根结点进行 回溯 ):

更新沿途各节点的 高度 。(通过高度计算平衡因子)

沿途检查各节点的 平衡因子 ，若出现了 平衡因子绝对值 > 1 的情况，则 对不平衡的子树进行调整 以保证整棵树的平衡性。

✨ 当然，这里的插入操作也是可以用递归来实现的。

✨ 如果AVL树节点中有 指向父节点 的指针变量，那么这个过程就不需要栈辅助了，直接向上遍历【插入节点】的所有 祖先节点 直至回到根节点即可。

什么是失衡节点

当树中某个节点的 平衡因子 \(BF \notin \left [ -1,1 \right ]\) 时，这个节点就是 失衡节点 。

以这个失衡节点为根节点的 子树 就是一棵不平衡的子树。

纸上快速做题思路

这一招适合纸上解题，可以结合程序实现一起理解。
另外，字丑勿cue（╥﹏╥）

首先插入新节点（ 红色 的节点就是新插入的节点）:

此时【值为9的节点】平衡因子为2，为失衡节点。

从 失衡节点 开始，沿着【 刚刚插入新节点的比较路径 】找，找到其中 与其最邻近的两个点 :

（插入④时的比较路径是⑨->⑤->③，因此图中就找到了③、⑤、⑨）

包括失衡节点在内，现在 一共有三个节点 ，从中选择 值的大小在中间的节点 。（图中是⑤）

将 除了中间值节点外的 两个节点按照 二叉搜索树的规则 接到【中间值节点】上，然后将【中间值节点】接到原本 失衡节点所在的位置 ，作为这棵子树的根节点。

（图中⑤替换了原本⑨的位置，③和⑨变成了⑤的孩子）

将【 除了这三个节点之外 】的 节点 按照 二叉搜索树插入规则 插入到这三个节点组成的子树中:

（图中就是把剩余的节点④、⑥、⑩按规则插入到⑤为根的子树中，实际上④没有移动）

更新各节点的 平衡因子 :

这种解题方法在纸上可以快速解决LL/LR/RL/RR这些类型的平衡调整问题，非常实用。

程序实现的话也可以靠这个思路来记忆和理解。

程序中定义树节点

程序实现没有标准答案，合理即可。

这里的树节点 没有指向父节点 的指针，因此往树中插入节点的过程中需要压栈，以在插入完成后进行回溯。

 typedef struct TreeNode *Tree;

struct TreeNode
{
    Tree left;  // 左子树
    Tree right; // 右子树
    int height; // 节点所在高度，平衡因子靠这个算
    int val;    // 节点值
};
 

失衡类型 - LL型失衡

LL型字面展开来看就是 Left - Left 。意思是 新插入节点 位于 失衡节点 的 左孩子的左子树中 。

举例

新节点插入在【值为2的节点】的 左子树中 ，而【值为2的节点】又是【值为3的节点】的 左孩子 。

此时【值为3的节点】的平衡因子 BF = 2-0 = 2 > 1 ，是一个 失衡节点 。

注: 插入节点后的回溯过程当然是自下而上的，因此这里指的是自下而上 首个 失衡节点。

可以发现新节点插在【失衡节点】的 左孩子 的 左子树 中，这就是LL型失衡。

调整方法-右旋转

这里我结合 纸上快速做题思路 来写一下。

【值为3的节点】是失衡节点。

找到失衡节点 沿着插入路径上的 最邻近的两个节点，一共有三个节点。
这里可以看成是 以失衡节点为根结点的子树 。

就是图中框出来的几个节点。

找到三个节点中【 值在中间的节点 】，接下来的“右旋转”过程以它为 轴 。

上图中找出的就是【值为2的节点】。其实就是失衡节点的左孩子。

将 失衡节点 以【值在中间的节点】为轴进行 右旋转 (顺时针)，让【值在中间的节点】变成这棵子树的 新的根结点 。

上图中的【值为3的节点】围绕【值为2的节点】进行右旋转，变成【值为2的节点】的右子树。

【值为2的节点】 原本的右子树 变成【值为3的节点】的 左子树 。

【值为2的节点】成为新的子树根结点。(详见动图)

动图演示过程 :

通过动图演示就能很直观地看到这个“ 右旋转 ”的过程。

可以发现 旋转 节点围绕的“旋转轴”就是【三个节点中 中间值的节点 】

图中我特意标出了空子树 NULL ，程序实现的时候 一定要把子树考虑在内 哦。

程序实现

程序实现的时候并不需要比较三个节点的大小。

对某个节点进行 右旋转 操作时，实际上就是把这个节点 绕着其左孩子 进行顺时针“旋转”。

 // 失衡节点右旋操作，node是失衡结点
void rotateRight(Tree node)
{
    Tree nodeLeft = node->left;         // 失衡节点左子树
    Tree nodeRight = node->right;       // 失衡节点右子树
    Tree lChildLeft = nodeLeft->left;   // 失衡节点的左孩子的左子树
    Tree lChildRight = nodeLeft->right; // 失衡节点左孩子的右子树
    // 这里【没有指向父节点】的指针，我们直接修改结点的值来模拟移动结点即可
    int nodeVal = node->val;   // 失衡节点的值
    node->val = nodeLeft->val; // 交换失衡节点和左孩子的值
    nodeLeft->val = nodeVal;
    // 这里已经不是左孩子了，而是“旋转”下来的失衡节点
    nodeLeft->left = lChildRight; // 修改结点的左右子树
    nodeLeft->right = node->right;
    node->left = lChildLeft; // 和子树的根结点接上
    node->right = nodeLeft;
    // 此时node是子树根结点，lChildLeft是左子树，nodeLeft是右子树
    updateHeight(nodeLeft); // 更新有变动的结点的高度，先更新子树再更新根
    updateHeight(node);
}
 

失衡类型 - RR型失衡

RR型字面展开来看就是 Right - Right 。意思是 新插入节点 位于 失衡节点 的 右孩子的右子树中 。

举例

新节点插入在【值为8的节点】的 右子树中 ，而【值为8的节点】又是【值为7的节点】的 右孩子 。

此时【值为7的节点】的平衡因子 BF = 0-2 = -2 < -1 ，是一个 失衡节点 。

可以发现新节点插在【失衡节点】的 右孩子 的 右子树 中，这就是RR型失衡。

调整方法-左旋转

【值为7的节点】是失衡节点。

找到失衡节点 沿着插入路径上的 最邻近的两个节点，一共有三个节点。
这里可以看成是 以失衡节点为根结点的子树 。

就是图中框出来的几个节点。

找到三个节点中【 值在中间的节点 】，接下来的“左旋转”过程以它为 轴 。

上图中找出的就是【值为8的节点】。其实就是失衡节点的右孩子。

将 失衡节点 以【值在中间的节点】为轴进行 左旋转 (逆时针)，让【值在中间的节点】变成这棵子树的 新的根结点 。

上图中的【值为7的节点】围绕【值为8的节点】进行左旋转，变成【值为8的节点】的左子树。

【值为8的节点】 原本的左子树 变成【值为7的节点】的 右子树 。

【值为8的节点】成为新的子树根结点。(详见动图)

动图演示过程 :

RR型和LL型的调节过程中的操作是 对称 的。

程序实现

程序实现的时候并不需要比较三个节点的大小。

对某个节点进行 左旋转 操作时，实际上就是把这个节点 绕着其右孩子 进行逆时针“旋转”。

 // 失衡节点左旋操作，node是失衡节点
void rotateLeft(Tree node)
{
    Tree nodeLeft = node->left;          // 失衡节点左子树
    Tree nodeRight = node->right;        // 失衡节点右子树
    Tree rChildLeft = nodeRight->left;   // 失衡节点的右孩子的左子树
    Tree rChildRight = nodeRight->right; // 失衡节点的右孩子的右子树
    // 这里【没有指向父节点】的指针，我们直接修改结点的值来模拟移动结点
    int nodeVal = node->val;
    node->val = nodeRight->val; // 交换失衡节点和右孩子的值
    nodeRight->val = nodeVal;
    // 这里的nodeRight就是“旋转”下来的节点
    nodeRight->right = rChildLeft;
    nodeRight->left = node->left;
    node->left = nodeRight;
    node->right = rChildRight;
    // 此时node是子树根结点，nodeRight是左子树，rChildRight是右子树
    updateHeight(nodeRight); // 更新有变动的结点的高度，先更新子树再更新根
    updateHeight(node);
}
 

失衡类型 - LR型失衡

LR型字面展开来看就是 Left - Right 。意思是 新插入节点 位于 失衡节点 的 左孩子的右子树中 。

举例

新节点插入在【值为4的节点】的 右子树中 ，而【值为4的节点】又是【值为8的节点】的 左孩子 。

此时【值为8的节点】的平衡因子 BF = 2-0 = 2 > 1 ，是一个 失衡节点 。

可以发现新节点插在【失衡节点】的 左孩子 的 右子树 中，这就是LR型失衡。

调整方法-先左旋转再右旋转

【值为8的节点】是失衡节点。

找到失衡节点 沿着插入路径上的 最邻近的两个节点，一共有三个节点。
这里可以看成是 以失衡节点为根结点的子树 。

就是图中框出来的几个节点。

找到三个节点中【 值在中间的节点 】，接下来的“左旋转”过程以它为 轴 。

上图中找出的就是【值为7的节点】。其实是失衡节点的 左孩子的右孩子 。

将【(三个节点中) 值最小的节点 】以【值在中间的节点】为轴进行 左旋转 (逆时针)，让【值在中间的节点】转上来， 转变成LL型失衡的情况 。

上图中的【值为4的节点】围绕【值为7的节点】进行左旋转，变成【值为7的节点】的左子树。

【值为7的节点】 原本的左子树 变成【值为4的节点】的 右子树 。

【值为7的节点】成为了【值为8的节点】的 左孩子 。

此时整棵树已经调整成了 LL型失衡 的情况，接着用 右旋转 进行调整即可。详见动图。

动图演示过程 :

可以很直观地看到，首先用 左旋转 将平衡树转变为了 LL失衡 的情况，再用 右旋转 对树进行调整。

可以发现整个过程中， 旋转 节点围绕的“旋转轴”都是【三个节点中 中间值的节点 】

程序实现

程序实现的时候并不需要比较三个节点的大小。

对某个节点A进行 左旋转+右旋转 操作时，实际上做的是:

令该节点A的 左孩子 为 B ，首先将B 绕着B的右孩子 进行 逆时针旋转 。
(对B进行 左旋转 )

然后将节点A 绕着B 进行 顺时针旋转 。
(对A进行 右旋转 )

 // 失衡节点左右旋操作，node是失衡节点
rotateLeft(node->left); // 先对失衡节点的左孩子进行左旋
rotateRight(node);      // 再对失衡节点进行右旋
 

失衡类型 - RL型失衡

RL型字面展开来看就是 Right - Left 。意思是 新插入节点 位于 失衡节点 的 右孩子的左子树中 。

举例

新节点插入在【值为10的节点】的 左子树中 ，而【值为10的节点】又是【值为8的节点】的 右孩子 。

此时【值为8的节点】的平衡因子 BF = 0-2 = -2 < -1 ，是一个 失衡节点 。

可以发现新节点插在【失衡节点】的 右孩子 的 左子树 中，这就是RL型失衡。

调整方法-先右旋转再左旋转

【值为8的节点】是失衡节点。

找到失衡节点 沿着插入路径上的 最邻近的两个节点，一共有三个节点。
这里可以看成是 以失衡节点为根结点的子树 。

就是图中框出来的几个节点。

找到三个节点中【 值在中间的节点 】，接下来的“右旋转”过程以它为 轴 。

上图中找出的就是【值为9的节点】。其实是失衡节点的 右孩子的左孩子 。

将【(三个节点中) 值最大的节点 】以【值在中间的节点】为轴进行 右旋转 (顺时针)，让【值在中间的节点】转上来， 转变成RR型失衡的情况 。

上图中的【值为10的节点】围绕【值为9的节点】进行右旋转，变成【值为9的节点】的右子树。

【值为9的节点】 原本的右子树 变成【值为10的节点】的 左子树 。

【值为9的节点】成为了【值为8的节点】的 右孩子 。

此时整棵树已经调整成了 RR型失衡 的情况，接着用 左旋转 进行调整即可。详见动图。

动图演示过程 :

可以很直观地看到，首先用 右旋转 将平衡树转变为了 RR失衡 的情况，再用 左旋转 对树进行调整。

LR型和RL型的调节过程中的操作也是 对称 的。

可以发现整个过程中， 旋转 节点围绕的“旋转轴”始终都是【三个节点中 中间值的节点 】

程序实现

程序实现的时候并不需要比较三个节点的大小。

对某个节点A进行 右旋转+左旋转 操作时，实际上做的是:

令该节点A的 右孩子 为 B ，首先将B 绕着B的左孩子 进行 顺时针旋转 。
(对B进行 右旋转 )

然后将节点A 绕着B 进行 逆时针旋转 。
(对A进行 左旋转 )

 // 失衡节点右左旋操作，node是失衡节点
rotateRight(node->right); // 先对失衡节点的右孩子进行右旋
rotateLeft(node);         // 再对失衡节点进行左旋
 

程序中判断失衡类型

程序中，咱们依赖于 平衡因子 来判断失衡类型。

平衡因子由 左右子树的高度差决定 ，因此根据平衡因子能判断出新节点插入在哪里:

当 失衡节点 的平衡因子 > 1 时:

如果 失衡节点的左孩子 的平衡因子 > 0 ，则是LL型失衡。

如果 失衡节点的左孩子 的平衡因子 < 0 ，则是LR型失衡。

当 失衡节点 的平衡因子 < -1 时:

如果 失衡节点的右孩子 的平衡因子 < 0 ，则是RR型失衡。

如果 失衡节点的右孩子 的平衡因子 > 0 ，则是RL型失衡。

展开查看程序实现

 // curr节点失衡了, 需要进行调整
// bf是这个节点的平衡因子
if (bf > 1) // 失衡节点的平衡因子>1，说明左子树比较高，因此找失衡节点的左孩子
{
    // 看失衡节点左孩子的平衡因子
    int leftBf = balanceFactor(curr->left);
    if (leftBf > 0) // 这个左孩子的左子树高于右子树
    {
        // 这说明是LL型，即插入在失衡节点【左孩子的左子树中】而导致失衡，需要进行“右旋”进行调整
        rotateRight(curr);
    }
    else // 这个左孩子的右子树高于左子树
    {
        // 这说明是LR型，插入在失衡结点【左孩子的右子树中】而导致失衡，需要进行“左旋再右旋”进行调整
        rotateLeft(curr->left); // 先对左孩子进行左旋
        rotateRight(curr);      // 再对失衡节点进行右旋
    }
}
else if (bf < -1) // 失衡节点的平衡因子<-1，说明右子树比较高，因此找失衡节点的右孩子
{
    int rightBf = balanceFactor(curr->right);
    if (rightBf < 0) // 右孩子的右子树高于左子树
    {
        // 这说明是RR型，即插入在失衡节点【右孩子的右子树中】，需要进行“左旋”进行调整
        rotateLeft(curr);
    }
    else // 右孩子的左子树高于右子树
    {
        // 这说明是RL型，即插入在失衡节点【右孩子的左子树中】，需要进行“右旋再左旋”进行调整
        rotateRight(curr->right); // 先对右孩子进行右旋
        rotateLeft(curr);         // 再对失衡节点进行左旋
    }
}
 

插入后一定要回溯到根节点吗？

本文开头咱 简述了一下 AVL树的插入操作。

在往AVL树中插入了一个节点后，需要沿着 祖先节点 向上回溯到 根节点 ，沿途更新每个节点的 高度 ，并寻找失衡的节点来进行调整。

节点的高度用于计算平衡因子。

遇到平衡因子为0的节点时回溯可以停止

? 实际上，在插入后的 回溯过程 中，如果发现某节点的 平衡因子 = 0 ，就可以 不用再回溯 了。

原因

究其原因，咱们得关注一下插入前和插入后的 平衡因子 变化情况:

插入前，AVL树中 每棵子树都是平衡的 ，也就是说，所有节点的平衡因子都在 [-1, 1] 范围内。

若树中某 节点A 的平衡因子 \(BF \in \left \lbrace -1,1 \right \rbrace\) ，就意味着节点A的 左子树和右子树的高度差 的绝对值为1。

复习一下， BF = 左子树高度 - 右子树高度 。

如果当 插入了一个新节点 后， 节点A 的平衡因子 \(BF=0\) :

插入前 插入后 子树的高度 节点A所在的高度

节点A的平衡因子	\(BF=1\)	\(BF=0\)	节点A的 右子树变高 ，说明新节点 插入在其右子树中	无变化
节点A的平衡因子	\(BF=-1\)	\(BF=0\)	节点A的 左子树变高 ，说明新节点 插入在其左子树中	无变化

【节点A所在的高度】取决于 其较高的一棵子树 ，而当平衡因子BF从【1或-1】变为0时，只是节点A的【原本较矮的一棵子树】的高度变得 和较高的子树高度一样 了，因此节点A所在的高度理所当然 没有发生改变 。

在插入后的回溯过程中会 更新沿途节点的高度 。在更新 节点A的父节点【FA】的高度 时，由于节点A的高度没有发生变化，因此 FA节点的高度也不会发生变化 ；同时，FA节点的 平衡因子也不会发生变化 。

FA节点的高度 = max(节点A的高度, FA节点另一个孩子的高度) + 1

依此类推，节点A的 所有祖先节点 的高度和平衡因子都不会发生变化，因此 回溯过程在节点A这里就可以停止了 。

所以，在回溯过程中如果遇到了平衡因子为0的节点，就可以不用再继续下去了。

相关题目

正好在DotCpp上找到了一个只考察 AVL树插入和查找 的题目:

https://www.dotcpp.com/oj/problem1713.html

我的题解:

https://github.com/SomeBottle/bottleofcat/blob/main/Algo/code/C-Cpp/DataStructure/AVLTree-Insertion.cpp

谢谢

感谢你看到这里。希望我的笔记能对你有所帮助~ 再会！( ´･ω･)ﾉ

查看更多关于【动画笔记】数据结构-AVL树的插入操作的详细内容...