⚠ 本笔记前置知识: 二叉搜索(排序)树及其插入操作。
本文主要围绕AVL树的平衡因子、纸上做题思路、失衡类型(LL/RR/LR/RL)、失衡调整方法、插入后回溯这几部分知识点展开。
-
注:
-
本笔记中的平衡二叉树规定所有左子树都小于其父节点,所有右子树都大于其父节点。
-
本笔记中的平衡因子计算方法是
左子树高度 - 右子树高度
。
-
目录
- 简单介绍一下下
- 简述平衡二叉树的插入操作
- 什么是失衡节点
- 纸上快速做题思路
- 程序中定义树节点
- 失衡类型 - LL型失衡
- 失衡类型 - RR型失衡
- 失衡类型 - LR型失衡
- 失衡类型 - RL型失衡
- 程序中判断失衡类型
- 插入后一定要回溯到根节点吗?
- 相关题目
- 谢谢
简单介绍一下下
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树中插入了一个节点后,需要沿着祖先节点向上回溯到根节点,沿途更新每个节点的高度,并寻找失衡的节点来进行调整。
节点的高度用于计算平衡因子。